文章/答案/技术大牛

发布

社区首页 >专栏 >数据结构与算法（七）——队列结构

数据结构与算法（七）——队列结构

拉维

发布于 2022-04-19 02:14:55

1K02

代码可运行

文章被收录于专栏：iOS小生活iOS小生活

运行总次数：2

代码可运行

今天来聊队列结构，队列的特点是先进先出：

如上图所示，在队列头部出队列，在对列尾部入队列。在队列的结构中，有四个要素：队列头、队列尾、队列长度、队列内容。

一、顺序队列的队列假溢出问题

如上图所示，front表示队头，rear表示队尾。

图（a）表示，一个空队列，此时front和rear均指向初始的0号位置；
图（b）表示，将c1、c2、c3三个元素入队，此时front指针并未移动，rear指针移动到了3号位；
图（c）表示，c1、c2俩元素相继出队，此时队尾指针rear并未移动，队首front指针移动到了2号位；
图（d）表示入队与出队同时进行的操作，c4、c5、c6相继入队，c3、c4相继出队，此时front移动到了4号位，rear指针按道理应该移动到6号位，但是我们这个队列没有6号位，所以rear指针就停留在了队列的最末端。

如上图中的（d）所示，在顺序队列中，队列的长度是在一开始就确定了的，当rear指针指向了队列的最末端、front指针指向4号位置的时候，如果此时又有一个新的元素需要加入到队列当中来，那咋办呢？没地儿存了啊。front指针之前的0号位~3号位这4个位置相当于就空出来了并且也不能被重复利用了。这就是所谓的顺序队列的假溢出问题。那么如何解决这个问题呢？我们可以采用“循环队列”的思想来解决顺序队列的假溢出问题。

如上图所示，就是一个“循环队列”，“循环队列”是在逻辑上将队列的头跟尾拼在一起，队列头指针和队列尾指针都是在这个“循环队列”中循环移动的。也就是说，队尾指针在移动到队列的最末端的时候，此时再有新元素入队的话，队尾指针就会移动到队列最开始的位置。这样的话就解决了顺序队列的假溢出问题。

需要注意的是，“循环队列”是一个思想，那么我们如何在代码中去实现“循环队列”思想呢？方法就是取余运算。比如，队列长度是length，那么队尾指针就可以通过rear%length来获取。

现在已经实现了队列空间的循环利用。我们接下来继续给队列入队和出队。

比如我们一开始那个(d)场景，其队尾指针rear就可以移动到如下的0号位置：

然后继续将c7、c8、c9、c10进行入队，如下图所示：

此时，队首指针front还停留在4号位置没有变，队尾指针rear也已经移动到了4号位置，此时该队列就处于满队的状态。可以看到，满队和空队的时候rear指针和front指针都是指向同一个位置。显然，只通过rear==front是不足以区分到底是满队还是空队的。那么如何进一步加以区分呢？答案就是留白一个占位空间，即牺牲一个存储单元。

如上图所示，红框内就是一个预留的占位空间，这样的话，rear指针指向占位空间的时候，就说明队列已满；而不是rear指针指向当前的front的时候才会队满。

需要注意的是，占位空间是一直跟随着队首指针在变化的，占位空间一直是在队首指针的前一个位置。

这样的话，当rear==front的时候就代表空队，（rear-front+max_size)%max_size==max_size - 1代表满队。

上面的这一整个流程，我们可以通过下面这张图来更为形象地解释一下：

（a）一开始处于空队的时候，front和rear都处于0号位置；
（b）紧接着a、b、c相继入队，front处于0号位置没有改变，rear移动到了3号位置；
（c）然后a出队，rear停留在了3号位置没有变，front移动到了1号位置；
（d1）然后d、e、f、g相继入队，front依旧停留在2号位置，rear也移动到了1号位置，此时队满。
（d2）我们发现，空队和满队都是rear==front，无法区分，因此我们牺牲掉了一个存储单元，这个存储单元不存储任何内容，只是作为满队的一个标识，该存储单元会随着队首指针而移动（一直是队首指针的上一个循环位置），当队尾指针rear指向该存储单元的时候，就代表满队了。

二、顺序队列

所谓顺序队列，指的就是用顺序存储的方式来实现的队列结构。

首先来看一下顺序队列的结构设计：

#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"
#include <stdbool.h>

#define Queue_Size 10 // 队列的长度

// 操作的状态
typedef enum : int {
  Success,
  Error,
} Status;

// 元素类型
typedef int ElementType;

// 顺序队列的结构
typedef struct SequentialQueue {
  int front; // 队列头指针
  int rear; // 队列尾指针
  ElementType datas[Queue_Size]; // 队列中的数据。注意，此时就已经开辟了一段连续的存储空间了。
} SequentialQueue;

我上面有提到，一个队列的结构设计需要有四个要素：队首、队尾、长度、队列内容。在这里，front和rear这两个首尾指针的取值就是下标，因此它俩包含了长度要素，所以，这里的顺序队列的结构中是包含了front、rear、datas这三个要素。

接下来看一下如何初始化一个空队列：

// 1，初始化一个空队列
Status initSequentialQueue(SequentialQueue *queue) {
  queue->front = 0;
  queue->rear = 0;
  return  Success;
}

这里只需要将rear和front这两个索引给初始化为0就可以了，不需要初始化队列的内存空间，因为在队列结构体创建的时候就已经开辟了一段连续的内存空间，不需要再次重复创建。

队列的置空代码如下：

// 2，将队列清空
Status clearSequentialQueue(SequentialQueue *queue) {
  queue->rear = queue->front = 0;
  return Success;
}

将队列置空的时候，也只需要将front和rear这两个索引置为0即可，不需要清理内存空间，因为顺序队列的内存空间是一开始创建的时候就开辟好的一段连续的内存空间，这段连续的内存空间只有在队列被销毁的时候才会清理。而我们这里是将队列清空，因此是没有必要处理内存空间的，即便是有新元素入队，那么也就覆盖原来的空间即可。

队列的判空代码如下：

// 3，队列的判空
bool isQueueEmpty(SequentialQueue queue) {
  return queue.front == queue.rear;
}

获取队列的当前长度代码如下：

// 4，队列的当前长度
int queueLength(SequentialQueue queue) {
  return (queue.rear - queue.front + Queue_Size) % Queue_Size;
}

这里所说的队列的长度，指的是队列中的有效元素的个数。

获取队头的代码如下：

// 5，队头元素
Status getQueueHead(SequentialQueue queue, ElementType *head) {
  // 队列为空，则返回Error
  if (queue.rear == queue.front) {
    return Error;
  }
  
  // 队列非空，则获取对应元素
  *head = queue.datas[queue.front];
  return Success;
}

入队代码如下：

// 6，入队
Status addElement(SequentialQueue *queue, ElementType element) {
  // 如果队满，则返回错误
  if ((queue->rear - queue->front + Queue_Size) % Queue_Size == Queue_Size - 1) {
    return Error;
  }
  
  // 如果队未满，则入队
  queue->datas[queue->rear] = element;
  queue->rear = (queue->rear + 1) % Queue_Size;
  
  return Success;
}

这里说两点。

第一点就是判断队满的条件。由于队列中是有一个辅助用的占位空间的，所以满队时的队列长度会比队列空间的长度要小1。
第二点是，队列的rear指针指向的是下一次入队的时候的位置，而不是当前队尾元素的位置，所以有新元素要入队的时候，直接给queue->datas[queue->rear]赋值即可，但是赋完值之后需要将rear向后移一位。

出队代码如下：

// 7，出队
Status removeElement(SequentialQueue *queue, ElementType *removedElement) {
  // 如果顺序栈为空，则直接返回错误
  if (queue->rear == queue->front) {
    return Error;
  }
  
  // 如果顺序栈不为空，则直接出队
  *removedElement = queue->datas[queue->front];
  queue->front = (queue->front + 1) % Queue_Size;
  return Success;
}

队列遍历打印的代码如下：

// 8，循环打印
Status printSequentialQueue(SequentialQueue queue) {
  // 队列为空
  if (queue.rear == queue.front) {
    printf("该队列为空\n");
    return Success;
  }
  
  // 队列不为空
  printf("队列信息如下:\n");
  int i = queue.front;
  while (i != queue.rear) {
    printf("%d\n", queue.datas[i]);
    i = (i + 1) % Queue_Size;
  }
  return Success;
}

三、链式队列

所谓链式队列，指的是用链式存储的方式实现一个队列结构。

我们之前在讲链表的时候，讲到通过头结点的设计可以简化链表元素增删改查的操作，可以减少一些判断逻辑。而链式队列也需要有一个头结点的设计，这个头结点的作用就类似于顺序队列中的那个预留的空白占位空间。

在链式队列中，当队列的首尾指针都指向链表的头结点的时候，说明是空队列。每一次入队，队列的尾结点都指向最新入队的节点。每一次出队，队列的首元结点就会被移除。注意，front指针永远是指向链式队列的头结点，而队列中真正的第一个元素（即队首）是front指向的头结点之后的那个首元结点。

我上面提到，队列的结构设计要考虑四个要素：队首、队尾、队列长度和队列的内容。而在现在这个链式队列中，front指针（指向头结点）和rear指针（指向尾结点）就将队列长度和队列内容给覆盖掉了。

链式队列的结构设计代码如下：

#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"
#include <stdbool.h>

// 操作的状态
typedef enum : int {
  Success,
  Error,
} Status;

// 元素类型
typedef int ElementType;

// 节点类型
typedef struct Node {
  ElementType data; // 数据域
  struct Node *next; // 指针域
} Node;

// 链式队列的结构
typedef struct {
  struct Node *front; // 指向头结点
  struct Node *rear; // 指向尾结点
} LinkedQueue;

接下来看一下队列的初始化代码：

// 1,初始化队列
Status initLinkedQueue(LinkedQueue *queue) {
  // 新建一个节点，并初始化新节点的指针域为NULL
  struct Node *headNode = malloc(sizeof(Node));
  if (!headNode) {
    return Error;
  }
  headNode->next = NULL;
  
  // 将新节点设置为链式队列的头结点
  queue->front = queue->rear = headNode;
  return Success;
}

初始化一个链式队列的时候，需要创建一个头结点，然后让front和rear都指向头结点，此时队列为空。

接下来看一下销毁队列的代码：

// 2,销毁队列
Status destroyQueue(LinkedQueue *queue) {
  // 如果队列不存在，或者队列为空，则直接销毁
  if (!queue) {
    return Error;
  }
  
  // 如果队列存在，则依次遍历销毁
  struct Node *tempNode;
  while (queue->front != queue->rear) {
    tempNode = queue->front;
    queue->front = queue->front->next;
    free(tempNode);
  }
  queue = NULL;
  return Success;
}

销毁队列的原则就是将队列中的所有节点的内存空间都释放，其他的什么都不需要关心。

清空队列的代码如下：

// 3,清空队列
Status clearLinkedQueue(LinkedQueue *queue) {
  // 如果队列不存在，则直接返回错误
  if (!queue) {
    return Error;
  }
  
  // 如果队列存在，则首尾指针指向头结点，其他的节点都销毁
  // 记录首元结点
  struct Node *trueFirstNode = queue->front->next;
  // 将尾结点指向头结点
  queue->rear = queue->front;
  // 依次销毁首元结点及其之后的所有节点
  struct Node *tempNode;
  while (trueFirstNode) {
    tempNode = trueFirstNode;
    trueFirstNode = trueFirstNode->next;
    free(tempNode);
  }
  // 将头结点的指针域置空
  queue->front->next = NULL;
  return Success;
}

需要注意的是，销毁队列和清空队列是不一样的。销毁队列是直接将所有节点销毁即可，但是清空队列需要考虚的东西要多一些。

清空队列的时候，需要保留头结点，并且将front和rear指针都指向头结点，并且需要将头结点的指针域置空；还需要将原来的首元结点以及其后面的所有节点都给销毁。

队列的判空：

// 4,队列的判空
bool isLinkedQueueEmpty(LinkedQueue queue) {
  return queue.front == queue.rear;
}

判空的逻辑很简单，就是看front和rear是否指向同一个节点。因为front指针的指向永远是头结点，而在队列中的所有元素都出队了之后，rear也会指向头结点；如果队列中还有其他元素，那么rear就不会指向头结点。

入队代码如下：

// 5,入队
/*
 入队就是将新节点插入到链表尾部
 */
Status addElement(LinkedQueue *queue, ElementType element) {
  // 如果队列不存在则报错
  if (!queue) {
    return Error;
  }
  
  // 新建一个节点，并初始化指针域为空
  struct Node* tailNode = malloc(sizeof(Node));
  if (!tailNode) {
    return Error;
  }
  tailNode->data = element;
  tailNode->next = NULL;
  
  //将新节点插入到链表尾部
  queue->rear->next = tailNode;
  queue->rear = tailNode;
  return Success;
}

入队其实就是将新建的节点放到链表的尾部。

出队代码如下：

// 6,出队
/*
 出队就是找到当前的首元结点，然后将首元结点给移除。
 有一种特殊情况需要判断，就是当前即将删除的节点是尾结点的时候，此时需要将rear指针指向头结点
 */
Status removeElement(LinkedQueue *queue, ElementType *removedElement) {
  // 队列不存在则报错
  if (!queue) {
    return Error;
  }
  
  // 空队列则报错
  if (queue->rear == queue->front) {
    return Error;
  }
  
  // 记录当前的首元结点
  struct Node *trueFirstNode = queue->front->next;
  // 将当前的首元结点改为原首元结点的下一个节点
  queue->front->next = trueFirstNode->next;
  // 记录移除的节点数据
  *removedElement = trueFirstNode->data;
  // 如果当前移除的是链式队列中的最后一个节点元素，那么移除之后队列就空了，此时还需要将rear指针指向头结点
  if (queue->rear == trueFirstNode) {
    queue->rear = queue->front;
  }
  // 释放原来的首元结点的内存
  free(trueFirstNode);
  return Success;
}

出队，实际上就是移除单向链表的首元结点，因此，出队的时候需要对队列进行判空；并且还要兼容一种特殊情况，就是当前即将删除的节点是尾结点的时候，此时需要将rear指针指向头结点。

获取队列长度的代码如下：

// 7,获取队列长度
int queueLength(LinkedQueue queue) {
  // 空队列
  if (queue.front == queue.rear) {
    return 0;
  }
  
  // 队列非空
  int length;
  struct Node *tempNode;
  for (length = 1, tempNode = queue.front->next; tempNode != queue.rear; length++, tempNode = tempNode->next);
  return length;
}

思路就是自首元结点开始遍历计数，一直到尾结点为止。

获取队列头元素以及遍历打印队列的代码如下：

// 8,获取头元素
Status getTrueFirstElement(LinkedQueue queue, ElementType *trueFirstElement) {
  // 队列为空则返回错误
  if (queue.front == queue.rear) {
    return Error;
  }
  
  // 队列非空则返回首元结点
  *trueFirstElement = queue.front->next->data;
  return Success;
}

// 9,遍历打印队列
void printLinkedQueue(LinkedQueue queue) {
  // 队列为空
  if (queue.rear == queue.front) {
    printf("该队列为空\n");
    return;
  }
  
  // 队列非空
  printf("队列信息如下：\n");
  struct Node *tempNode = queue.front->next;
  while (tempNode) {
    printf("%d\n", tempNode->data);
    tempNode = tempNode->next;
  }
}