定义
队列（Queue）简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。
队头（Front）：允许删除的一端，又称队首。
队尾（Rear）：允许插入的一端。
循环队列元素入队
循环队列元素出队
队列的链式存储
队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。
动画网站：https://www.cs.usfca.edu/~galles/visualization/QueueLL.html
代码
流程：判断循环队列是否为空，入队，出队
#include <stdio.h>#define MaxSize 5
typedef int ElemType;
typedef struct{ElemType data[MaxSize];//数组,存储MaxSize - 1个元素int front,rear;//队列头,队列尾
}SqQueue;void InitQueue(SqQueue &Q){Q.front = Q.rear = 0;//初始化循环队列,就是让头和尾都指向零号
}//普安段循环队列是否为空
bool isEmpty(SqQueue &Q){return Q.rear == Q.front;
}//入队
bool EnQueue(SqQueue &Q,ElemType x){
// 判断循环队列是否满了,满了就不能入队了if((Q.rear + 1) % MaxSize == Q.front){return false;}Q.data[Q.rear] = x;//放入元素Q.rear = (Q.rear + 1) % MaxSize;//rear 要+1,如果大于数组最大下标,回到开头return true;}//出队
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);bool ret;ret = isEmpty(Q);if(ret){printf("SqQueue is Empty\n");}else{printf("SqQueue is not Empty\n");}EnQueue(Q,3);EnQueue(Q,4);EnQueue(Q,5);ret = EnQueue(Q,6);ret = EnQueue(Q,7);if(ret){printf("EnQueue success\n");}else{printf("EnQueue failed\n");}ElemType element;ret = DeQueue(Q,element);if(ret){printf("DeQueue success\n");}else{printf("DeQueue failed\n");}return 0;
}效果
队列的链表实现
代码
#include <stdio.h>
#include <stdlib.h>typedef int ElemType;
typedef struct LinkNode {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;//头结点的next指针为NULL
}//入队
void EnQueue(LinkQueue &Q,ElemType x){LinkNode *pnew = (LinkNode*) malloc(sizeof(LinkNode));pnew -> data = x;pnew -> next =NULL;//要让next为NULL;Q.rear -> next = pnew;//尾指针的next指向pnew,因为从尾部入队Q.rear = pnew;//rear要指向新的尾部
}bool DeQueue(LinkQueue &Q,ElemType &x){if(Q.rear == Q.front){//队列为空return false;}LinkNode* q = Q.front -> next;//拿到第一个结点,存入qx = q -> data;//获取要出对的元素值Q.front -> next = q->next;//让第一个结点断链if(Q.rear == q){//链表只剩余一个结点时,被删除后,要改变rearQ.rear = Q.front;}free(q);return true;
}
int main(){LinkQueue Q;bool ret;ElemType element;//存储出对元素InitQueue(Q);//初始化队列EnQueue(Q,3);EnQueue(Q,4);EnQueue(Q,5);EnQueue(Q,6);EnQueue(Q,7);ret = DeQueue(Q,element);if(ret){printf("DeQueue success element=%d\n",element);}else{printf("DeQueue failed\n",element);}return 0;
}效果
