一、队列的定义
队列是啥？
数据从表的一端进，从另一端出，且遵循 "先进先出" 原则的线性存储结构就是队列。
队列的两个基本操作：入队将一个数据放到队列尾部；出队从队列的头部取出一个元素。
队列的应用：循环队列、阻塞队列、并发队列、优先级队列等。
栈和队列不要混淆，栈结构是一端封口，特点是"先进后出"；而队列的两端全是开口，特点是"先进先出"。
队列存储结构的实现有以下两种方式：
- 顺序队列：在顺序表的基础上实现的队列结构；
- 链队列：在链表的基础上实现的队列结构；
两者的区别仅是顺序表和链表的区别，即在实际的物理空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。
队列的操作
入队（尾部入队）
①将值存入rear所代表的位置。
②rear = (rear+1)%数组的长度。
出队（头部出队）
front = (front+1)%数组的长度。
队列是否为空
front和rear的值相等，则该队列就一定为空。
假溢出
随着入队、出队的进行，会使整个队列整体向后移动，就会出现上图中的现象：队尾指针已经移到了最后，即队尾出现溢出，无法再进行入队操作，然而实际上，此时队列中还有空闲空间，这种现象称为“假溢出”。
解决“假溢出”的三种办法：
方法一：每次删除队头元素后，把整个队列向前移动一个位置，这样可保证队头元素在存储空间的最前面。但每次删除元素时，都要把表中所有元素向前移动，效率太低。
方法二：当队尾指针出现溢出时，判断队头指针位置，如果前部有空闲空间，则把当前队列整体前移到最前方。这种方法移动元素的次数大为减少。
方法三：将队列看成头尾相接的循环结构，当队尾指针到队尾后，再从队头开始向后指，这样就不需要移动队列元素了，显然，第三种方法最经济、应用最多，这种顺序队列被称为“循环队列”或“环形队列”。
二、循环队列
采用了这种头尾相接的循环队列后，入队的队尾指针加1操作及出队的队头指针加1操作必须做相应的修改，以确保下标范围为0~Max_Size-1。对指针进行取模运算，就能使指针到达最大下标位置后回到0，符合“循环”队列的特点。
因此入队时队尾指针加1操作改为： pQueue->tail = (pQueue->tail+1) % MAX_SIZE;
入队时队尾指针加1操作改为： pQueue->head = (pQueue->head+1) % MAX_SIZE。
1.结构
/* 循环队列的顺序存储结构 */
typedef struct
{
QElemType data[MAXSIZE];
int front; /* 头指针 */
int rear; /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}SqQueue
2.初始化
int InitSqQueue(SqQueue *Q){
Q->front = 0;
Q->rear = 0;
return 1;
}
3.清空
int ClearSqQueue(SqQueue *Q){
Q->front = Q->rear = 0;
return 1;
}
4.是否为空
int IsSqQueueEmpty(SqQueue Q){
//队空标记
if (Q.front == Q.rear)
return 1;
else
return 0;
}
5.获取队列长度
(Q.rear - Q.front + MAXSIZE)%MAXSIZE;
6.获取队列头元素
int GetSqQueueHead(SqQueue Q,QElemType *e){
if (Q.front == Q.rear)
return 0;
*e = Q.data[Q.front];
return 1;
}
7.插入元素
int EnterSqQueue(SqQueue *Q,QElemType e){
if((Q->rear+1)%MAXSIZE == Q->front)
return 0;
Q->data[Q->rear] = e;
Q->rear = (Q->rear+1)%MAXSIZE;
return 1;
}
8.删除元素
int DeleteSqQueue(SqQueue *Q,QElemType *e){
if (Q->front == Q->rear) {
return 0;
}
*e = Q->data[Q->front];
Q->front = (Q->front+1)%MAXSIZE;
return 1;
}
9.遍历队列
int ReadSqQueue(SqQueue Q){
int I;
i = Q.front;
while (i != Q.rear) {
printf("%d ",Q.data[i]);
i = (i+1)%MAXSIZE;
}
printf("\n");
return 1;
}
三、链式队列
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。
为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。链队列示意图：
链队列.jpeg
当队列为空时，front和rear都指向头结点。
队列为空.jpeg
1.结构
/* 循环队列的顺序存储结构 */
typedef int Status;
typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */
typedef struct QNode /* 结点结构 */
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct /* 队列的链表结构 */
{
QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
2.初始化
int InitLinkQueue(LinkQueue *Q){
Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
if (!Q->front) {
return 0;
}
Q->front->next = NULL;
return 1;
}
- 销毁队列
int DestoryLinkQueue(LinkQueue *Q){
while (Q->front) {
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
return 1;
}
4.置空
int ClearLinkQueue(LinkQueue *Q){
QueuePtr p,q;
Q->rear = Q->front;
p = Q->front->next;
Q->front->next = NULL;
while (p) {
q = p;
p = p->next;
free(q);
}
return 1;
}
5.是否为空
int IsLinkQueueEmpty(LinkQueue Q){
if (Q.front == Q.rear)
return 1;
else
return 0;
}
6.获取队列长度
int LinkQueueLength(LinkQueue Q){
int i= 0;
QueuePtr p;
p = Q.front;
while (Q.rear != p) {
i++;
p = p->next;
}
return i;
}
7.获取队列头元素
int GetLinkQueueHead(LinkQueue Q,QElemType *e){
if (Q.front != Q.rear) {
*e = Q.front->next->data;
return 1;
}
return 0;
}
8.插入元素
int EnterLinkQueue(LinkQueue *Q,QElemType e){
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
if (!s) {
return 0;
}
s->data = e;
s->next = NULL;
Q->rear->next = s;
Q->rear = s;
return 1;
}
9.删除元素
int DeleteLinkQueue(LinkQueue *Q,QElemType *e){
QueuePtr p;
if (Q->front == Q->rear) {
return 0;
}
p = Q->front->next;
*e = p->data;
Q->front->next = p ->next;
if(Q->rear == p) Q->rear = Q->front;
free(p);
return 1;
}
10.遍历队列
int ReadLinkQueue(LinkQueue Q){
QueuePtr p;
p = Q.front->next;
while (p) {
p = p->next;
}
return 1;
}
网友评论