引入

介绍完栈的各种定义，今天我们来介绍一下队列。我们常常会把栈和队列放在一起讲，因为它们有相似的地方，也有所不同，我们今天来看看什么是队列，以及如何初始化一个队列。

栈和队列

队列嘛，我们就可以想象成排队

  • 先来的排在前面，后来的排在后面
  • 不能插队，因为要讲究先来后到
  • 所以先来的先出队，后来的排在队尾

理解了上面的例子，要理解栈和队列，那就简单了

  • **栈：**后进先出，只能在顶端进行插入和删除，也就是压栈和出栈
  • **队列：**先进先出，队列只能在尾部出，头部入队。

队列

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

  • **与栈相反：**队列是先进先出（First In First Out），简称为FIFO 的线性表。
  • **与栈相同：**队列也是一种重要的线性结构，实现一个队列同样需要顺序表或链表作为基础。

最常见的队列就是我们计算机的输入缓冲区

  • 先按下的按键排在前面，ABCDE
  • 然后出个输出，ABCDE
  • 如果是栈输出，那就成了 EDCBA 了

队列的存储结构

队列即可以用链式存储结构也可以用顺序存储结构来实现。

  • 栈：我们经常用顺序存储结构，而少用链式存储结构
  • 队列：我们经常用链式存储结构，而少用顺序存结构，我们也称之为链队列。

队列的链式存储结构

//构建一个数据结点的结构体，用于存储数据，和下一个结点指针
struct Queue{
int data;
struct Queue *next;
};
//然后构建了一个头部和尾部的结构体，存储头部和尾部的信息
struct Queue_link{
struct Queue *front;
struct Queue *rear;
};

注意，我们要生明两个结构体

  • 一个适用于构成链表结点的结构体，存放数据和下一个结点指针
  • 一个是存储该队列头部和尾部的结构体，我们才能知道从哪里插入和从哪里出来

正常情况下：

  • **队头指针：**指向队列的头结点。
  • **队尾指针：**指向队列的终端结点。
  • 注：头结点并不是必须的

队列为空时：

  • **队头指针：**指向队列的头结点。
  • **队尾指针：**指向队列的头结点。

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。