数据结构重学日记（十二）队列

概念

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

队头

允许删除的一端，也称为队首。

队尾

允许插入的一端。

，，

端进行删除，为队首，端允许插入，为队尾。

队列一般遵循先入先出。
根据存储结构，分为顺序队列和链式队列。

顺序队列

队列的顺序存储结构。

可以用数组来实现队列，将队首放在数组下标为 0 的位置。但是这样会造成操作时间复杂度变大，因此也可以用指针存放队首元素位置和队尾元素位置。

实现

#define MaxSize 5
typedef int ElemType;
typedef struct {
   ElemType data[MaxSize];
   int front,rear;
}SqQueue;

当队列为空时，队首和队尾会重合，会造成操作的复杂性，所以队尾指针指向最后一个元素的下一个元素位置。

队列

由上图可以看出，随着入队出队的进行，整个队列会向后整体移动，就会出现图 b 的现象：队尾指针已经移动到了最后，即队尾出现溢出，无法再进行入队操作，但是实际上队列中还有空闲空间，这种现象称为假溢出。

为了解决这个问题一般有以下三种方法：

• 每次删除队首元素后，把整个队列向前移动一个位置，这样可以保证队首元素在存储空间的最前边，但每次删除元素都要把所有元素向前移动，效率太低。
• 当队尾指针出现溢出，判断队首指针的位置，如果前边还有空闲，则把队列整体向前移动，这种方式移动的元素次数大为减少。
• 将队列看成头尾相接的循环结构，当队尾指针移到最后时，再从队首开始向后指，这样就不需要再移动元素了。这种顺序队列被称为循环队列或环形队列。是最经济、应用最多的模式。

循环队列 队空队满

入队：rear = (rear + 1)%MaxSize
出队：front = (front + 1)%MaxSize

当队列已满时，仍然会有一个大问题，front = rear，这和对空的条件一模一样，无法区分是队空还是队满，所以这里就有了两种解决方式：

• 设置一个 flag，标记队空和队满。
• 浪费一个存储空间，当 rear 的下一个位置是 front 时，就认为是队满。

队满

队满：(rear + 1) % MaxSize == front
队列数据个数：(rear - front + MaxSize ) % MaxSize

链式队列

队列的链式存储结构，其实就是有限制的单链表，只能在表尾插入元素，表头删除元素。

队首指针指向头结点，队尾指针指向尾结点。
空队列时首位指针都指向头结点。

实现

typedef int ElemType;
typedef struct{ // 链式队列结点
    ElemType data;
    struct LinkNode * next;
}LinkNode;

typedef struct { // 链式队列
    LinkNode * front, * rear; //队首队尾指针
}LinkQueue;

插入操作和单链表的插入是一致的。

双端队列

两端都可以进行入队和出队操作的队列。

双端队列的队首队尾称为前段后端。

相关代码下一篇再贴。写完了我先跑一下再说。