栈与队列：数据结构核心解析

栈和队列的基本概念栈的基本概念栈是一种线性数据结构遵循**后进先出LIFO**原则。最后插入的元素最先被删除。栈的操作通常限制在栈顶进行。核心操作Push: 将元素添加到栈顶。Pop: 移除并返回栈顶元素。Peek/Top: 返回栈顶元素但不移除。isEmpty: 检查栈是否为空。应用场景函数调用时的调用栈。表达式求值如括号匹配。浏览器的“后退”功能。队列的基本概念队列是一种线性数据结构遵循**先进先出FIFO**原则。最先插入的元素最先被删除。队列的操作在队尾插入队头删除。核心操作Enqueue: 将元素添加到队尾。Dequeue: 移除并返回队头元素。Front: 返回队头元素但不移除。isEmpty: 检查队列是否为空。应用场景任务调度如CPU任务队列。打印队列管理。广度优先搜索BFS算法。栈与队列的区别特性栈队列操作原则LIFO后进先出FIFO先进先出插入/删除端同一端栈顶两端队尾插入队头删除典型应用递归、括号匹配缓冲、BFS栈和队列的实现方式栈的实现方式栈是一种后进先出LIFO的数据结构Java中可以通过以下方式实现基于数组实现public class ArrayStack { private int maxSize; private int[] stack; private int top -1; public ArrayStack(int size) { maxSize size; stack new int[maxSize]; } public boolean isFull() { return top maxSize - 1; } public boolean isEmpty() { return top -1; } public void push(int value) { if (isFull()) throw new RuntimeException(Stack is full); stack[top] value; } public int pop() { if (isEmpty()) throw new RuntimeException(Stack is empty); return stack[top--]; } public int peek() { if (isEmpty()) throw new RuntimeException(Stack is empty); return stack[top]; } }基于链表实现public class LinkedStack { private static class Node { int data; Node next; Node(int data) { this.data data; } } private Node top; public void push(int data) { Node newNode new Node(data); newNode.next top; top newNode; } public int pop() { if (isEmpty()) throw new RuntimeException(Stack is empty); int data top.data; top top.next; return data; } public boolean isEmpty() { return top null; } public int peek() { if (isEmpty()) throw new RuntimeException(Stack is empty); return top.data; } }使用Java集合框架StackInteger stack new Stack(); stack.push(1); stack.pop();队列的实现方式队列是一种先进先出FIFO的数据结构Java中可以通过以下方式实现基于数组实现public class ArrayQueue { private int maxSize; private int[] queue; private int front; private int rear; private int size; public ArrayQueue(int size) { maxSize size; queue new int[maxSize]; front 0; rear -1; size 0; } public boolean isFull() { return size maxSize; } public boolean isEmpty() { return size 0; } public void enqueue(int item) { if (isFull()) throw new RuntimeException(Queue is full); rear (rear 1) % maxSize; queue[rear] item; size; } public int dequeue() { if (isEmpty()) throw new RuntimeException(Queue is empty); int item queue[front]; front (front 1) % maxSize; size--; return item; } public int peek() { if (isEmpty()) throw new RuntimeException(Queue is empty); return queue[front]; } }基于链表实现public class LinkedQueue { private static class Node { int data; Node next; Node(int data) { this.data data; } } private Node front; private Node rear; public void enqueue(int data) { Node newNode new Node(data); if (rear ! null) { rear.next newNode; } rear newNode; if (front null) { front rear; } } public int dequeue() { if (isEmpty()) throw new RuntimeException(Queue is empty); int data front.data; front front.next; if (front null) { rear null; } return data; } public boolean isEmpty() { return front null; } public int peek() { if (isEmpty()) throw new RuntimeException(Queue is empty); return front.data; } }使用Java集合框架QueueInteger queue new LinkedList(); queue.offer(1); queue.poll(); // 双端队列 DequeInteger deque new ArrayDeque(); deque.offerFirst(1); deque.offerLast(2); deque.pollFirst(); deque.pollLast();注意事项数组实现的栈和队列需要考虑容量限制链表实现则不需要。Java集合框架中的Stack类继承自Vector是线程安全的但性能较差通常建议使用Deque接口的实现类如ArrayDeque来替代栈。队列接口Queue的主要实现类有LinkedList和ArrayDeque前者基于链表后者基于可扩展数组。应用场景分析栈的应用场景函数调用栈Java虚拟机使用栈结构管理方法调用每次方法调用时压入栈帧方法返回时弹出栈帧。表达式求值编译器利用栈处理运算符优先级将中缀表达式转换为后缀表达式后进行计算。括号匹配检查代码中的括号是否成对出现遇到左括号压栈遇到右括号弹栈匹配。浏览器后退功能浏览器历史记录使用栈实现后退操作相当于弹出最近访问的URL。撤销操作文本编辑器通过栈保存操作记录撤销时从栈顶取出最近的操作进行回退。队列的应用场景线程池任务调度Java线程池使用阻塞队列管理待执行任务保证任务按提交顺序执行。消息队列分布式系统中使用队列实现异步通信如RabbitMQ、Kafka等消息中间件。BFS算法广度优先搜索需要队列保存待访问节点确保按层次遍历图结构。打印任务管理打印机使用队列缓存多个打印请求按照先进先出原则处理。生产者-消费者模式通过阻塞队列协调生产者和消费者的速度差异如ArrayBlockingQueue。双端队列的特殊应用滑动窗口最大值使用Deque维护窗口内元素的单调递减序列快速获取最大值。工作窃取算法ForkJoinPool使用双端队列实现任务窃取提高并行计算效率。LRU缓存实现LinkedHashMap通过维护访问顺序的双端队列实现最近最少使用策略。性能比较时间复杂度分析栈的操作性能压栈push时间复杂度为 O(1)。弹栈pop时间复杂度为 O(1)。查看栈顶peek时间复杂度为 O(1)。队列的操作性能入队offer/add时间复杂度为 O(1)。出队poll/remove时间复杂度为 O(1)。查看队头peek/element时间复杂度为 O(1)。空间复杂度分析栈和队列空间复杂度均为 O(n)n 为元素数量。动态扩容ArrayDeque和Stack在容量不足时需要扩容均摊时间复杂度为 O(1)。适用场景栈适合需要后进先出的场景如函数调用栈、表达式求值、括号匹配等。队列适合需要先进先出的场景如任务调度、广度优先搜索BFS等。性能优化建议避免频繁扩容初始化时指定容量以减少动态扩容开销。选择合适实现栈推荐使用ArrayDeque而非StackStack为线程安全但性能较低。队列推荐使用ArrayDeque非阻塞场景或ConcurrentLinkedQueue高并发场景总结栈和队列在时间复杂度上表现相近但实现选择会影响实际性能。ArrayDeque在大多数场景下优于Stack和LinkedList因其基于数组实现缓存友好且扩容效率高。根据具体需求选择数据结构是关键。Java集合框架中的实现Java集合框架中的栈实现Java中栈的实现通常通过Stack类或Deque接口完成。Stack类是Vector的子类提供了标准的栈操作。使用Stack类StackInteger stack new Stack(); stack.push(1); // 压栈 int topElement stack.pop(); // 弹栈 int peekElement stack.peek(); // 查看栈顶元素使用Deque接口推荐DequeInteger stack new ArrayDeque(); stack.push(1); int topElement stack.pop(); int peekElement stack.peek();ArrayDeque作为栈使用时比Stack类性能更好因为避免了同步开销。Java集合框架中的队列实现Java中队列的实现主要通过Queue接口及其子接口Deque完成。常见实现类包括LinkedList和ArrayDeque。基本队列操作QueueInteger queue new LinkedList(); queue.offer(1); // 入队 int head queue.poll(); // 出队 int peek queue.peek(); // 查看队首元素双端队列(Deque)DequeInteger deque new ArrayDeque(); deque.offerFirst(1); // 前端入队 deque.offerLast(2); // 后端入队 int first deque.pollFirst(); // 前端出队 int last deque.pollLast(); // 后端出队优先队列(PriorityQueue)QueueInteger priorityQueue new PriorityQueue(); priorityQueue.offer(3); priorityQueue.offer(1); priorityQueue.offer(2); // 元素将按自然顺序出队1, 2, 3栈和队列的选择建议需要栈结构时优先使用Deque接口的实现类而非Stack类因为Stack继承自Vector存在性能问题。队列操作根据需求选择普通队列LinkedList或ArrayDeque优先级队列PriorityQueue线程安全队列LinkedBlockingQueue或ArrayBlockingQueue双端操作ArrayDeque所有实现类都位于java.util包中使用时无需额外依赖。Java中栈和队列常见面试问题栈相关问题实现栈的基本操作使用数组或链表实现栈的push、pop、peek操作。数组实现需考虑扩容问题链表实现注意头插法。最小栈问题设计一个栈支持push、pop、top操作并能以常数时间检索栈内最小元素。通常使用辅助栈同步存储最小值。有效的括号给定一个只包含括号的字符串判断括号是否有效匹配。使用栈遇到左括号入栈右括号时检查栈顶是否匹配。逆波兰表达式求值根据逆波兰表示法后缀表达式求值。遇到数字入栈遇到运算符弹出栈顶两个元素计算后结果入栈。队列相关问题实现队列的基本操作使用数组或链表实现队列的enqueue、dequeue操作。数组实现需处理循环队列避免假溢出。用栈实现队列使用两个栈模拟队列操作。一个栈负责入队另一个栈负责出队出队时若第二个栈为空则将第一个栈元素全部转移。滑动窗口最大值给定数组和滑动窗口大小找出所有窗口中的最大值。使用双端队列维护可能成为最大值的元素索引。循环队列设计设计循环队列支持队首队尾指针循环移动避免数据搬迁。关键点在于判断队列空和满的条件。栈和队列混合问题用队列实现栈使用单个队列模拟栈操作。每次push后通过循环移动元素将新元素置于队首保证后进先出。二叉树的层序遍历使用队列实现广度优先搜索。将根节点入队每次处理队首元素并将其子节点入队。柱状图中最大矩形给定非负整数数组表示柱状图高度找出能勾勒出的最大矩形面积。使用单调栈维护递增序列快速计算面积。每日温度给定温度列表返回需要等待多少天才能遇到更高温度。使用单调栈存储温度索引遇到更高温度时弹出并计算天数差。