栈与队列

更新2/14/2026

字数0

时长0 分钟

栈

栈的概念

• 栈（Stack）：一种 后进先出（LIFO, Last In First Out） 的数据结构。
• 特点：
  • 只能在栈顶进行插入和删除操作。
  • 插入操作称为 压栈（push）。
  • 删除操作称为 出栈（pop）。

在 Java 中，Stack 是继承自 Vector 的一个类：

public class Stack<E> extends Vector<E>

栈的常用方法

方法	说明
push(E item)	将元素压入栈顶
pop()	移除并返回栈顶元素
peek()	返回栈顶元素但不移除
empty()	判断栈是否为空
search(Object o)	返回对象到栈顶的距离（1-based），未找到返回 -1
size()	查看元素个数

基本使用示例

import java.util.Stack;

public class StackDemo {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // 压栈
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("栈内容: " + stack); // [10, 20, 30]

        // 查看栈顶元素
        System.out.println("栈顶元素: " + stack.peek()); // 30

        // 出栈
        int popped = stack.pop();
        System.out.println("出栈元素: " + popped); // 30
        System.out.println("出栈后: " + stack);   // [10, 20]

        // 判断是否为空
        System.out.println("栈是否为空: " + stack.empty()); // false

        // 搜索元素位置
        System.out.println("元素 10 的位置: " + stack.search(10)); // 2
    }
}

栈的常见应用场景

1. 括号匹配（表达式校验）
2. 表达式求值（后缀表达式、中缀转后缀）
3. 函数调用栈（递归调用）
4. 浏览器前进后退（页面历史记录）
5. 深度优先搜索（DFS）

使用 Deque 替代 Stack

官方建议使用 Deque（如 ArrayDeque）代替 Stack，因为 Stack 基于 Vector，线程安全但效率较低。

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeStackDemo {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();

        // 压栈
        stack.push(10);
        stack.push(20);
        stack.push(30);

        // 出栈
        System.out.println(stack.pop());  // 30
        System.out.println(stack.peek()); // 20
    }
}

栈应用示例

括号匹配（Balanced Parentheses） 的经典栈应用示例。

经典应用示例：括号匹配

括号匹配问题是栈的典型应用场景之一。  
给定一个字符串，判断其中的括号是否成对、顺序是否正确。  
支持 `()`, `{}`, `[]` 三种括号。

### 示例代码
import java.util.Stack;

public class BracketMatcher {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (char ch : s.toCharArray()) {
            // 左括号入栈
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                // 如果遇到右括号，栈为空 -> 不匹配
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if ((ch == ')' && top != '(') ||
                    (ch == '}' && top != '{') ||
                    (ch == ']' && top != '[')) {
                    return false;
                }
            }
        }

        // 遍历结束后，栈为空才说明完全匹配
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isValid("()"));       // true
        System.out.println(isValid("({[]})"));   // true
        System.out.println(isValid("([)]"));     // false
        System.out.println(isValid("{[("));      // false
    }
}

队列

队列的概念

• 队列（Queue）：一种 先进先出（FIFO, First In First Out） 的数据结构。
• 特点：
  • 元素只能从队尾插入（enqueue，入队）。
  • 元素只能从队头移除（dequeue，出队）。

在 Java 中，Queue 是一个接口：

public interface Queue<E> extends Collection<E>

常见实现类：

• LinkedList
• PriorityQueue
• ArrayDeque

队列的常用方法

方法	说明	抛异常方式	返回特殊值方式
add(E e)	入队（队尾）	队满时抛 IllegalStateException
offer(E e)	入队（队尾）		队满时返回 false
remove()	出队（队头）	队空时抛 NoSuchElementException
poll()	出队（队头）		队空时返回 null
element()	查看队头元素（不移除）	队空时抛 NoSuchElementException
peek()	查看队头元素（不移除）		队空时返回 null
isEmpty()	判断队列是否为空		队空时返回 true
size()	查看元素个数		返回元素个数

基本使用示例

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

public class QueueDemo {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        // 入队
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);
        System.out.println("队列内容: " + queue); // [10, 20, 30]

        // 查看队头元素
        System.out.println("队头元素: " + queue.peek()); // 10

        // 出队
        int first = queue.poll();
        System.out.println("出队元素: " + first); // 10
        System.out.println("出队后: " + queue);  // [20, 30]

        // 再次查看队头
        System.out.println("队头元素: " + queue.element()); // 20
    }
}

双向队列

Deque（Double Ended Queue）：双端队列，可以在队头和队尾进行插入和删除。

常见实现：ArrayDeque。

常用方法：

• offerFirst(E e), offerLast(E e)
• pollFirst(), pollLast()
• peekFirst(), peekLast()

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeDemo {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();

        // 1. 当作栈使用（LIFO）
        System.out.println("===== 当作栈使用 =====");
        deque.push(1); // 入栈
        deque.push(2);
        deque.push(3);
        System.out.println(deque.pop()); // 出栈：3（后进先出）
        System.out.println(deque.peek()); // 查看栈顶：2

        // 清空后，当作队列使用
        deque.clear();
        
        // 2. 当作队列使用（FIFO）
        System.out.println("===== 当作队列使用 =====");
        deque.offer(1); // 入队
        deque.offer(2);
        deque.offer(3);
        System.out.println(deque.poll()); // 出队：1（先进先出）
        System.out.println(deque.peek()); // 查看队首：2
    }
}

用途	核心方法	说明
当作栈	push() / pop() / peek()	遵循后进先出（LIFO） 规则
当作队列	offer() / poll() / peek()	遵循先进先出（FIFO） 规则