Java—栈与队列

本篇来讲解栈与队列~

模块一：栈（Stack）

1. 基础知识

栈是一种后进先出（LIFO）的数据结构，只允许在一端（称为栈顶）进行插入和删除操作。核心操作包括：

• 压栈（Push）：向栈顶添加元素。
• 弹栈（Pop）：从栈顶移除元素。
• 查看栈顶（Peek）：获取栈顶元素但不移除。
• 判空（isEmpty）：检查栈是否为空。
• 容量（Size）：获取栈中元素数量。

2. 数组实现栈

使用数组实现栈时，需维护一个指向栈顶的指针（通常用top表示）。数组大小固定，需处理栈满的情况。

代码实现：

public class ArrayStack { private int maxSize; // 栈的最大容量 private int[] stack; // 存储元素的数组 private int top; // 栈顶指针（初始为-1） public ArrayStack(int size) { maxSize = size; stack = new int[maxSize]; top = -1; } // 压栈 public void push(int value) { if (isFull()) { throw new RuntimeException("栈已满！"); } stack[++top] = value; } // 弹栈 public int pop() { if (isEmpty()) { throw new RuntimeException("栈为空！"); } return stack[top--]; } // 查看栈顶 public int peek() { if (isEmpty()) { throw new RuntimeException("栈为空！"); } return stack[top]; } // 判空 public boolean isEmpty() { return top == -1; } // 判满 public boolean isFull() { return top == maxSize - 1; } // 获取栈中元素数量 public int size() { return top + 1; } }

3. 双链表实现栈

双链表（双向链表）每个节点包含前驱和后继指针，实现栈时可灵活地在头部插入和删除节点（时间复杂度为O(1)）。

代码实现：

public class LinkedListStack { private static class Node { int value; Node prev; Node next; Node(int value) { this.value = value; } } private Node top; // 栈顶节点 private int size; // 栈中元素数量 public LinkedListStack() { top = null; size = 0; } // 压栈（在链表头部插入） public void push(int value) { Node newNode = new Node(value); if (top != null) { newNode.next = top; top.prev = newNode; } top = newNode; size++; } // 弹栈（移除链表头部节点） public int pop() { if (isEmpty()) { throw new RuntimeException("栈为空！"); } int value = top.value; top = top.next; if (top != null) { top.prev = null; } size--; return value; } // 查看栈顶 public int peek() { if (isEmpty()) { throw new RuntimeException("栈为空！"); } return top.value; } // 判空 public boolean isEmpty() { return size == 0; } // 获取栈中元素数量 public int size() { return size; } }

模块二：队列（Queue）

1. 基础知识

队列是一种先进先出（FIFO）的数据结构，元素从一端（队尾）插入，从另一端（队首）删除。核心操作包括：

• 入队（Enqueue）：向队尾添加元素。
• 出队（Dequeue）：从队首移除元素。
• 查看队首（Peek）：获取队首元素但不移除。
• 判空（isEmpty）：检查队列是否为空。
• 容量（Size）：获取队列中元素数量。

队列的典型应用场景包括任务调度（如线程池）、消息队列、广度优先搜索（BFS）等。

2. 数组实现队列（循环队列）

数组实现队列时，需解决假溢出问题（即数组前部有空间但尾部已满）。通过循环数组（head和tail指针循环移动）可高效利用空间。

代码实现：

public class CircularQueue { private int maxSize; // 队列最大容量 private int[] queue; // 存储元素的数组 private int head; // 队首指针（指向待出队元素） private int tail; // 队尾指针（指向待插入位置） public CircularQueue(int size) { maxSize = size + 1; // 预留一个空位以区分队满和队空 queue = new int[maxSize]; head = 0; tail = 0; } // 入队 public void enqueue(int value) { if (isFull()) { throw new RuntimeException("队列已满！"); } queue[tail] = value; tail = (tail + 1) % maxSize; // 循环移动 } // 出队 public int dequeue() { if (isEmpty()) { throw new RuntimeException("队列为空！"); } int value = queue[head]; head = (head + 1) % maxSize; // 循环移动 return value; } // 查看队首 public int peek() { if (isEmpty()) { throw new RuntimeException("队列为空！"); } return queue[head]; } // 判空：head == tail public boolean isEmpty() { return head == tail; } // 判满：(tail + 1) % maxSize == head public boolean isFull() { return (tail + 1) % maxSize == head; } // 获取队列中元素数量 public int size() { return (tail - head + maxSize) % maxSize; } }

3. 双链表实现队列

双链表实现队列时，在链表尾部插入节点（入队），在头部删除节点（出队），时间复杂度均为O(1)。

代码实现：

public class LinkedListQueue { private static class Node { int value; Node prev; Node next; Node(int value) { this.value = value; } } private Node head; // 队首节点 private Node tail; // 队尾节点 private int size; // 队列中元素数量 public LinkedListQueue() { head = null; tail = null; size = 0; } // 入队（在链表尾部插入） public void enqueue(int value) { Node newNode = new Node(value); if (tail == null) { head = newNode; tail = newNode; } else { tail.next = newNode; newNode.prev = tail; tail = newNode; } size++; } // 出队（移除链表头部节点） public int dequeue() { if (isEmpty()) { throw new RuntimeException("队列为空！"); } int value = head.value; head = head.next; if (head != null) { head.prev = null; } else { tail = null; // 队列已空 } size--; return value; } // 查看队首 public int peek() { if (isEmpty()) { throw new RuntimeException("队列为空！"); } return head.value; } // 判空 public boolean isEmpty() { return size == 0; } // 获取队列中元素数量 public int size() { return size; } }

总结对比

• 栈：优先使用java.util.Stack或java.util.Deque（如ArrayDeque）。
• 队列：优先使用java.util.Queue的实现类（如LinkedList、ArrayDeque）。
• 不过都可以使用LinkedList。