数据结构中的队列是什么？

本文共计3333个文字，预计阅读时间需要14分钟。

队列的基本概念：队列是运算受限的线性表，其限制为先进先出（FIFO）。

队列的特点：- 先进先出（FIFO）：允许插入的一端称队尾，允许删除的一端称队头。- 头尾操作：队头删除，队尾插入。- 特殊队列：允许插入的一端称队尾，允许删除的一端称队头。

队列的基本概念

队列是运算受限的线性表

限制：一端插入，另一端删除。头删尾插

特点：先进先出(FIFO)允许插入(入队)的一端称队尾、允许删除(出队)的一端称队头。

队列的存储结构为链队或顺序队（常用循环顺序队）

队列的常见应用

队列的抽象数据类型定义

ADT Queue {

数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n } 约定an 端为队尾，a1 端为队头。

基本操作： InitQueue(&Q) 操作结果：构造一个空队列Q。

DestroyQueue(&Q) 初始条件：队列Q已存在。 操作结果：队列Q被销毁,不再存在。

ClearQueue(&Q) 初始条件：队列Q已存在。 操作结果：将Q清为空队列。

QueueEmpty(Q) 初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。

QueueLength(Q) 初始条件：队列Q已存在。 操作结果：返回Q的元素个数，即队列的长度。

GetHead(Q, &e) 初始条件：Q为非空队列。 操作结果：用e返回Q的队头元素。

EnQueue(&Q, e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。 DeQueue(&Q, &e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值 }ADT Queue

队列的表示和实现

队列的物理存储可以用顺序存储结构，也可以用链式存储结构。相应地，队列的存储方式也分为两种，即顺序队列和链式队列

在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队头到队尾的元素之外，还需附设两个“指针”front和rear，分别指示队头元素及队尾元素的位置。

为在c语言中描述方便起见，在此约定：初始化建空队列时，令front=rear=0，每当插入新的队尾元素时，尾指针增1；每当删除队列头元素时，头指针增1。

在非空队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一个位置。

队列顺序存储结构的不足

我们假设1个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队操作，其实就是在队尾追加1个元素，不需要移动任何元素，因此时间复杂度为O（1）。

与栈不同的是，队列元素的出列是在队头，即下标为0的位置，那也就意味着 队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为O(n) 。

可有时想想，为什么出列时一定要全部移动呢，如果不去限制队列的元素必须 存储在数组的前n个单元这一条件，出队的可能性就会大大增加，也就是说，队头不需要一定在下标为0的位置。

为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针， front 指针指向队头元素，rear 指针指向队尾元素的一个位置，这样当front=rear 肘，此队列是空队列。

队列的顺序表示——用一维数组base[MAXQSIZE]

#define MAXQSIZE 100//最大队列长度 Typedef struct { QElemType *base;//初始化的动态分配存储空间 int front; int rear;//下标位置 }SqQueue;//没加星号是普通类型，引用参数用“.”

解决假上溢的方法：

引入循环队列

循环队列解决队满时判断方法——少用一个元素空间

循环队列的初始化——队列的初始化

Status InitQueue(SqQueue &Q) { Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));//是个指针哦，能放0~MAXQSIZE-1个元素的地址 if(!Q.base) exit(OVERFLOW); Q.front=Q.rear=0;//头指针尾指针置为0，队列为空 return OK; }

求队列长度

循环队列，指针可能转一圈又回到原来的位置，rear值-front值可能为负，不合理。

int QueueLength(SqQueue Q) { return ((Q.rear-Q.front+MAXQSIZE)%MAXQSIZE); }

循环队列入队操作

Status EnQueue(SqQueue &Q,QElemType e) { if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;//首先要判断队是否满了 Q.base[Q.rear]=e;//只能插队尾，将新元素加入队尾 Q.rear=(Q.rear+1)%MAXQSIZE;//队尾指针+1 return OK; }

循环队列出队操作

Status DeQueue(SqQueue &Q,QElemType ) { if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front];//保存队头元素 Q.front=(Q.front+1)%MAXQSIZE;//对头指针+1 return OK; }

取队头元素

对头元素即为front指针指的位置

QElemType GetHead(SqQueue Q) { if(Q.front!=Q.rear)//队列不为空 return Q.base[Q.front];//返回队头指针元素的值，队头指针不变 }

循环队列代码实现

#include<stdio.h> typedef int QElemType; typedef int Status; #include<stdlib.h> #define MAXSIZE 100 #define OK 1 #define OVERFLOW -2 #define ERROR 0 typedef struct { QElemType *base; int front; int rear; }SqQueue; Status InitQueue(SqQueue *Q) { Q->base=(QElemType*)malloc(MAXSIZE*sizeof(QElemType)); if(!Q->base) exit(OVERFLOW); Q->front=Q->rear=0; return OK; } Status QueueLength(SqQueue Q) { return ((Q.rear-Q.front+MAXSIZE)%MAXSIZE); } Status EnQueue(SqQueue *Q,QElemType e) { if((Q->rear+1)%MAXSIZE==Q->front) return ERROR; Q->base[Q->rear]=e; Q->rear=(Q->rear+1)%MAXSIZE; return OK; } Status DeQueue(SqQueue *Q,QElemType e) { if(Q->front==Q->rear) return ERROR; Q->base[Q->front]=e; Q->front=(Q->front+1)%MAXSIZE; return OK; } QElemType GetHead(SqQueue Q,QElemType *e) { if(Q.front!=Q.rear) *e=Q.base[Q.front]; return *e; } Status DestroyQueue(SqQueue *Q) { Q->front=Q->rear=0; return OK; } Status ClearQueue(SqQueue *Q) { while(Q->front) { Q->front=Q->rear=0; } return OK; } Status QueueEmpty(SqQueue Q) { if(Q.front==Q.rear) { printf("队为空！\n"); return ERROR; } return (Q.front==Q.rear)?0:1; } Status Print(SqQueue Q) { if(Q.front==Q.rear) { printf("\n队列为空！\n"); return ERROR; } printf("\n队列中的元素为:\n"); while(Q.front!=Q.rear) { printf("%d\t",Q.base[Q.front]); Q.front=(Q.front+1)%MAXSIZE; } return OK; } int main() { SqQueue Q; InitQueue(&Q); int x,i; QElemType e; printf("输入队列的长度："); scanf("%d",&x); for(i=1;i<=x;i++) { scanf("%d",&e); EnQueue(&Q,e); } Print(Q); e=GetHead(Q,&e); printf("\n队头元素为：%d",e); printf("\n出队\n"); DeQueue(&Q,e); Print(Q); DestroyQueue(&Q); Print(Q); ClearQueue(&Q); Print(Q); return 0; }

链队——队列的链式表示和实现

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。

一个链队列需要两个分别指示队头和队尾的指针（头指针，尾指针）才能唯一确定 。

为了操作方便，给链队列添加一个头结点，并令头指针指向头结点 。

链队为空的判定条件：头指针和尾指针均指向头结点。

若用户无法估计所用队列的长度，则宜采用链队列。

链队列的类型定义：

#define MAXQSIZE 100 typedef struct QNode { QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front;//队头指针 QueuePtr rear;//队尾指针 }LinkQueue;//链式队列

链队列运算指针变化状况

（a)空队列，front指针和rear指针指向同一个地方

（b)元素x入队，入队只能从队尾进入

（c)y入队列

（d）x出队

链队列的操作——链队列初始化

在内存中找到这样一个头结点，然后首尾指针都指向这个头结点。

Status InitQueue(LinkQueue &Q) { Q.front=Q.rear=((QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW); Q.front->next=NULL; return OK; }

链队列的操作——销毁链队列

算法思想：从对头结点开始，依次释放所有结点

Status DestroyQueue(LinkQueue &Q) { while(Q.front) { p=Q.front->next; free(Q.front); Q.front=p; }//Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear; return OK; }

链队列的操作——将元素e入队（尾插）

Status EnQueue(LinkQueue &Q,QElemType e) { p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p->data=e; p->next=NULL; Q->rear->next=p; Q.rear=p;//修改尾指针 return OK; }

链队列的操作——链队列的出队（删除头的后继）

出队操作时，就是头结点的后继出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指针指向头结点。

Status DeQueue(LinkQueue &Q,QElemType &e) { if(Q.front==Q.rear) return ERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p)//如果删除的是尾结点 Q.rear=Q.front;//都指向头结点 free p; return OK; }

链队列的操作——求链队列的队头元素

Status GetHead(LinkQueue Q,QElemType &e) { if(Q.front==Q.rear) return ERROR; e=Q.front->next->data; return OK; }

链队列代码实现

#include<stdio.h> #include<stdlib.h> #define OVERFLOW -2 #define OK 1 #define TRUE 1 #define FALSE 0 #define ERROR 0 typedef int QElemType; typedef int Status; typedef struct QNode { QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; Status InitQueue(LinkQueue *Q) { Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q->front) exit(OVERFLOW); Q->front->next=NULL; return OK; } Status DestroyQueue(LinkQueue *Q) { while(Q->front) { Q->rear=Q->front->next; free(Q->front); Q->front=Q->rear; } return OK; } Status ClearQueue(LinkQueue *Q) { while(Q->front) { Q->front=Q->rear=NULL; } return OK; } Status QueueEmpty(LinkQueue Q) { if(Q.front==Q.rear) return TRUE; else return FALSE; } Status QueueLength(LinkQueue Q) { int n=0; QueuePtr p; p=Q.front; while(p!=Q.rear) { n++; p=p->next; } return n; } Status GetHead(LinkQueue Q,QElemType *e) { if(Q.front==Q.rear) return ERROR; *e=Q.front->next->data; return *e; } Status EnQueue(LinkQueue *Q,QElemType e) { QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p->data=e; p->next=NULL; Q->rear->next=p; Q->rear=p; return OK; } Status DeQueue(LinkQueue *Q,QElemType *e) { QueuePtr p; if(Q->front==Q->rear) return ERROR; p=Q->front->next; *e=p->data; Q->front->next=p->next; if(Q->rear==p) Q->rear=Q->front; free(p); return OK; } Status Print(LinkQueue Q) { if(Q.front==Q.rear) { printf("队空！\n"); return ERROR; } QueuePtr p; p=Q.front->next; printf("队列为：\n"); while(p) { printf("%d\t",p->data); p=p->next; } printf("\n"); return OK; } int main() { LinkQueue Q; InitQueue(&Q); int x,i; QElemType e; printf("输入队列的长度："); scanf("%d",&x); for(i=1;i<=x;i++) { scanf("%d",&e); EnQueue(&Q,e); } Print(Q); e=GetHead(Q,&e); printf("队头元素为：%d",e); printf("\n删除\n"); DeQueue(&Q,&e); Print(Q); DestroyQueue(&Q); Print(Q); ClearQueue(&Q); Print(Q); return 0; }

总结

栈是限定仅在表尾进行插入和删除操作的线性表。

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

它们均可以用线性表的顺序存储结构来实现，但都存在着顺序存储的一些弊端。

因此它们各自有各自的技巧来解决这个问题，对于栈来说，如果是两个相同数据类型的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据，这就可以最大化地利用数组的空间。

对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗，使得本来插入和删除是O(n)的时间复杂度变成了O(1)。