数据结构1-4队列

一、队列是什么？

先举一个日常例子，排队买饭。

排队买饭

大家按先来后到的顺序，在窗口前排队买饭，先到先得，买完之后走开，轮到下一位买，新来的人排在队尾，不能插队。

可见，上面的“队”的特点是只允许从一端进入，从另一端离开。

这样的一个队，放在数据结构中就是“队列”。

首先，队列是一个线性表，所以它具有线性表的基本特点。

其次，队列是一个受限的线性表，受限之处为：只允许从一端进入队列，从另一端离开。

由此可得： 

        队列Queue，是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除（只允许在队尾添加元素，在队头删除元素，不支持随机访问），向队列中插入元素称为入队或进队；删除元素称为出队或离队,FIFO

相关名词解释：

入队：进入队列，即向队列中插入元素出队：离开队列，即从队列中删除元素队头：允许出队(删除)的一端队尾：允许入队(插入)的一端队头元素：队列中最先入栈的元素队尾元素：队列中最后入栈的元素

二、队列的实现思路

和栈一样，队列也可以有两种实现方式：数组实现的顺序队列和链表实现的链队列。

2.1 队列的链式存储 2.1.1 原理

        队列的链式表示称为链队列，实际是一个同时带有队头指针和队尾指针的单链表。

头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点

以看到，要实现一个链队列，需要以下结构：

1.单链表的基本单元结点 —— QueueNode

存储数据的数据域 —— data指向下一个结点的指针域 —— next

2.指向链表的头指针 —— head

3.标识队头端的队头指针 —— front

4.标识队尾端的队尾指针 —— rear

其中，头指针 head 和队头指针 front 都指向了单链表的第一个结点，所以这个指针可以合二为一，队头指针即头指针。

如此一来，我们可以借助链表的尾插法实现队列的入队操作，借助链表的头删法实现队列的出队操作。

 可参考动画版：Linked List Queue Visualization

链队列入队出队动画

2.1.2 队列的状态

【空队列】：空队列中没有元素，此时，队头下标和队尾下标均为 0，即front = rear = 0： 

【非空非满队列】：队列不是空队列且有剩余空间：

【满队列】：顺序队列分配的固定空间用尽，没有多余空间，不能再插入元素，此时 front = 0，rear = MAXSIZE：

2.1.3 代码实现 typedef int Elemtype; typedef struct LinkNode { Elemtype data; struct LinkNode *next; }LinkNode;//先进先出 typedef struct { LinkNode *front, *rear; }LinkQueue; 2.1.3.1 初始化队列 //队列的初始化，使用的是带头节点的链表 void init_queue(LinkQueue &Q) { Q.front = Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); Q.front->next =NULL; } 2.1.3.2 入队 //入队 void enqueue(LinkQueue &Q, Elemtype m) { LinkNode *pnew = (LinkNode *)malloc(sizeof(LinkNode)); pnew->data = m; pnew->next =NULL;//要让next 为null Q.rear->next = pnew;//尾指针next指向pnew,尾插法 Q.rear =pnew;//rear指向新的尾部 } 2.1.3.3 出队 bool dequeue(LinkQueue &Q, Elemtype &m) { if (Q.front ==Q.rear) {//队列为空 return false; } LinkNode *q=Q.front->next;//拿到第一个节点，存入q Q.front->next = q->next;让节点断链 m = q->data; if (Q.rear ==q) { Q.rear = Q.front;//链表只剩一个节点时，被删除后要改变rear } free(q); return true; } 2.1.3.4 主函数 int main() { LinkQueue Q; init_queue(Q); enqueue(Q, 3); enqueue(Q, 4); // enqueue(Q, 5); Elemtype elem; bool ret; ret = dequeue(Q,elem); if (ret) { printf("dequeue success ele=%d\n",elem); } else { printf("dequeue failed\n"); } ret = dequeue(Q,elem); if (ret) { printf("dequeue success ele=%d\n",elem); } else { printf("dequeue failed\n"); } ret = dequeue(Q,elem); if (ret) { printf("dequeue success ele=%d\n",elem); } else { printf("dequeue failed\n"); } return 0; }

三、循环队列 3.1 原理

将这种顺序队列画成一个圆：

循环队列的 rear 和 front 能够在队列中一圈一圈地转，像钟表的时针和分针一样。 

【空队列】：队列中没有元素，空队列的条件  front = rear 

【满队列】：少用一个元素，rear + 1 = front

【归零法】：就像钟表的时针满 12 归零一样，front 和 rear 也应该满某个数后归零，这个数就是 MAXSIZE。

比如 rear = 6 时，如果按平常做法来 ，下一步应该是 rear = 7，但在这里，我们让其归零，所以下一步应该是 rear = 0。

用数学公式来表示上面的归零过程就是：rear % MAXSIZE

所以满队列的判断条件应该为：(rear + 1) % MAXSIZE = front。

3.2 循环队列的数组实现 3.2.1 定义 typedef int ElementType; typedef struct { ElementType data[MaxSize]; int front, rear;//队列头，队列尾 }SqQueue; 3.2.2  初始化循环队列 void init_queue(SqQueue &Q) { Q.front =Q.rear = 0;//初始化循环队列，让头尾都指向零号 } 3.3.3 判断空队 bool is_empty(SqQueue Q) { return Q.front==Q.rear; } 3.3.4 入队

//入队 bool enqueue(SqQueue &Q,ElementType m ) { //判断循环队列是否满？ if ((Q.rear +1) % MaxSize == Q.front){ return false; } Q.data[Q.rear]=m; Q.rear=(Q.rear + 1)%MaxSize;//rear +1 ,如果大于数组最大下标需要回到开头 return true; } 3.3.5 出队

bool dequeue(SqQueue &Q, ElementType &m) { if (Q.front == Q.rear) { return false; } m = Q.data[Q.front]; Q.front = (Q.front + 1) %MaxSize; return true; } 3.3.6 主函数 int main() { SqQueue Q; init_queue(Q); bool ret; ret= is_empty(Q); if (ret) { printf("SqQueue is empty\n"); }else { printf("SqQueue is not empty\n"); } enqueue(Q, 3); enqueue(Q, 4); enqueue(Q, 5); enqueue(Q, 6); ret = enqueue(Q, 7); ret = enqueue(Q, 8); if (ret) { printf("SqQueue success\n"); }else { printf("SqQueue failed\n"); } ElementType element; ret = dequeue(Q, element); if (ret) { printf("dequeue success\n"); }else { printf("dequeue failed\n"); } ret = enqueue(Q, 8); if (ret) { printf("SqQueue success\n"); }else { printf("SqQueue failed\n"); } return 0; }  3.3循环队列的链式存储实现（单向循环链表）

队头指针为front，队尾指针为rear；

队空的判断条件：front== rear

队满的判定条件：front == rear->next

3.3.1 代码实战 typedef int ElemType; typedef struct LNode { ElemType data; struct LNode* next; }LNode, *LinkList; 3.3.1.1 初始化 void CircleQueue(LinkList &front,LinkList &rear) { front=(LinkList)malloc(sizeof(LNode)); rear = front; rear->next = front; EnQueue(front,rear,3); EnQueue(front,rear,3); DeQueue(front,rear); DeQueue(front,rear); DeQueue(front,rear); } 3.3.1.2 入队 void EnQueue(LinkList &front,LinkList &rear, ElemType x) { LinkList pnew; if (rear->next == front) { pnew = (LinkList)malloc(sizeof(LNode)); rear->data = x; pnew->next = rear->next; rear->next = pnew; rear = pnew; } else { rear->data =x; rear = rear->next; } } 3.3.1.2 出队 void DeQueue(LinkList &front,LinkList &rear) { if (front == rear) { printf("the queue is empty\n"); } else { printf("the valude=%d\n",front->data); front = front->next; } }

参考地址： .51cto /article/656335.html