1. 栈

1. 概念

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

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

2. 栈的使⽤

Stack<E> name = new Stack<>();

<E> 是一个类型参数，表示栈中存储的元素类型。

  • 必须判空：在调用 pop() 或 peek() 之前，必须使用 isEmpty() 方法检查栈是否为空。

  • 避免异常：判空可以避免 EmptyStackException，提高代码的健壮性。

  • 最佳实践：始终在操作栈之前检查栈的状态，确保程序能够正确处理边界情况。

3. 栈的底层实现

（1）数组实现

  • java.util.Stack：这是Java提供的一个栈类，其底层是基于数组实现的。它继承自Vector类，而Vector是一个动态数组。Stack 是线程安全的

  • 特点：

    • 数组实现的栈在扩容时需要复制数组，效率较低。

    • 但数组实现的栈在访问元素时速度较快，因为数组是连续存储的。

    • 出栈和入栈的时间复杂度都为O(1)

  • java.util.ArrayDeque：基于数组实现的双端队列，也可以用作栈。线程不安全

（2）链表实现

  • 自定义栈：可以使用java.util.LinkedList来实现栈

  • 1. 单链表

  • 1.1 头插和头删

    • 通过调用LinkedList的addFirst()和removeFirst()方法，可以模拟栈的push和pop操作。

    • 链表实现的栈不需要扩容，出栈和入栈的时间复杂度为O(1)。

  • 1.2 尾插和尾删

    • 通过调用LinkedList的addLast()和removeLast()方法，可以模拟栈的push和pop操作。

    • 链表实现的栈不需要扩容，入栈的时间复杂度为O(1),出栈的时间复杂度为O(n),因为需要遍历完整个链表。

  • 2. 双链表

    • 不需要扩容，不管从哪边出栈和入栈时间复杂度都为O(1)。

使用数组模拟实现栈

2. 队列

注意：Queue和Deque都是个接⼝，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue和Deque接⼝。

1 概念

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

2.  队列的使用

import java.util.Queue;
import java.util.LinkedList;

Queue<E> queue1 = new LinkedList<>();//基于双链表实现


import java.util.Queue;
import java.util.ArrayDeque;

Queue<E> queue2 = new ArrayDeque<>();//基于动态数组实现

操作类型 方法 功能 队列为空/满时的行为 中文解释
插入 add(E e) 添加元素到队列尾部 队列已满时抛出异常 强制添加，可能抛异常
插入 offer(E e) 添加元素到队列尾部 队列已满时返回 false 安全添加，不抛异常
移除 remove() 移除并返回队头元素 队列为空时抛出异常 强制移除，可能抛异常
移除 poll() 移除并返回队头元素 队列为空时返回 null 安全移除，不抛异常
检查 element() 返回队头元素（不移除） 队列为空时抛出异常 强制获取，可能抛异常
检查 peek() 返回队头元素（不移除） 队列为空时返回 null 安全获取，不抛异常

队列的模拟实现（基于双链表）

3. 循环队列

环形队列通常使⽤数组实现

1. 数组下标循环的小技巧

通过取模运算 ( %)，可以确保数组下标在超出数组长度时循环回到起始位置，从而实现  循环访问。
1. 假设有一个长度为  array.length 的数组，当前下标为  index，需要向后移动  offset 个位置。由于数组是循环的，当  index + offset 超出数组长度时，通过取模运算将其映射回数组的有效范围内。
 index = (index + offset) % array.length
2. 假设有一个长度为  array.length 的数组，当前下标为  index，需要向前移动  offset 个位置。由于数组是循环的，当  index - offset 小于 0 时，通过取模运算将其映射回数组的有效范围内。
 index = (index + array.length - offset) % array.length

2. 如何区分空与满

1. 通过添加 size 属性记录

  1. 初始状态：

    • front 和 rear 都指向 0。

    • size 初始化为 0。

  2. 队列空：

    • size == 0。

  3. 队列满：

    • size == capacity。

  4. 入队操作：

    • 检查队列是否已满。

    • 如果未满，将元素放入 rear 位置，并移动 rear 指针。

    • 增加 size。

  5. 出队操作：

    • 检查队列是否为空。

    • 如果不为空，取出 front 位置的元素，并移动 front 指针。

    • 减少 size。

2. 使⽤标记

  • 初始状态：

    • front 和 rear 都指向 0。

    • isFull 设置为 false，表示队列为空。

  • 入队操作：

    • 检查 rear 是否与 front 重合：

      • 如果重合且 isFull 为 true，表示队列已满，无法入队。

      • 如果重合但 isFull 为 false，表示队列为空，可以入队。

    • 如果 rear 与 front 不重合，正常入队并移动 rear。

    • 如果 rear 移动后与 front 重合，设置 isFull = true。

  • 出队操作：

    • 移动 front 指针。

    • 设置 isFull = false（因为出队后队列不可能满）。

  • 判断队列空和满：

    • 队列空：front == rear 且 isFull == false。

    • 队列满：front == rear 且 isFull == true。

3. 保留⼀个位置

  1. 初始状态：

    • front 和 rear 都指向 0。

    • 队列中保留一个空位，因此实际可用容量为 capacity - 1。

  2. 队列空：

    • front == rear。

  3. 队列满：

    • (rear + 1) % capacity == front。

  4. 入队操作：

    • 检查队列是否已满。

    • 如果未满，将元素放入 rear 位置，并移动 rear 指针。

  5. 出队操作：

    • 检查队列是否为空。

    • 如果不为空，取出 front 位置的元素，并移动 front 指针。

3. 代码示例

622. 设计循环队列 - 力扣（LeetCode）

4. 双端队列

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

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

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

例题分析

1. 栈

什么是波兰表达式？

2. 队列

# 数据结构 # java
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

‌关于人工智能（AI）的发展现状和未来趋势的详细分析！

avatar 魔乐社区
cover

【SF顺丰】顺丰开放平台API对接（注册、API测试篇）

avatar 魔乐社区
cover

数据库系统概论的第六版与第五版的区别

avatar 魔乐社区