数据结构——栈和队列（队列的定义、顺序队列以及链式队列的基本操作）

目录

队列（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;//队尾指针+1return OK;
}

• 队列的基本操作——循环队列出队

Status EnQueue(SqQueue& Q, QlemType &e)
{if ((Q.rear = Q.front)return ERROR;  //队空e = Q.base[front];    //保存队头元素Q.front = (Q.front + 1) % MAXQSIZE;//队头指针+1return 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;
}