Java数据结构入门——栈和队列
目录
一.栈（Stack）
1.1什么是栈？
栈是一种只允许在一段进行插入和删除操作的线性表。允许操作的一段称为栈顶，另一端称为栈底
核心特性：后进先出（LIFO）
类比生活中的场景：
叠盘子：后洗干净的盘子放在最上面，取用时先取最上面的
撤销操作：最后执行的操作最先被撤销。
基本操作：
压栈（push）：将元素放在栈顶
出栈（pop）：将栈顶元素移除并返回。
查看栈顶（peek）：只返回栈顶元素，不移除。
1.2Java中的Stack类
Java集合框架提供了Stack类，继承自Vector（一个线程安全的动态数组）。
注意：Stack是线程安全的（因为继承自Vector），但在单线程环境下会带来不必要的同步开销。官方文档建议使用Deque接口的实现类（如ArrayDeque）来替代Stack。
常用方法
| 方法 | 功能描述 |
| Stack() | 构造一个空栈 |
| E push(E item) |
将元素压入栈顶，返回该元素 |
| E pop() | 弹出栈顶元素并返回 |
| E peek() | 获取栈顶元素但不弹出 |
| int size() |
获取栈中元素个数 |
| boolean empty() | 判断栈是否为空 |
基本使用示例：
import java.util.Stack;
public class StackDemo {
//Stack的一些方法的使用
public static void main(String[] args) {
Stack<Integer> stack=new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
System.out.println("栈大小"+stack.size());
System.out.println("栈顶元素"+stack.peek());
//出栈
System.out.println("弹出"+stack.pop());
System.out.println("弹出"+stack.pop());
System.out.println("当前栈大小"+stack.size());
//遍历栈（从栈顶到栈底）
while (!stack.empty()){
System.out.print(stack.pop()+" ");
}
}
}
1.3栈的模拟实现（基于数组）
我们可以基于动态数组手动实现一个栈，核心就是利用数组的尾部作为栈顶。
import java.util.Arrays;
public class MyStack {
private int[] array; // 存储元素的数组
private int size; // 栈中元素个数
public MyStack() {
array = new int[3]; // 初始容量3
size = 0;
}
// 压栈
public int push(int e) {
ensureCapacity(); // 检查并扩容
array[size++] = e;
return e;
}
// 出栈
public int pop() {
if (empty()) {
throw new RuntimeException("栈为空，无法出栈");
}
int top = array[size - 1];
size--;
return top;
}
// 查看栈顶元素
public int peek() {
if (empty()) {
throw new RuntimeException("栈为空，无栈顶元素");
}
return array[size - 1];
}
// 判断栈空
public boolean empty() {
return size == 0;
}
// 获取栈大小
public int size() {
return size;
}
// 扩容：1.5倍（与ArrayList类似）
private void ensureCapacity() {
if (size == array.length) {
int newCapacity = array.length + (array.length >> 1);
array = Arrays.copyOf(array, newCapacity);
}
}
// 清空栈
public void clear() {
size = 0; // 简单重置，实际可将数组元素置null（如果存储引用类型）
}
}二.队列
2.1什么是队列？
队列是只允许在一端插入（队尾），在另一端删除（队头）的线性表。核心特性：先进先出
类别生活中的场景：
排队买票：先到的人先买到票，后来的人排在队尾。
打印机任务队列：先提交的文档先被打印。
基本操作：
入队（offer/add）：将元素插入队尾。
出队（poll/remove）：移除队头元素并返回。
查看队头（peek/element）：只返回队头元素，不移除。
2.2 Java中的Queue接口
Queue接口是Java集合框架中的一个接口，它定义了队列的基本类型。常用的实现类有：
LinkedList：基于双向链表实现，最常用。
PriorityQueue：基于堆的优先队列
ArrayQueue：基于循环数组的双端队列，也可作为普通队列使用。
常用方法
| 方法 | 功能描述 | 异常处理 |
| boolean offer(E e) | 入队 | 返回false表示失败 |
| E poll() | 出队并返回队头 | 队列为空时返回null |
| E peek() | 获取队头有元素但不删除 | 队列为空时返回null |
| boolean add(E e) | 入队 | 失败抛异常 |
| E remove() | 出队 | 队列为空抛异常 |
| E element () | 获取队头 | 队列空抛异常 |
基本使用示例：
import java.util.LinkedList;
import java.util.Queue;
public class QueueDemo {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
// 入队
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println("队列大小：" + queue.size()); // 3
System.out.println("队头元素：" + queue.peek()); // 1
// 出队
System.out.println("出队：" + queue.poll()); // 1
System.out.println("出队：" + queue.poll()); // 2
System.out.println("队列是否为空：" + queue.isEmpty()); // false
// 遍历剩余元素
while (!queue.isEmpty()) {
System.out.print(queue.poll() + " "); // 输出：3
}
}
}2.3队列的模拟实现（基于双向链表）
因为队列需要频繁在队头删除，队尾插入，使用双向链表最为合适（O(1)操作）。
public class MyQueue {
// 双向链表节点
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 void offer(int e) {
Node newNode = new Node(e);
if (head == null) {
head = tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
size++;
}
// 出队（头部删除）
public int poll() {
if (isEmpty()) {
throw new RuntimeException("队列为空，无法出队");
}
int val = head.value;
if (head == tail) {
head = tail = null;
} else {
head = head.next;
head.prev = null;
}
size--;
return val;
}
// 获取队头
public int peek() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
return head.value;
}
public int size() {
return size;
}
public boolean isEmpty() {
return head == null;
}
}2.4循环队列
为什么需要循环队列？
普通队列用数组实现时，随着元素的出队，数组头部会留下无法利用的空闲空间，造成“假溢出”。循环队列通过模运算将数组的逻辑头连接起来，实现空间的重复利用。
循环队列的核心概念：
使用数组存储元素，front指向队头，rear指向队尾的下一个位置（或指向队尾，不同实现有一点差异）
入队：rear=(rear+1)%capacity
出队：front=(front+1)%capacity
如何区分队列空和满？
在循环队列中，front==rear可能表示队列空，也可能表示队列满。常用三种方法区分：
| 方法 | 实现方式 | 优缺点 |
| 使用size变量 |
记录当前元素个数 size=capacity为满 |
简单直观 |
| 保留一个空闲位置 |
(rear+1)%capacity==front 为满，初始front==rear=0 |
浪费一个空间 |
| 使用标志位 |
设置isFull布尔值,入队时如果导致 front==rear则设为true |
需要额外维护标志 |
设计循环队列：
我们采用保留一个空闲位置的方式来实现一个容量我k的循环队列。
class MyCircularQueue {
private int[] array;
private int front;
private int rear;
private int capacity;
// 构造一个容量为 k 的循环队列
public MyCircularQueue(int k) {
capacity = k + 1; // 多分配一个位置用于判满
array = new int[capacity];
front = 0;
rear = 0;
}
// 入队
public boolean enQueue(int value) {
if (isFull()) return false;
array[rear] = value;
rear = (rear + 1) % capacity;
return true;
}
// 出队
public boolean deQueue() {
if (isEmpty()) return false;
front = (front + 1) % capacity;
return true;
}
// 获取队头元素
public int Front() {
if (isEmpty()) return -1;
return array[front];
}
// 获取队尾元素
public int Rear() {
if (isEmpty()) return -1;
// 注意：队尾元素在 rear-1 的位置，处理循环情况
return array[(rear - 1 + capacity) % capacity];
}
// 判空
public boolean isEmpty() {
return front == rear;
}
// 判满
public boolean isFull() {
return (rear + 1) % capacity == front;
}
}三.双端队列（Deque）
3.1什么是双端队列？
双端队列是允许在两端进行插入和删除操作的队列。它既可以当作栈使用，也可以当作队列使用。
3.2Java中Deque接口
Deque接口继承自Queue，提供了更丰富的两端操作方法。常用实现类：
ArrayDeque：基于循环数组实现，性能好，推荐作为栈和普通队列使用。
LinkedList：基于双向链表实现，支持任意长度的同时，也实现了List接口。
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeDemo {
public static void main(String[] args) {
// 作为栈使用（推荐替代 Stack）
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // 等价于 addFirst
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 3，后进先出
// 作为队列使用
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); // 等价于 addLast
queue.offer(2);
queue.offer(3);
System.out.println(queue.poll()); // 1，先进先出
// 双端操作
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
deque.addFirst(0);
System.out.println(deque); // [0, 1, 2]
System.out.println(deque.removeLast()); // 2
}
}3.3为什么推荐使用Deque代替Stack
| 特性 | Stack | Deque |
| 线程安全 | 是（同步锁，有开销） | 否（单线程更高性能） |
| 底层实现 | 动态数组 | 循环数组或链表 |
| 是否推荐 | 官方建议不推荐 | 推荐使用 |
| 栈操作名 | push,pop,peek | push,pop,peek同样支持 |
结论：在单线程环境下，优先使用ArrayDeque作为栈；在多线程环境下，使用ConcurrentLinkedDeque或添加同步。
四.总结与对比
4.1栈与队列对比
| 特性 | 栈（Stack） | 队列（Queue） |
| 访问规则 | 后进先出 | 先进先出 |
| 操作端 | 同一端（栈顶） | 两端（队头/队尾） |
| 常用实现 | ArrayDeque | LinkedList |
| 典型应用 | 括号匹配，逆波兰 | 任务调度，消息队列 |
4.2选型建议
| 需求 | 推荐实现 |
| 栈（单线程） | ArrayDeque |
| 栈（多线程） | Stack或Collections.synchronized |
| 普通队列 | LinkedList或ArrayDeque |
| 需要两端操作的双端队列 |
ArrayDeque性能好， LinkedList（同时需要List功能） |
| 有容量限制的循环队列 | 自定义或ArrayBlockingQueue |
| 需要优先级 | PriorityQueue |
五.结语
本章我们：
详细介绍了栈和队列的概念，使用和模拟实现
讲解了循环队列的设计要点
展示了Deque接口如何同时支持栈和队列操作
更多推荐
7
0- 0
已为社区贡献20条内容
所有评论(0)