数据结构——栈和队列（队列的定义、顺序队列以及链式队列的基本操作）
目录
队列（queue）的定义
顺序队——队列的顺序表示和实现
顺序队列（循环队列）的类型定义
顺序队列上溢问题的解决方法
编辑
循环队列的基本操作
队列的基本操作——队列的初始化
队列的基本操作——求队列的长度
队列的基本操作——循环队列入队
队列的基本操作——循环队列出队
队列的基本操作——取队头元素
队列的基本操作——取队尾元素
链队——队列的链式表示和实现
链队列的类型定义
链队列的基本操作
链队列的基本操作——链队列初始化
链队列的基本操作——链队列销毁
链队列的基本操作——将元素e入队
链队列的基本操作——将元素e出队
队列（queue）的定义
顺序队——队列的顺序表示和实现
- 队列和栈一样，也是限定只能在表的“端点”进行的线性表。
- 队列在插入的时候，只能在表尾进行插入，在删除的时候，只能在表头进行删除。（先进先出），表尾即队尾，表头即队头。
- 栈和队列是线性表的子集（是插入和删除位置受限的线性表）
- 由于队列的操作具有先进先出的特性，使得队列成为程序设计中解决类似排队问题的有用工具。
- 队列的逻辑结构与同线性表相同，仍为一对一关系。
- 队列的存储结构有顺序队和链队，以循环顺序队列更常见。
- 关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。
顺序队列（循环队列）的类型定义
- 队列的顺序表示——用一维数组base[MAXQSIZE]
#define MAXQSIZE 100 //最大队列长度
typedef struct
{
QElemType* base; //初始化的动态分配存储空间
int front; //头指针（队头元素的下标）
int rear; //尾指针（队尾元素的下标）
}SqQueue;顺序队列上溢问题的解决方法
初始：front = rear = 0
入队：base[rear] = x; rear++;
出队：x = base[front]; front++;
空队标志：front == rear
上面的假设存在什么问题呢？有下面的两种情况：
解决上溢出的方法
1、将队中元素依次向队头方向移动。
缺点：浪费时间，每移动一次，队中元素都要移动。
2、将队空间设想成一个循环的表，即分配给队列的m个存储单元可以循环使用，当rear为maxqsize时，若向量的开始端空着，又可以从头使用空着的空间。当front为maxqsize时，也是一样。
解决假上溢的方法——引入循环队列
base[0]接在base[MAXQSIZE-1]之后，若rear+1==M，则令rear = 0;
实现方法：利用%运算
插入元素
Q.base[Q.rear] = x; //base为动态分配的一维数组
Q.rear = (Q.rear + 1) % MAXQSIZE;删除元素
x = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;将上述方法想象成循环队列，如下图:
如果这样操作的话就会出现新的问题，就是队空和队满的时候，front = rear
那么如何解决这个问题呢，我们接下面往下分析：
解决方案：
1、另外设一个标志以区别队空、队满
2、另设一个变量，记录元素个数
3、少用一个元素空间循环队列解决队满时判断方法——少用一个元素空间：
循环队列的基本操作
-
队列的基本操作——队列的初始化
#define MAXQSIZE 100
typedef int QElemType;
Status InitQueue(SqQueue& Q) //C++中的引用操作，不是单纯的值拷贝，类似给变量取别名，还是同一块内存
{
Q.base = new QElemType[MAXQSIZE]; //分配数组空间，利用C++关键字new实现
//.base = malloc(MAXQSIZE*sizeof(QElemType)); //C语言实现
if (!Q.base)exit(OVERFLOW);
Q.front = Q.rear = 0;
return OK;
}-
队列的基本操作——求队列的长度
int QueueLength(SqQueue Q)
{
return ((Q.rear-Q.front+MQXQSIZE)%MAXQSIZE);
}-
队列的基本操作——循环队列入队
Status EnQueue(SqQueue& Q, QlemType 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 EnQueue(SqQueue& Q, QlemType &e)
{
if ((Q.rear = Q.front)return ERROR; //队空
e = Q.base[front]; //保存队头元素
Q.front = (Q.front + 1) % MAXQSIZE;//队头指针+1
return OK;
}-
队列的基本操作——取队头元素
SElemType GetHead(SqQueue Q)
{
if(Q.front!=Q.rear) //队列不为空
return Q.base[Q.front];//返回队头指针元素的值，队头指针不变
}-
队列的基本操作——取队尾元素
链队——队列的链式表示和实现
若用户无法估计所用队列的长度，则宜采用链队列
链队列的类型定义
#define MAXQSIZE 100 //最大队列长度
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));
Q.front->next = NULL;
return OK;
}-
链队列的基本操作——链队列销毁
Status DestroyQueue(LinkQueue& Q)
{
while (Q.front)
{
p = Q.front->next;//指针p指向头结点的下一结点
free(Q.front); //释放头结点
Q.front = p; //把指针指向的结点变为新的头结点
}
}-
链队列的基本操作——将元素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;
}-
链队列的基本操作——将元素e出队
思路：
p=Q.front->next; //暂存头结点的下一个，也就是第一结点
e=p->data; //将要删除的队头的数据存下来
Q.front->next=p->next; //将头结点指向第二结点
delete p; //释放要删除的元素的内存空间
代码实现：
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;
delete p;
return OK;
}-
链队列的基本操作——求链队列的队头元素
Status GetHead (LinkQueue Q QElemType &e)
{
if(Q.front==Q.rear) return ERROR;
e=Q.front->next->data;
return OK;
}