❤️队列的顺序实现❤️
#include <stdio.h> #define MAXSIZE 10//队列元素的最大个数 //顺序队列的描述 typedef struct { ElemType data[MAXSIZE];//静态数组存放队列元素 int front,rear;//队头指针，队尾指针 }sqQueue; //初始化一个队列 void InitQueue(sqQueue &Q){ Q.rear=Q.front=0;//初始化时，队尾指针指向队头指针 } //判断队列是否为空 bool QueueEmpty(sqQueue &Q){ if(Q.rear==Q.front)//对空条件 return true; else return FALSE; } int main() { //声明一个队列 sqQueue Q; //初始化一个队列 InitQueue(Q); //判断队列是否为空 QueueEmpty(Q); return 0; }
❤️循环队列的入队操作❤️
- 顺序队列在队列满的情况下容易发生假溢出的情况，所以引入了循环队列。
- 顺序队列满的条件无法代码表示，所以我们引入了模运算的方式进行的表示。
- 队列满：
(Q.rear+1)%MAXSIZE==Q.front - 顺序队列–>(抽象成)循环队列：
Q.rear=(Q.rear+1)%MAXSIZE,这里采用的是队尾指针加1取模，使得顺序队列的存储空间在逻辑上变成了“环状”，也就形成了循环队列。
这里需要解释一下，这是取余操作的神奇之处，奇妙之处。设定总事件为5，分别为0,1,2,3,4。这5个小事件分别对5取余操作，最后得到的结果只会在0,1,2,3,4之间进行循环，利用取余循环的特征，我们可以使得原本的顺序队列在存储空间逻辑上变成循环的环状。
#include <stdio.h> typedef struct { ElemType data[MAXSIZE];//静态数组存放队列元素 int front,rear;//队头指针，队尾指针 }sqQueue; //入队操作 bool EnQueue(sqQueue &Q,ElemType e){ if((Q.rear+1)%MAXSIZE==Q.front) return FALSE;//队满则报错 Q.data[Q.rear]=x;//新元素插入队尾 Q.rear=(Q.rear+1)%MAXSIZE;//队尾指针加1 return true; } int main() { //声明一个队列 sqQueue Q; //初始化一个队列 InitQueue(Q); //判断队列是否为空 QueueEmpty(Q); //入队操作 EnQueue(Q,x); return 0; }
❤️循环队列的出队操作❤️
#include <stdio.h> typedef struct { ElemType data[MAXSIZE];//静态数组存放队列元素 int front,rear;//队头指针，队尾指针 }sqQueue; //出队操作 bool DeQueue(sqQueue &Q,ElemType &x){ if(Q.rear==Q.front) return FALSE; x=Q.data[Q.front]; Q.front=(Q.front+1)%MAXSIZE;//把这个删了就可以获得队头元素 return true; } // int main() { //声明一个队列 sqQueue Q; //初始化一个队列 InitQueue(Q); //判断队列是否为空 QueueEmpty(Q); //入队操作 EnQueue(Q,x); //出队操作 DeQueue(Q,x); return 0; }
❤️队列的链式实现❤️
#include <stdio.h> #include <cstdlib> //队列的链式存储类型 typedef struct {//链式队列的结点 ElemType data; struct LinkNode *next; }LinkNode; typedef struct {//链式队列 LinkNode *front,*rear;//队列的头指针和尾指针 }LinkQueue; //=====================队列的基本操作============================ //队列的初始化 void InitQueue(LinkQueue &Q){ Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode));//建立头结点 Q.front->next=null;//初始化为空 } //判断队空 bool IsEmpty(LinkQueue Q){ if(Q.rear==Q.front)//队列为空的条件 return true; else return false; } //入队操作 void EnQueue(LinkQueue &Q,ElemType x){ LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode)); s->data=x; s->next=null;//创建新节点，把数据插入到链尾 Q.rear->next=s; Q.rear=s; } //出队操作 bool DeQueue(LinkQueue &Q,ElemType &x){ if(Q.rear==Q.front) return false;//空队操作 LinkNode *p=Q.front->next; x=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); return true; } int main() { return 0; }
