自己写的队列
这里我新加了一个打印函数,并且我只写了循环队列,教材有两种,一种是循环队列,一种是顺序队列,
但是顺序队列实在太耗空间了,基本用不到,所以我就直接跳了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
//自己写的队列(数组实现) //因为非循环队列太耗空间了,我就直接写循环队列,其实区别很小,要注意的就两点: //利用求余操作就可以实现:front=(front+1)%max rear=(rear+1)%max //例外需要注意的数组必须留一个空间,不能存满,为了方便判断队列满和队列空的情况 //要写的操作有 : 初始化队列 :initqueue , 销毁队列: destroyqueue , 判断为空: emptyqueue // 进队列 enqueue , 出队列 dequeueu 打印队列 printqueue #include<bits/stdc++.h> #define maxsize 100 using namespace std; typedef int elemtype;//之前不喜欢这样写,觉得太麻烦了,后来我想把int换成char去写字符串匹配的时候,就爱上了这样的写法 typedef struct{ elemtype data[maxsize]; int front,rear; }squeue; void initqueue(squeue*&q){ q=(squeue*)malloc(sizeof(squeue)); q->front=q->rear=0; } void destroyqueue(squeue*&q){ free(q); } bool emptyqueue(squeue*q){ return (q->front==q->rear); } bool enqueue(squeue*&q,elemtype e){ if((q->rear+1)%maxsize==q->front) return false; q->rear=(q->rear+1)%maxsize; q->data[q->rear]=e; return true; } bool dequeue(squeue*&q,elemtype &e){ if(q->rear==q->front) return false; q->front=(q->front+1)%maxsize; e=q->data[q->front];//因为队列中必须空一个数,空的数我们让front指向 return true; } void printqueue(squeue*q){ int pre=q->front; while(pre!=q->rear){ pre=(pre+1)%maxsize; cout<<q->data[pre]<<" "; } cout<<endl; } int main(){ squeue *q; elemtype e; initqueue(q); for(elemtype i=1;i<=10;i++) enqueue(q,i); printqueue(q); enqueue(q,5); enqueue(q,7); printqueue(q); dequeue(q,e); dequeue(q,e); dequeue(q,e); printqueue(q); } |
教材标准队列(循环队列)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
//顺序队列(环形队列)基本运算算法 #include <stdio.h> #include <malloc.h> #define MaxSize 100 typedef char ElemType; typedef struct { ElemType data[MaxSize]; int front,rear; //队首和队尾指针 } SqQueue; void InitQueue(SqQueue *&q) { q=(SqQueue *)malloc (sizeof(SqQueue)); q->front=q->rear=0; } void DestroyQueue(SqQueue *&q) { free(q); } bool QueueEmpty(SqQueue *q) { return(q->front==q->rear); } bool enQueue(SqQueue *&q,ElemType e) { if ((q->rear+1)%MaxSize==q->front) //队满上溢出 return false; q->rear=(q->rear+1)%MaxSize; q->data[q->rear]=e; return true; } bool deQueue(SqQueue *&q,ElemType &e) { if (q->front==q->rear) //队空下溢出 return false; q->front=(q->front+1)%MaxSize; e=q->data[q->front]; return true; } |
教材标准队列(顺序队列)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
//顺序队列(非环形队列)基本运算算法 #include <stdio.h> #include <malloc.h> #define MaxSize 100 typedef char ElemType; typedef struct { ElemType data[MaxSize]; int front,rear; //队头和队尾指针 } SqQueue; void InitQueue(SqQueue *&q) { q=(SqQueue *)malloc (sizeof(SqQueue)); q->front=q->rear=-1; } void DestroyQueue(SqQueue *&q) //销毁队列 { free(q); } bool QueueEmpty(SqQueue *q) //判断队列是否为空 { return(q->front==q->rear); } bool enQueue(SqQueue *&q,ElemType e) //进队 { if (q->rear==MaxSize-1) //队满上溢出 return false; //返回假 q->rear++; //队尾增1 q->data[q->rear]=e; //rear位置插入元素e return true; //返回真 } bool deQueue(SqQueue *&q,ElemType &e) //出队 { if (q->front==q->rear) //队空下溢出 return false; q->front++; e=q->data[q->front]; return true; } |