数据结构 - 4（栈和队列6000字详解）

一：栈

1.1 栈的概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

• 压栈（push）：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
• 出栈（pop）：栈的删除操作叫做出栈。出数据在栈顶。

栈这种结构在现实生活中也很常见：

1.2 栈的使用

方法	功能
Stack()	构造一个空的栈
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

下面是这些方法的使用示例：

public static void main(String[] args) {Stack<Integer> s = new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size());  // 获取栈中有效元素个数---> 4System.out.println(s.peek());  // 获取栈顶元素---> 4s.pop();  // 4出栈，栈中剩余1  2  3，栈顶元素为3System.out.println(s.pop());  // 3出栈，栈中剩余1 2  栈顶元素为3if(s.empty()){System.out.println("栈空");}else{System.out.println(s.size());}}

1.3栈的模拟实现

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。

public class MyStack {int[] array;  // 数组用于存储栈元素int size; // 记录栈中元素的个数// 构造方法，创建一个初始容量为3的数组作为栈的存储空间public MyStack(){array = new int[3];}// 入栈操作，将元素 e 加入到栈顶，并返回入栈的元素public int push(int e){ensureCapacity();// 确保栈的容量足够array[size++] = e;// 将元素 e 加入到数组中，更新 size 的值return e;// 返回入栈的元素}// 出栈操作，将栈顶元素移出并返回该元素public int pop(){int e = peek(); // 调用 peek 方法获取栈顶元素，并记录在变量 e 中size--; // 栈中元素个数减少1return e;// 返回出栈的元素}// 返回栈顶元素的值，但不删除栈顶元素public int peek(){if(empty()){ // 如果栈为空，则抛出异常throw new RuntimeException("栈为空，无法获取栈顶元素");}return array[size-1];// 返回栈顶元素的值}// 返回栈中元素的个数public int size(){return size;}// 判断栈是否为空public boolean empty(){return 0 == size;}// 确保栈的容量足够，如果栈已满，则将栈的容量扩大为原来的2倍private void ensureCapacity(){if(size == array.length){array = Arrays.copyOf(array, size*2);}}
}

二：队列

2.1 队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

2.2 队列的使用

在Java中，Queue是个接口，底层是通过链表实现的。

下面是队列中常用的方法：

方法	功能
boolean offer(E e)	入队列
E poll()	出队列
peek()	获取队头元素
int size()	获取队列中有效元素个数
boolean isEmpty()	检测队列是否为空

注意：

• Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

下面是这些方法的使用示例：

public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();// 从队尾入队列q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5);         System.out.println(q.size());// 获取队头元素System.out.println(q.peek()); q.poll();System.out.println(q.poll());  // 从队头出队列，并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}
}

2.3队列的模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构 和 链式结构。所以队列的实现也可以采用这两种方式，但是具体采用哪种实现方式取决于具体的需求和场景。

1. 顺序结构：使用数组或列表等连续的内存空间来存储队列元素。顺序结构实现队列的优点是简单、易于理解和实现，并且访问元素的时间复杂度为 O(1)。缺点是在插入和删除操作时可能需要进行元素的搬移，这会造成时间复杂度为 O(n)。

2. 链式结构：使用链表的形式来存储队列元素。链式结构实现队列的优点是插入和删除操作的时间复杂度为 O(1)，无需进行元素的搬移。缺点是需要额外的指针来维护节点之间的连接，且节点的分配和释放可能会引起额外的内存开销和碎片问题。

所以说如果你以访问为主，那么采用顺序结构，如果你以插入和删除为主，那么采用链式结构

2.3.1顺序结构实现队列

因为我以及在代码中通过注释进行了详细的解答，在此就不过多赘述了。

public class Queue {private int capacity;           // 队列的容量private int[] elements;         // 存储队列元素的数组private int front;              // 队列的头指针private int rear;               // 队列的尾指针private int size;               // 队列的当前大小// 队列的构造方法public Queue(int capacity) {this.capacity = capacity;this.elements = new int[capacity];this.front = 0;this.rear = -1;this.size = 0;}// 入队列---向队尾插入新元素public void offer(int element) {// 检查队列是否已满if (size == capacity) {throw new IllegalStateException("Queue is full");}// 队尾指针移动到下一个位置rear = (rear + 1) % capacity;// 将新元素插入队尾elements[rear] = element;// 队列大小加1size++;}// 出队列---将队头元素删除并返回public int poll() {// 检查队列是否为空if (isEmpty()) {throw new IllegalStateException("Queue is empty");}// 获取队头元素int element = elements[front];// 队头指针移动到下一个位置front = (front + 1) % capacity;// 队列大小减1size--;// 返回队头元素return element;}// 获取队头元素---返回队头元素的值，但不删除public int peek() {// 检查队列是否为空if (isEmpty()) {throw new IllegalStateException("Queue is empty");}// 返回队头元素return elements[front];}// 返回队列的大小public int size() {return size;}// 判断队列是否为空public boolean isEmpty() {return size == 0;}
}

2.3.2链式结构实现队列

public class Queue {// 双向链表节点public static class ListNode{ListNode next;ListNode prev;int value;// 双向链表节点的构造方法ListNode(int value){this.value = value;}}ListNode first;  // 队头ListNode last;   // 队尾int size = 0;// 入队列---向双向链表尾部插入新节点public void offer(int e){ListNode newNode = new ListNode(e);if (first == null) {// 如果队列为空，新节点同时成为队头和队尾first = newNode;} else {// 如果队列不为空，将新节点插入到队尾last.next = newNode;newNode.prev = last;}// 更新队尾为新节点last = newNode;// 队列大小加1size++;}// 出队列---将双向链表第一个节点删除public int poll(){// 队列为空，返回nullif (first == null) {return null;} else if (first == last) {// 队列中只有一个元素，将队头和队尾设置为null即可last = null;first = null;} else {// 队列中有多个元素，将第一个节点删除int value = first.value;first = first.next;// 删除节点的引用关系，避免内存泄漏first.prev.next = null;first.prev = null;return value;}// 队列大小减1--size;// 返回删除的值return value;}// 获取队头元素---获取双向链表的第一个节点的值public int peek(){// 如果队列为空，返回nullif (first == null) {return null;}// 返回队头的值return first.value;}// 返回队列的大小public int size() {return size;}// 判断队列是否为空public boolean isEmpty(){return first == null;}
}

2.4 循环队列

2.4.1索引公式

循环队列的视图如下：

我们该如何去实现一个循环队列呢？答案是通过 %取模

举个例子：

int a = b % 7；

在这个例子中，我们不管b取何值，a的取值返回是不是始终在0到6之间，所以我们通过这个性质就可以很好的把队列的首和尾建立关联，即尾向后走一步就到了头，因此我们就可以很好的去实现一个循环队列了

在循环队列中，(index + offset) % array.length 和 (index + array.length - offset) % array.length 是我们常用的索引计算方式。其中：

• index 是当前元素的索引。
• offset 是偏移量，它决定了要添加/访问的元素在当前索引的基础上偏移了多少个位置。
• array.length 是数组的长度，它表示整个循环队列的大小。

下面我们对这两个公式进行解释：

1. (index + offset) % array.length：
   • 当我们需要向循环队列的下一个位置插入元素时，我们使用这种索引计算方式。
   • 假设队列在索引5处结束，我们需要向后移动1个位置，即在索引7处插入元素。使用 (5 + 1) % 8，得到的值是6，即有效的索引。

2. (index + array.length - offset) % array.length：
   • 当我们需要从循环队列的上一个位置移除元素时，我们使用这种索引计算方式。
   • 假设队列在索引2处结束，我们需要向前移动1个位置，即从索引1处移除元素。使用 (2 + 8 - 1) % 8，得到的值是1，即有效的索引。

这两种计算方式都确保了索引在循环队列中的有效范围内，因为它们会通过取模运算将索引限制在数组长度范围内。这样，我们可以在循环队列中正确地插入和移除元素。

2.4.2 队列区分空和满

当我们使用一个固定大小的数组作为队列的底层数据结构。在循环队列中，我们使用两个指针，一个指向队列的头部，即出队列的位置，另一个指向队列的尾部，即入队列的位置。

当队列为空时，这两个指针指向同一个位置，即头部与尾部指针相等。而当队列满时，尾部指针的下一个位置就是头部指针所在的位置。

那么我们该怎么区分队列是空还是满呢？

为了区分队列是空还是满，我们可以采用三种常用的方法：

1. 使用 size 属性记录:

通过添加一个 size 属性来记录队列中的元素数量，可以方便地判断队列是空还是满。当队列为空时，size 的值为 0，当队列满时，size 的值等于队列的容量。

2. 保留一个位置:

在循环队列的实现中，可以将一个位置始终空置不用，用于区分队列是空还是满。例如，当队列为空时，头部指针和尾部指针都指向同一个位置；当队列满时，尾部指针的下一个位置就是头部指针所在的位置。通过查看这个空置位置是否为空，可以判断队列是空还是满。

3. 使用标记:

可以在循环队列中使用一个额外的标记来区分队列是空还是满。这个标记可以是一个布尔值或者一个特殊的值，用于表示队列的状态。例如，当队列为空时，可以将标记设置为 true；当队列满时，可以将标记设置为 false。通过判断标记的值，可以确定队列的状态。

这些方法都可以用于区分队列是空还是满，具体选择哪种方法取决于个人偏好和实际需求。

2.5 Deque双端队列

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

Deque是一个接口，使用时必须创建LinkedList的对象。

在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现