一文读懂Java的栈和队列

数组是一种随机访问数据结构，其中每个元素都可以在恒定时间内直接访问。随机访问的一个典型例子是一本书——这本书的每一页都可以独立于其他页面打开。随机访问对许多算法至关重要，例如二分搜索。

链表是一种顺序访问数据结构，其中每个元素只能按特定顺序访问。顺序访问的一个典型例子是一卷纸或胶带——所有先前的材料必须展开才能获得您想要的数据。

在本说明中，我们考虑顺序数据结构的一个子案例，即所谓的受限访问数据结构 。

堆栈

堆栈是根据后进先出 (LIFO) 原则插入和移除的对象的容器。在下推堆栈中只允许两种操作：将 项目推入堆栈，并将项目弹出堆栈。堆栈是一种访问受限的数据结构 - 元素只能在堆栈顶部添加和删除。push将一个项目添加到堆栈的顶部， pop从顶部删除该项目。一个有用的比喻是想想一堆书;您可以只删除顶部的书，也可以在顶部添加新书。

堆栈是一种递归数据结构。这是一个堆栈的结构定义：

一个栈要么是空的，要么

是由一个栈顶和其余栈组成;

应用

堆栈的最简单应用是反转一个字。您将一个给定的单词压入堆栈 - 一个字母一个字母 - 然后从堆栈中弹出字母。

另一个应用是文本编辑器中的“撤消”机制;此操作是通过将所有文本更改保存在堆栈中来完成的。

执行

在标准类库中，数据类型栈是一个适配器类，这意味着栈是建立在其他数据结构之上的。堆栈的底层结构可以是数组、向量、ArrayList、链表或任何其他集合。无论底层数据结构的类型如何，堆栈都必须实现相同的功能。这是通过提供一个独特的界面来实现的：

public interface StackInterface<AnyType>
{
   public void push(AnyType e);
   public AnyType pop();
   public AnyType peek();
   public boolean isEmpty();
}

下图展示了组合实现的思想。

另一个实现要求(除了上述接口之外)是所有堆栈操作必须在恒定时间 O(1) 内运行。恒定时间意味着存在一些常数 k，这样无论堆栈大小如何，操作都需要 k 纳秒的计算时间。

基于数组的实现

在基于阵列的实现中，我们维持以下字段：一个默认大小(≥1)中，变量的阵列顶引用在堆栈的顶部元件和容量，指的数组的大小。变量 top从 -1 变为capacity - 1. 我们说当 时栈是空的，当 时top = -1栈是满的top = capacity-1。

在固定大小的堆栈抽象中，容量保持不变，因此当top达到容量时，堆栈对象会抛出异常。

在动态堆栈抽象中，当top达到容量时，我们将堆栈大小加倍。

基于链表的实现

基于链表的实现提供了最好的(从效率的角度来看)动态堆栈实现。

队列

队列是根据先进先出 (FIFO) 原则插入和删除的对象(线性集合)的容器。排队的一个很好的例子是加州大学美食广场的一排学生。在队列后面添加新的一行，而删除(或服务)发生在前面。在队列中只允许入队和出队两个操作 。Enqueue 意味着将一个 item 插入到队列的后面，dequeue 意味着移除前面的 item。该图演示了 FIFO 访问。

堆栈和队列之间的区别在于删除。在堆栈中，我们删除最近添加的项目;在队列中，我们删除最近最少添加的项目。

执行

在标准类库中，数据类型队列是一个适配器类，这意味着队列建立在其他数据结构之上。队列的底层结构可以是数组、向量、ArrayList、LinkedList 或任何其他集合。无论底层数据结构的类型如何，队列都必须实现相同的功能。这是通过提供独特的界面来实现的。

interface QueueInterface‹AnyType>
{
   public boolean isEmpty();
   public AnyType getFront();
   public AnyType dequeue();
   public void enqueue(AnyType e);
   public void clear();
}

上述每个基本操作都必须以恒定时间 O(1) 运行。下图展示了组合实现的思路。

循环队列

给定一个默认大小 (≥ 1) 的数组 A 有两个引用back和front，最初分别设置为 -1 和 0。每次我们插入(入队)一个新项目时，我们都会增加反向索引;当我们删除(出队)一个项目时 - 我们增加了前面的索引。下图展示了经过几步后的模型：

从图中可以看出，队列在数组中从左到右在逻辑上移动。几次后退到达终点，没有空间添加新元素

但是，在前面的索引之前有一个空闲空间。我们将使用该空间来排队新项目，即下一个条目将存储在索引 0，然后是 1，直到front。这样的模型称为环绕队列或循环队列

最后，当back到达front 时，队列已满。处理满队列有两种选择：a) 抛出异常;b) 将数组大小加倍。

循环队列的实现是通过使用模运算符(表示为 %)来完成的，它是通过取除法的余数来计算的(例如，8%5 是 3)。通过使用模运算符，我们可以将队列视为一个循环数组，其中“环绕”可以模拟为“back % array_size”。除了前后索引之外，我们还维护了另一个索引：cur - 用于计算队列中元素的数量。拥有这个索引简化了实现的逻辑。