一、何为队列？

队列 (Queue) ：是一种先进先出 (First In First Out ,简称 FIFO) 的线性表，也是运算受限的线性表。只允许在表的一端进行插入，而在另一端进行删除。

队首 (front) ：允许进行删除的一端称为队首。

队尾 (rear) ：允许进行插入的一端称为队尾。

队列中没有元素时称为空队列。在空队列中依次加入元素 a 1 , a 2 , …, a n 之后, a 1 是队首元素, a n 是队尾元素。显然退出队列的次序也只能是 a 1 , a 2 , …, a n ,即队列的修改是依先进先出的原则进行的,如图 3-5 所示。

二、基本操作

创建新队列判空进队出队清空队获得队头元素遍历队销毁队队长

三、队列的存储实现及运算实现

与线性表、栈类似，队列也有顺序存储和链式存储两种存储方法。

1．顺序队列

循环队列的类型定义如下：

#define MAXQSIZE 100 //最大队列长度

typedef struct {

QElemType *base; //动态分配存储空间

int front; //头指针，若队列不空，指向队列头元素

int rear; //尾指针，若队列不空，指向队列尾元素的下一个位置

} SqQueue;

下面是循环队列上基本操作的实现。

（1）入队：

int 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;

return OK;

}

（2）出队：

int DeQueue (SqQueue &Q, QElemType &e) {

if (Q.front = = Q.rear) return ERROR;

e = Q.base[Q.front];

Q.front = (Q.front+1) % MAXQSIZE;

return OK;

}

（3）求循环队列元素个数：

int QueueLength（SqQueue Q）{

return (Q.rear-Q.front+MAXQSIZE) %MAXQSIZE；

}

2．链队列

链式存储的队称为链队列。和链栈类似，用单链表来实现链队列，根据队的先进先出原

则，为了操作上的方便，分别需要一个头指针和尾指针。

链队列的形式描述如下：

typedef struct QNode { // 结点类型

QElemType data;

struct QNode *next;

} QNode, *QueuePtr;

typedef struct { //链队列类型

QueuePtr front; //队头指针

QueuePtr rear; //队尾指针

} LinkQueue;

定义一个指向链队列的指针：LinkQueue Q;

下面是链队列的基本运算的实现。

（1）入队

int EnQueue (LinkQueue &Q, QElemType e) {

QNode *p;

p = （QNode *）malloc（sizeof（QNode））;

p->data = e;

p->next = NULL;

Q.rear->next = p;

Q.rear = p;

return OK;

}

（2）出队

int DeQueue (LinkQueue &Q, QElemType &e) {

if (Q.front == Q.rear) return ERROR; //队空，出队失败

p = Q.front->next;

e = p->data; //队头元素放 e 中

Q.front->next = p->next;

if(Q.rear==p) Q.rear= Q.front; //只有一个元素时，此时还要修改队尾指针

free (p);

return OK;

}

3．除了栈和队列之外，还有一种限定性数据结构是双端队列。

（1）双端队列：可以在双端进行插入和删除操作的线性表。

（2）输入受限的双端队列：线性表的两端都可以输出数据元素，但是只能在一端输入数

据元素。

（3）输出受限的双端队列：线性表的两端都可以输入数据元素，但是只能在一端输出数

据元素。

结束语

好了，今天的知识就分享到这里，欢迎关注“怀念感觉12”，私信关键词：学习资料，获取更多学习资源，如果文章对你有有帮助，请收藏关注，在今后与你分享更多学习c/c++的文章。同时欢迎在下面评论区留言如何学习c/c++。