《阿里P8甩给我这份数据结构笔记：表/栈/队列源码+图解+10大算法应用，看完跪了》

北极的代码

发布于 2026-04-22 16:50:03

1050

前言：

来源：《数据结构与算法》一书，我们来深入浅出地探讨数据结构中最基础也最重要的三种结构：表（List）、栈（Stack）和队列（Queue）。我会从定义、形象比喻、原理、到Java中的应用，逐一进行详细解释，以及底层的一些原理。

1. 表 (List)

详细解释表，通常指的是线性表。它是由同一类型的数据元素构成的有序序列。这里的“有序”指的是元素之间存在一种“一对一”的逻辑关系（即除了第一个和最后一个，每个元素都有且只有一个前驱和一个后继）。形象解释

数组（顺序表）：就像一个排好座位的电影院。每个座位都有固定的编号（索引）。你想找第20排的观众，可以直接走过去。但如果想在中间插入一个观众，你需要把后面所有人都往后挪一个位置，非常麻烦。
链表（链式表）：就像一场寻宝游戏。你手里只有第一条线索（头指针），根据线索找到第一个宝藏。第一个宝藏里藏着找到第二个宝藏的线索（指针），以此类推。如果你想在中间藏一个新宝藏，你只需要修改前后两个宝藏的线索指向即可，不需要动其他的宝藏。

原理是什么在Java中，表主要通过两个类来实现：ArrayList 和 LinkedList。

ArrayList (顺序表)
- 原理：底层是一个动态扩展的数组 Object[]。
- 特点：
  - 查询快：因为数组在内存中是连续存储的，知道索引就能直接计算出内存地址，时间复杂度为 O(1)。
  - 增删慢：在中间插入或删除元素，需要批量移动后续元素。如果数组容量不够，还需要进行更大的数组扩容和数据拷贝，时间复杂度为 O(n)。
- 应用场景：适合频繁查找、遍历，但很少进行插入和删除操作（特别是中间位置）的场景。
LinkedList (链表)
- 原理：底层是一个双向链表。每个节点（Node）包含三部分：存储的数据、指向前一个节点的引用（prev）、指向后一个节点的引用（next）。
- 特点：
  - 查询慢：要找到第n个元素，必须从头或尾开始顺着指针遍历，时间复杂度为 O(n)。
  - 增删快：在已知位置的插入或删除，只需要修改前后节点的指针指向即可，时间复杂度理论上为 O(1)（但注意，找到这个位置通常需要O(n)的时间）。
- 应用场景：适合频繁在表头或表尾进行插入和删除，或者数据量不大且增删操作远多于查询操作的场景。

Java语言的应用

java

import java.util.*;

public class ListExample {
    public static void main(String[] args) {
        // ArrayList 示例
        List<String> arrayList = new ArrayList<>();
        arrayList.add("Apple"); // 追加
        arrayList.add(0, "Banana"); // 在索引0插入
        String fruit = arrayList.get(1); // 随机访问，非常快
        System.out.println("ArrayList: " + arrayList);

        // LinkedList 示例
        List<String> linkedList = new LinkedList<>();
        linkedList.add("Apple");
        linkedList.add("Banana");
        // LinkedList 特有方法，利用其链式结构
        ((LinkedList<String>) linkedList).addFirst("Grape"); // 在头部添加，很快
        String first = ((LinkedList<String>) linkedList).getFirst();
        System.out.println("LinkedList: " + linkedList);
    }
}

2. 栈 (Stack)

详细解释栈是一种操作受限的线性表，它只允许在表的一端（称为栈顶）进行插入和删除操作。其核心特性是 后进先出（LIFO，Last In First Out）。形象解释

一摞盘子：你洗完盘子会把它摞在最上面，用的时候也是从最上面拿走一个。你总是最后放上去的盘子，最先被拿走。
浏览器的后退功能：你访问了页面A -> B -> C，浏览器会把它们依次压入栈中。当你点击后退时，C页面（栈顶）先被弹出，回到B页面。

原理是什么栈的底层实现可以是数组（顺序栈），也可以是链表（链式栈）。关键在于对操作的限制，只暴露 push（压栈）和 pop（弹栈）等方法。

压栈 (push)：将元素添加到栈顶。
弹栈 (pop)：移除并返回栈顶元素。
查看栈顶 (peek)：返回栈顶元素但不移除。

Java语言的应用

在Java中，Stack 是一个遗留类，它继承自 Vector（一个线程安全的类似ArrayList的类），性能较差。现在官方推荐使用 Deque 接口的实现类，如 ArrayDeque 来作为栈使用。

常用方法：push()， pop()， peek()。
经典应用：
- 函数调用堆栈：追踪方法的调用和返回。
- 表达式求值：编译器中用于计算数学表达式（如 1+（2+3）*4）。
- 括号匹配：检查代码中的括号（如{}， []， ()）是否正确闭合。
- 深度优先搜索（DFS）。

java

import java.util.*;

public class StackExample {
    public static void main(String[] args) {
        // 推荐使用 Deque 作为栈
        Deque<String> stack = new ArrayDeque<>();

        // 压栈
        stack.push("第一页");
        stack.push("第二页");
        stack.push("第三页");

        System.out.println("栈顶元素：" + stack.peek()); // 输出：第三页

        // 弹栈
        while (!stack.isEmpty()) {
            System.out.println("弹出：" + stack.pop());
        }
        // 输出顺序：第三页，第二页，第一页 (LIFO)
    }
}

3. 队列 (Queue)

详细解释队列也是一种操作受限的线性表，它只允许在表的一端（称为队尾）进行插入操作，在另一端（称为队头）进行删除操作。其核心特性是 先进先出（FIFO，First In First Out）。形象解释

排队买票：大家按先来后到的顺序排成一队。新来的人排在队伍后面（入队），排在队首的人买完票后离开（出队）。
打印机任务队列：多个文档同时要求打印，打印机处理不过来，就会把它们放进一个队列里，先点打印的先被打印。

原理是什么队列的底层实现也可以是数组（顺序队列）或链表（链式队列）。

入队 (offer/add)：将元素添加到队尾。
出队 (poll/remove)：移除并返回队头元素。
查看队头 (peek/element)：返回队头元素但不移除。

Java语言的应用 Java 中 Queue 是一个接口，常用的实现类有 LinkedList 和 ArrayDeque。

常用方法：
- offer() / add()：入队。在容量限制时，offer 优于 add（add 失败会抛异常）。
- poll() / remove()：出队。队列为空时，poll 返回 null，remove 抛异常。
- peek() / element()：查看队头。队列为空时，peek 返回 null，element 抛异常。
经典应用：
- 消息队列：系统解耦，异步处理。
- 线程池任务调度：等待执行的任务被放入队列。
- 广度优先搜索（BFS）：例如在迷宫中找最短路径。
- 缓存：例如 LRU（最近最少使用） 缓存算法的变种。

java

import java.util.*;

public class QueueExample {
    public static void main(String[] args) {
        // 使用 LinkedList 作为队列
        Queue<String> queue = new LinkedList<>();

        // 入队
        queue.offer("顾客1");
        queue.offer("顾客2");
        queue.offer("顾客3");

        System.out.println("队头元素：" + queue.peek()); // 输出：顾客1

        // 出队
        while (!queue.isEmpty()) {
            System.out.println("服务：" + queue.poll());
        }
        // 输出顺序：顾客1，顾客2，顾客3 (FIFO)
    }
}

总结对比

数据结构	核心原则	比喻	插入/删除端	Java中的代表实现	典型应用
表 (List)	有序集合	电影院座位 / 寻宝线索	任意位置	ArrayList， LinkedList	存储数据集合，如用户列表
栈 (Stack)	后进先出 (LIFO)	一摞盘子	同一端（栈顶）	ArrayDeque （作为栈用）	函数调用、后退、括号匹配
队列 (Queue)	先进先出 (FIFO)	排队买票	一端进（队尾），另一端出（队头）	LinkedList， ArrayDeque	任务调度、消息队列、BFS

栈的内存原理图

数组实现的顺序栈

text

内存地址：低地址 → 高地址
┌─────┬─────┬─────┬─────┬─────┐
│  A  │  B  │  C  │     │     │
└─────┴─────┴─────┴─────┴─────┘
 索引0   1     2     3     4
        ↑           ↑
      栈底         栈顶

链表实现的链式栈

text

栈顶指针 → ┌───┬───┐    ┌───┬───┐    ┌───┬───┐
          │ C │   │ → │ B │   │ → │ A │null│
          └───┴───┘    └───┴───┘    └───┴───┘
          节点3         节点2         节点1

三、栈在算法中的经典应用

1. 括号匹配检测

检查表达式中的括号是否匹配：

java

public class BracketMatcher {
    public static boolean isBalanced(String expression) {
        Deque<Character> stack = new ArrayDeque<>();
        
        for (char ch : expression.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);  // 左括号入栈
            } 
            else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty()) {
                    return false;  // 有右括号但栈空，不匹配
                }
                
                char top = stack.pop();  // 弹出栈顶左括号
                if (!isMatchingPair(top, ch)) {
                    return false;  // 括号类型不匹配
                }
            }
        }
        
        return stack.isEmpty();  // 最后栈应为空
    }
    
    private static boolean isMatchingPair(char left, char right) {
        return (left == '(' && right == ')') ||
               (left == '[' && right == ']') ||
               (left == '{' && right == '}');
    }
    
    public static void main(String[] args) {
        String expr1 = "{[()]}";  // 匹配
        String expr2 = "{[(])}";  // 不匹配
        
        System.out.println(expr1 + ": " + isBalanced(expr1));
        System.out.println(expr2 + ": " + isBalanced(expr2));
    }
}

执行过程图解（以 "{[()]}" 为例）：

text

步骤1: 遇到 '{'  → 栈: [ { ]
步骤2: 遇到 '['  → 栈: [ {, [ ]
步骤3: 遇到 '('  → 栈: [ {, [, ( ]
步骤4: 遇到 ')'  → 弹出 '('，栈: [ {, [ ]
步骤5: 遇到 ']'  → 弹出 '['，栈: [ { ]
步骤6: 遇到 '}'  → 弹出 '{'，栈: [ ]
最终: 栈为空 → 匹配成功

2. 表达式求值（中缀转后缀）

将中缀表达式 a + b * c 转换为后缀表达式 a b c * +：

java

public class InfixToPostfix {
    public static String convert(String infix) {
        StringBuilder postfix = new StringBuilder();
        Deque<Character> stack = new ArrayDeque<>();
        
        // 运算符优先级
        Map<Character, Integer> precedence = new HashMap<>();
        precedence.put('+', 1);
        precedence.put('-', 1);
        precedence.put('*', 2);
        precedence.put('/', 2);
        
        for (char ch : infix.toCharArray()) {
            if (Character.isLetterOrDigit(ch)) {
                postfix.append(ch);  // 操作数直接输出
            } 
            else if (ch == '(') {
                stack.push(ch);  // 左括号入栈
            } 
            else if (ch == ')') {
                // 弹出直到遇到左括号
                while (!stack.isEmpty() && stack.peek() != '(') {
                    postfix.append(stack.pop());
                }
                stack.pop();  // 弹出 '('
            } 
            else {  // 运算符
                while (!stack.isEmpty() && stack.peek() != '(' &&
                       precedence.getOrDefault(stack.peek(), 0) >= 
                       precedence.getOrDefault(ch, 0)) {
                    postfix.append(stack.pop());  // 弹出优先级高的运算符
                }
                stack.push(ch);  // 当前运算符入栈
            }
        }
        
        // 弹出栈中剩余运算符
        while (!stack.isEmpty()) {
            postfix.append(stack.pop());
        }
        
        return postfix.toString();
    }
}

转换过程图解（以 "a+b*c" 为例）：

text

输入: a + b * c

读取 a: 输出 a               栈: [ ]
读取 +:                       栈: [ + ]
读取 b: 输出 a b             栈: [ + ]
读取 *: 优先级高于栈顶+       栈: [ +, * ]
读取 c: 输出 a b c           栈: [ +, * ]
结束: 弹出剩余运算符           栈: [ ]
最终输出: a b c * +

3. 深度优先搜索（DFS）

使用栈实现图的深度优先遍历：

java

public class DepthFirstSearch {
    static class Graph {
        private int vertices;
        private LinkedList<Integer>[] adjList;
        
        Graph(int v) {
            vertices = v;
            adjList = new LinkedList[v];
            for (int i = 0; i < v; i++) {
                adjList[i] = new LinkedList<>();
            }
        }
        
        void addEdge(int v, int w) {
            adjList[v].add(w);
        }
        
        void DFS(int start) {
            boolean[] visited = new boolean[vertices];
            Deque<Integer> stack = new ArrayDeque<>();
            
            stack.push(start);  // 起始节点入栈
            
            while (!stack.isEmpty()) {
                int vertex = stack.pop();  // 出栈
                
                if (!visited[vertex]) {
                    visited[vertex] = true;
                    System.out.print(vertex + " ");
                    
                    // 将所有未访问的邻居入栈
                    for (int neighbor : adjList[vertex]) {
                        if (!visited[neighbor]) {
                            stack.push(neighbor);
                        }
                    }
                }
            }
        }
    }
}

DFS执行过程图解：

text

图结构：  0——1——3
         |  |
         2——4

从0开始的DFS过程：

步骤1: 访问0，栈: [ ]
      将0的邻居1,2入栈 → 栈: [2, 1]

步骤2: 弹出2，访问2，栈: [1]
      将2的邻居4入栈 → 栈: [4, 1]

步骤3: 弹出4，访问4，栈: [1]
      将4的邻居3入栈 → 栈: [3, 1]

步骤4: 弹出3，访问3，栈: [1]
      3的邻居1已访问，不入栈

步骤5: 弹出1，访问1，栈: [ ]

访问顺序: 0 → 2 → 4 → 3 → 1

4. 浏览器的前进后退功能

java

public class BrowserHistory {
    private Deque<String> historyStack;      // 后退栈
    private Deque<String> forwardStack;      // 前进栈
    private String currentPage;
    
    public BrowserHistory(String homepage) {
        historyStack = new ArrayDeque<>();
        forwardStack = new ArrayDeque<>();
        currentPage = homepage;
    }
    
    public void visit(String url) {
        historyStack.push(currentPage);  // 当前页入后退栈
        currentPage = url;
        forwardStack.clear();  // 新访问清空前栈
        System.out.println("访问: " + url);
    }
    
    public String back() {
        if (!historyStack.isEmpty()) {
            forwardStack.push(currentPage);  // 当前页入前栈
            currentPage = historyStack.pop();  // 后退
            System.out.println("后退到: " + currentPage);
        }
        return currentPage;
    }
    
    public String forward() {
        if (!forwardStack.isEmpty()) {
            historyStack.push(currentPage);  // 当前页入后栈
            currentPage = forwardStack.pop();  // 前进
            System.out.println("前进到: " + currentPage);
        }
        return currentPage;
    }
}

执行过程图解：

text

访问顺序: A → B → C → D

操作过程:
1. 访问A: 后退栈[]         当前页A  前进栈[]
2. 访问B: 后退栈[A]        当前页B  前进栈[]
3. 访问C: 后退栈[A,B]      当前页C  前进栈[]
4. 访问D: 后退栈[A,B,C]    当前页D  前进栈[]

点击后退:
5. 后退:  后退栈[A,B]      当前页C  前进栈[D]
6. 后退:  后退栈[A]        当前页B  前进栈[D,C]

点击前进:
7. 前进:  后退栈[A,B]      当前页C  前进栈[D]

四、栈的复杂度分析

操作	顺序栈（数组）	链式栈（链表）	说明
Push	O(1)*	O(1)	*数组可能需扩容，摊销后仍为O(1)
Pop	O(1)	O(1)	直接操作栈顶
Peek	O(1)	O(1)	查看栈顶元素
Search	O(n)	O(n)	需要遍历
空间	O(n)	O(n)

五、栈的使用场景总结

语法解析
- 括号匹配
- XML/HTML标签校验
- 表达式求值
系统调用
- 函数调用堆栈
- 递归实现
- 异常处理栈轨迹
算法实现
- DFS深度优先搜索
- 回溯算法
- 迷宫求解
- 汉诺塔问题
日常应用
- 浏览器后退前进
- 编辑器撤销操作
- 代码编译器的语法检查
- 计算器的表达式计算

栈这种看似简单的数据结构，通过"后进先出"的特性，在计算机科学中发挥着不可替代的作用。掌握栈的原理和应用，对于理解更复杂的算法和系统设计都至关重要。

队列的详细原理解析

一、队列的基本概念

队列是一种先进先出（FIFO, First In First Out）的线性数据结构，只允许在一端（队尾）进行插入操作，在另一端（队头）进行删除操作。

二、队列的存储结构图解

1. 顺序队列（数组实现）

初始状态（空队列）：

text

    front = 0
    rear = 0
    
    数组: [ ][ ][ ][ ][ ][ ]
           ↑
        front/rear

插入元素A、B、C后：

text

    操作：queue.offer(A)
         queue.offer(B)
         queue.offer(C)
    
    数组: [A][B][C][ ][ ][ ]
           ↑       ↑
         front    rear
    rear = 3
    front = 0

删除一个元素（出队）后：

text

    操作：queue.poll()  // 移除A
    
    数组: [ ][B][C][ ][ ][ ]
             ↑    ↑
           front  rear
    rear = 3
    front = 1  // front指针后移

2. 链式队列（链表实现）

text

    front节点                  rear节点
       ↓                          ↓
    ┌───┬───┐    ┌───┬───┐    ┌───┬───┐
    │ A │next──→│ B │next──→│ C │null│
    └───┴───┘    └───┴───┘    └───┴───┘
    
    队头可以出队               队尾可以入队

三、顺序队列的"假溢出"问题及解决方案

1. 假溢出问题图解

text

    初始：插入A,B,C,D
    [A][B][C][D][ ][ ]
     ↑           ↑
    front       rear
    
    删除A,B：front后移
    [ ][ ][C][D][ ][ ]
           ↑    ↑
         front rear
    
    此时想插入E：rear已到末尾，但数组前面还有空间
    [ ][ ][C][D][E][ ]
           ↑       ↑
         front    rear
    
    再插入F：rear越界，但front前面还有空间 → 假溢出！
    [ ][ ][C][D][E][F]  // rear = 6，超出数组长度
           ↑           ↑
         front        rear(越界)

2. 循环队列解决方案

利用取模运算实现逻辑上的环形结构：

text

    数组大小 n = 6
    
    初始状态：
    [ ][ ][ ][ ][ ][ ]
     ↑
    front=0, rear=0
    
    插入A,B,C,D：
    [A][B][C][D][ ][ ]
     ↑        ↑
    front=0  rear=4
    
    删除A,B：
    [ ][ ][C][D][ ][ ]
           ↑    ↑
        front=2 rear=4
    
    插入E,F：
    [E][F][C][D][ ][ ]  // 利用取模，E插入索引4，F插入索引5
           ↑        ↑
        front=2   rear=0 (rear = (4+2) % 6 = 0)
    
    此时队列满的条件：(rear+1) % n == front
    rear=0, (0+1)%6=1 ≠ front=2，还可插入

循环队列的判空判满：

java

// 判空
isEmpty() { return front == rear; }

// 判满
isFull() { return (rear + 1) % capacity == front; }

// 入队
offer(E e) {
    if (isFull()) return false;  // 队列满
    elements[rear] = e;
    rear = (rear + 1) % capacity;
    return true;
}

// 出队
poll() {
    if (isEmpty()) return null;  // 队列空
    E e = elements[front];
    front = (front + 1) % capacity;
    return e;
}

四、队列的变种及其原理

1. 双端队列（Deque）

可以在两端进行插入和删除操作：

text

           addFirst     addLast
               ↓           ↓
        ┌───┬───┬───┬───┬───┐
        │   │   │   │   │   │
        └───┴───┴───┴───┴───┘
           ↑           ↑
        removeFirst  removeLast
        
        可以同时作为栈和队列使用

Java实现原理：

java

// ArrayDeque的内部实现（循环数组）
public class ArrayDeque<E> {
    transient Object[] elements;  // 存储元素的数组
    transient int head;           // 头部索引
    transient int tail;           // 尾部索引
    
    public void addFirst(E e) {
        head = (head - 1) & (elements.length - 1);
        elements[head] = e;
    }
    
    public void addLast(E e) {
        elements[tail] = e;
        tail = (tail + 1) & (elements.length - 1);
    }
}

2. 优先队列（PriorityQueue）

基于堆（Heap）实现，元素按优先级出队：

text

        优先级最高元素（最小值/最大值）
                ↓
               [5]
              /    \
            [10]   [15]    二叉堆结构
           /    \
        [20]   [25]
        
    插入新元素：上浮调整
    删除元素：下沉调整

二叉堆原理图解：

text

数组形式存储： [5,10,15,20,25]
索引关系：     0  1  2  3  4

父子节点关系：
- 父节点索引 = (子节点索引 - 1) / 2
- 左子节点索引 = 父节点索引 * 2 + 1
- 右子节点索引 = 父节点索引 * 2 + 2

小顶堆性质：父节点 ≤ 子节点
大顶堆性质：父节点 ≥ 子节点

插入操作（上浮）：

text

插入元素3：
1. 先放在数组末尾：[5,10,15,20,25,3]
2. 与父节点比较：3 < 15，交换
3. 继续与父节点比较：3 < 5，交换
4. 最终位置：[3,10,5,20,25,15]

删除操作（下沉）：

text

删除堆顶3：
1. 将最后一个元素移到堆顶：[15,10,5,20,25]
2. 与子节点比较：15 > 5，与较小的子节点5交换
3. 继续下沉：[5,10,15,20,25]

3. 阻塞队列（BlockingQueue）

用于生产者-消费者模式，支持线程安全操作：

text

    生产者线程1 ──┐
    生产者线程2 ──┼─→ [队列] ──→ 消费者线程1
    生产者线程3 ──┘             消费者线程2
    
    队列空时：消费者线程阻塞等待
    队列满时：生产者线程阻塞等待

五、队列的经典算法应用

1. 广度优先搜索（BFS）

java

public class BFS {
    // 二叉树层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();  // 当前层节点数
            List<Integer> currentLevel = new ArrayList<>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                
                // 下一层节点入队
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            
            result.add(currentLevel);
        }
        
        return result;
    }
}

执行过程图解：

text

二叉树：
        1
       / \
      2   3
     / \   \
    4   5   6

队列变化：
1. 初始: [1]
2. 处理1: 输出1，入队2,3 → [2,3]
3. 处理2: 输出2，入队4,5 → [3,4,5]
4. 处理3: 输出3，入队6 → [4,5,6]
5. 处理4,5,6: 输出4,5,6 → []

层序遍历结果：1,2,3,4,5,6

2. 滑动窗口最大值

java

public class SlidingWindowMax {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        
        // 使用双端队列存储索引，保持递减顺序
        Deque<Integer> deque = new ArrayDeque<>();
        int[] result = new int[nums.length - k + 1];
        
        for (int i = 0; i < nums.length; i++) {
            // 移除超出窗口范围的元素
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            
            // 保持队列递减：移除所有小于当前元素的队尾元素
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            
            deque.offerLast(i);
            
            // 当窗口形成后，记录最大值
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
}

图解过程（数组[1,3,-1,-3,5,3,6,7]，k=3）：

text

窗口位置        队列（存储索引）    最大值
[1,3,-1],-3,5,3,6,7  [1(3)]        3
1,[3,-1,-3],5,3,6,7  [1(3),2(-1)]  3
1,3,[-1,-3,5],3,6,7  [4(5)]         5
1,3,-1,[-3,5,3],6,7  [4(5),5(3)]    5
1,3,-1,-3,[5,3,6],7  [6(6)]         6
1,3,-1,-3,5,[3,6,7]  [7(7)]         7

3. 用队列实现栈

java

public class StackUsingQueue {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;
    
    public StackUsingQueue() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    // 方法1：push操作O(n)，pop操作O(1)
    public void push(int x) {
        queue2.offer(x);
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        // 交换引用
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    public int pop() {
        return queue1.poll();
    }
    
    // 方法2：push操作O(1)，pop操作O(n)
    public void push2(int x) {
        queue1.offer(x);
    }
    
    public int pop2() {
        while (queue1.size() > 1) {
            queue2.offer(queue1.poll());
        }
        int result = queue1.poll();
        // 交换引用
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
        return result;
    }
}

操作图解（方法2）：

text

入栈顺序：1 → 2 → 3

push 1: queue1: [1]
push 2: queue1: [1,2]
push 3: queue1: [1,2,3]

pop:
1. 将1,2移到queue2: queue1: [3], queue2: [1,2]
2. 弹出3: 结果=3
3. 交换queue1和queue2: queue1: [1,2], queue2: []

4. 消息队列（生产者-消费者模式）

java

public class MessageQueue {
    private final Queue<String> queue = new LinkedList<>();
    private final int capacity;
    private final Object lock = new Object();
    
    public MessageQueue(int capacity) {
        this.capacity = capacity;
    }
    
    // 生产者
    public void produce(String message) throws InterruptedException {
        synchronized (lock) {
            while (queue.size() == capacity) {
                System.out.println("队列满，生产者等待...");
                lock.wait();  // 队列满时等待
            }
            
            queue.offer(message);
            System.out.println("生产: " + message + ", 队列大小: " + queue.size());
            lock.notifyAll();  // 唤醒消费者
        }
    }
    
    // 消费者
    public String consume() throws InterruptedException {
        synchronized (lock) {
            while (queue.isEmpty()) {
                System.out.println("队列空，消费者等待...");
                lock.wait();  // 队列空时等待
            }
            
            String message = queue.poll();
            System.out.println("消费: " + message + ", 队列大小: " + queue.size());
            lock.notifyAll();  // 唤醒生产者
            
            return message;
        }
    }
}

// 使用示例
public class ProducerConsumerDemo {
    public static void main(String[] args) {
        MessageQueue mq = new MessageQueue(3);
        
        // 生产者线程
        new Thread(() -> {
            for (int i = 0; i < 10; i++) {
                try {
                    mq.produce("消息" + i);
                    Thread.sleep(500);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }).start();
        
        // 消费者线程
        new Thread(() -> {
            for (int i = 0; i < 10; i++) {
                try {
                    mq.consume();
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }).start();
    }
}

六、队列的复杂度分析

操作	普通队列	循环队列	链式队列	优先队列	说明
入队	O(1)*	O(1)	O(1)	O(log n)	*普通数组可能需移动元素
出队	O(1)*	O(1)	O(1)	O(log n)	*普通数组可能需移动元素
查看队首	O(1)	O(1)	O(1)	O(1)
查找	O(n)	O(n)	O(n)	O(n)
空间	O(n)	O(n)	O(n)	O(n)

七、队列的应用场景总结

队列这种看似简单的数据结构，通过"先进先出"的特性，在计算机系统中扮演着缓冲、解耦、削峰的重要角色。理解队列的原理和实现，对于开发高并发、高可用的系统至关重要。

系统设计
- 消息队列（Kafka、RabbitMQ）
- 任务调度队列
- 线程池任务缓冲
- 请求排队处理
算法应用
- BFS广度优先搜索
- 滑动窗口问题
- 树的层序遍历
- 图的拓扑排序
实际开发
- 打印机任务队列
- 键盘缓冲区
- 网络数据包处理
- 数据库连接池
并发编程
- 生产者-消费者模式
- 线程池工作队列
- 异步任务处理
- 流量削峰填谷

用队列实现栈的含义详解（不同数据类型的融合）

栈和队列是并列的两种不同数据结构，但"用队列实现栈"的意思是：使用队列这种数据结构作为底层存储，通过特定的操作方式，模拟出栈的行为特性（LIFO）。

这就像是：给你一些积木（队列），让你搭出一个能实现"后进先出"功能的装置（栈）。虽然积木本身是方的（FIFO），但通过巧妙的组合方式，可以实现圆的功能（LIFO）。

一、为什么要用队列实现栈？

语言限制：有些编程语言只提供了队列的库，没有栈，需要自己模拟
理解数据结构：帮助深入理解两种数据结构的本质区别
面试考察：常见的算法面试题，考察对数据结构的灵活运用
特殊场景：某些系统只能使用队列接口，但需要栈的功能

二、两种实现方式图解

方法一：入栈时调整（push O(n), pop O(1)）

使用两个队列：主队列q1和辅助队列q2

核心思想：每次入栈时，保证新元素总是在队首位置

java

class StackUsingQueue_Method1 {
    private Queue<Integer> q1;  // 主队列
    private Queue<Integer> q2;  // 辅助队列
    
    public StackUsingQueue_Method1() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    
    // 入栈 - O(n)
    public void push(int x) {
        // 1. 新元素先放入q2
        q2.offer(x);
        
        // 2. 将q1所有元素移到q2
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        
        // 3. 交换q1和q2的引用
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }
    
    // 出栈 - O(1)
    public int pop() {
        return q1.poll();
    }
}

执行过程图解：

text

入栈顺序：1 → 2 → 3

步骤1：push(1)
q1: [ ]          q2: [1]
↓ 交换后
q1: [1]          q2: [ ]    ← 1在队首，相当于栈顶

步骤2：push(2)
q1: [1]          q2: [2]
↓ q1元素移到q2
q1: [ ]          q2: [2,1]
↓ 交换后
q1: [2,1]        q2: [ ]    ← 2在队首，相当于栈顶

步骤3：push(3)
q1: [2,1]        q2: [3]
↓ q1元素移到q2
q1: [ ]          q2: [3,2,1]
↓ 交换后
q1: [3,2,1]      q2: [ ]    ← 3在队首，相当于栈顶

此时队列q1的顺序：[3,2,1]（队首→队尾）
对应栈的顺序：    栈顶3, 栈底1

pop()操作：
q1.poll() → 3  （队首出队，即栈顶出栈）
q1剩余：[2,1]  （对应栈中剩余2,1）

方法二：出栈时调整（push O(1), pop O(n)）

核心思想：入栈直接放，出栈时把前面的元素都挪走

java

class StackUsingQueue_Method2 {
    private Queue<Integer> q1;  // 主队列
    private Queue<Integer> q2;  // 辅助队列
    
    public StackUsingQueue_Method2() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    
    // 入栈 - O(1)
    public void push(int x) {
        q1.offer(x);
    }
    
    // 出栈 - O(n)
    public int pop() {
        // 将q1前n-1个元素移到q2
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }
        
        // 最后一个元素就是要出栈的
        int result = q1.poll();
        
        // 交换q1和q2
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
        
        return result;
    }
}

执行过程图解：

text

入栈顺序：1 → 2 → 3

步骤1：push(1)
q1: [1]          q2: [ ]

步骤2：push(2)
q1: [1,2]        q2: [ ]

步骤3：push(3)
q1: [1,2,3]      q2: [ ]

此时队列q1的顺序：[1,2,3]（队首→队尾）
对应栈的顺序：    栈底1, 栈顶3

pop()操作 - 想拿到3（栈顶）：
1. 将前2个元素移到q2
   q1: [3]          q2: [1,2]
   
2. q1中剩下的3就是要出栈的
   result = q1.poll() → 3
   
3. 交换队列
   q1: [1,2]        q2: [ ]
   q1中现在[1,2]对应栈中剩余[1,2]（1在栈底，2在栈顶）

下一次pop()：
1. 将前1个元素移到q2
   q1: [2]          q2: [1]
2. result = 2
3. 交换后q1: [1]

三、用栈实现队列

既然可以用队列实现栈，当然也可以用栈实现队列：

java

class QueueUsingStack {
    private Stack<Integer> stack1;  // 入队栈
    private Stack<Integer> stack2;  // 出队栈
    
    public QueueUsingStack() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    // 入队 - O(1)
    public void offer(int x) {
        stack1.push(x);
    }
    
    // 出队 - 平均O(1)
    public int poll() {
        if (stack2.isEmpty()) {
            // 将stack1所有元素倒入stack2
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

执行过程图解：

text

入队顺序：1 → 2 → 3

offer(1): stack1: [1]        stack2: []
offer(2): stack1: [1,2]      stack2: []
offer(3): stack1: [1,2,3]    stack2: []

poll()操作 - 想要拿到1（队首）：
stack2为空，将stack1倒入stack2：
stack1弹出顺序：3,2,1
stack2压入顺序：3,2,1 → stack2: [3,2,1]
然后stack2.pop() → 1

此时stack1: []      stack2: [3,2]

下一次poll()：
stack2不为空，直接pop → 2
stack2剩余: [3]

四、理解要点对比

方面	栈 (Stack)	队列 (Queue)	用队列实现的栈
本质特性	LIFO	FIFO	模拟LIFO
底层存储	数组/链表	数组/链表	队列
对外接口	push/pop	offer/poll	push/pop
内部实现	直接操作一端	两端操作	用队列的offer/poll组合实现

五、类比理解

用队列实现栈，就像：

排队买票但后到的人先买
- 正常排队：先到先买（队列）
- 但你想实现：后到先买（栈）
- 办法：让新来的人插队到最前面
一列火车要变成栈
- 火车车厢（队列）：只能从一端进，另一端出
- 要变成：只能从同一端进出（栈）
- 办法：加一条辅助铁轨，来回倒腾
自助餐厅的餐盘
- 正常餐盘：后放的先拿（栈）
- 但餐厅只有传送带（队列）：一端放，另一端取
- 办法：每次放新餐盘时，把传送带上的都拿下来，放上新盘，再把原来的放回去

六、总结

"用队列实现栈"的本质是：

存储介质：使用队列（FIFO）作为底层存储
操作逻辑：通过控制队列的出入队顺序，模拟栈的LIFO行为
对外表现：提供标准的栈接口（push/pop/peek）

这就好比你用算盘（队列）去模拟计算器（栈）的功能——虽然工具不同，但通过巧妙的使用方法，可以达到相同的目的。这也是数据结构学习中很重要的一课：灵活运用基础数据结构，组合出更复杂的功能

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2026-04-22，如有侵权请联系 cloudcommunity@tencent.com 删除

算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！