栈与队列为什么是受限线性表

学习目标

本节先从整体上理解栈和队列。

学习完成后，你需要知道：栈和队列并不是完全脱离线性表的新结构，它们本质上仍然保存一组按顺序排列的元素。不同之处在于，栈和队列限制了元素进入和离开的方式，因此形成了非常明确的处理规则。

线性表通常允许我们在多个位置进行操作。例如，可以按下标访问元素，可以在指定位置插入元素，也可以删除指定位置的元素。

栈和队列则更克制。

栈只允许在同一端进行插入和删除。这个端通常叫作栈顶。元素从栈顶进入，也从栈顶离开。

队列允许在一端插入，在另一端删除。插入的一端叫队尾，删除的一端叫队头。

因此，栈和队列可以看作是“操作受限制的线性表”。

栈遵循后进先出，也就是 Last In, First Out，常简写为 LIFO。

可以把栈想象成一摞盘子。最后放上去的盘子在最上面，因此最先被拿走。最早放进去的盘子在最下面，必须等上面的盘子都被拿走之后才能取出。

入栈顺序：A -> B -> C
出栈顺序：C -> B -> A

这种规则适合描述“最近发生的事情最先被处理”的场景。

队列遵循先进先出，也就是 First In, First Out，常简写为 FIFO。

可以把队列想象成排队买票。先来的人站在队头，会先被服务；后来的人站到队尾，需要等待前面的人离开。

入队顺序：A -> B -> C
出队顺序：A -> B -> C

这种规则适合描述“先到先处理”的场景。

初学者可能会觉得，栈和队列限制了操作位置，好像不如普通线性表灵活。但正是这些限制，让它们能够准确表达某些过程。

例如，撤销操作需要处理最近一次动作，所以适合用栈。打印任务需要先提交的任务先处理，所以适合用队列。

限制不是缺点，而是一种建模方式。它让结构的行为更加稳定，也让程序逻辑更容易推理。

栈和队列描述的是抽象行为，不限定底层必须怎么存储。

栈可以用数组实现，也可以用链表实现。队列也可以用数组、循环数组或链表实现。不同实现方式会影响扩容、空间使用和操作复杂度，但不会改变栈和队列的核心规则。

学习时要区分两层含义：

栈和队列都是受限线性表。

栈限制元素只能从同一端进入和离开，因此形成后进先出规则。队列限制元素从一端进入、另一端离开，因此形成先进先出规则。后续学习时，要先抓住它们的抽象行为，再理解不同语言和不同底层结构的实现方式。