企业官网建设流程全解析

栈和队列的基本概念

栈的基本概念

栈是一种线性数据结构，遵循**后进先出（LIFO）**原则。最后插入的元素最先被删除。栈的操作通常限制在栈顶进行。

核心操作

• Push: 将元素添加到栈顶。
• Pop: 移除并返回栈顶元素。
• Peek/Top: 返回栈顶元素但不移除。
• isEmpty: 检查栈是否为空。

应用场景

• 函数调用时的调用栈。
• 表达式求值（如括号匹配）。
• 浏览器的“后退”功能。

队列的基本概念

队列是一种线性数据结构，遵循**先进先出（FIFO）**原则。最先插入的元素最先被删除。队列的操作在队尾插入，队头删除。

核心操作

• Enqueue: 将元素添加到队尾。
• Dequeue: 移除并返回队头元素。
• Front: 返回队头元素但不移除。
• isEmpty: 检查队列是否为空。

应用场景

• 任务调度（如CPU任务队列）。
• 打印队列管理。
• 广度优先搜索（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集合框架

Stack<Integer> 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集合框架

Queue<Integer> queue = new LinkedList<>(); queue.offer(1); queue.poll(); // 双端队列 Deque<Integer> 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而非Stack（Stack为线程安全但性能较低）。
  • 队列推荐使用ArrayDeque（非阻塞场景）或ConcurrentLinkedQueue（高并发场景）

总结

栈和队列在时间复杂度上表现相近，但实现选择会影响实际性能。ArrayDeque在大多数场景下优于Stack和LinkedList，因其基于数组实现，缓存友好且扩容效率高。根据具体需求选择数据结构是关键。

Java集合框架中的实现

Java集合框架中的栈实现

Java中栈的实现通常通过Stack类或Deque接口完成。Stack类是Vector的子类，提供了标准的栈操作。

使用Stack类

Stack<Integer> stack = new Stack<>(); stack.push(1); // 压栈 int topElement = stack.pop(); // 弹栈 int peekElement = stack.peek(); // 查看栈顶元素

使用Deque接口（推荐）

Deque<Integer> stack = new ArrayDeque<>(); stack.push(1); int topElement = stack.pop(); int peekElement = stack.peek();

ArrayDeque作为栈使用时比Stack类性能更好，因为避免了同步开销。

Java集合框架中的队列实现

Java中队列的实现主要通过Queue接口及其子接口Deque完成。常见实现类包括LinkedList和ArrayDeque。

基本队列操作

Queue<Integer> queue = new LinkedList<>(); queue.offer(1); // 入队 int head = queue.poll(); // 出队 int peek = queue.peek(); // 查看队首元素

双端队列(Deque)

Deque<Integer> deque = new ArrayDeque<>(); deque.offerFirst(1); // 前端入队 deque.offerLast(2); // 后端入队 int first = deque.pollFirst(); // 前端出队 int last = deque.pollLast(); // 后端出队

优先队列(PriorityQueue)

Queue<Integer> 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后通过循环移动元素将新元素置于队首，保证后进先出。

二叉树的层序遍历使用队列实现广度优先搜索。将根节点入队，每次处理队首元素并将其子节点入队。

柱状图中最大矩形给定非负整数数组表示柱状图高度，找出能勾勒出的最大矩形面积。使用单调栈维护递增序列快速计算面积。

每日温度给定温度列表，返回需要等待多少天才能遇到更高温度。使用单调栈存储温度索引，遇到更高温度时弹出并计算天数差。