深入理解栈与队列：从底层存储到真实应用场景的完整解析

在数据结构的体系中，栈（Stack） 与 队列（Queue） 是两类极为基础但应用场景非常广泛的结构。它们在算法、系统体系结构以及工程系统中扮演着不可或缺的角色，例如：

• 函数调用栈
• 浏览器前进/后退操作
• 任务调度与消息队列
• BFS/DFS 图搜索
• 表达式求值

本篇将从底层结构出发，深入分析栈与队列的实现方式，并通过代码示例来展示它们在真实应用场景中的使用方法。

1. 栈（Stack）

1.1 栈的特点

栈是一种后进先出（LIFO, Last In First Out） 的数据结构。

1.2 栈的底层实现方式

栈通常使用 数组或链表 来实现：

• 使用数组实现栈：易于随机访问，性能高，但扩容可能带来开销。
• 使用链表实现栈：动态大小，不需要扩容，但有额外指针开销。

1.3 代码实战：使用数组实现栈（Java）

class MyStack {
    private int[] data;
    private int top; // 栈顶指针

    public MyStack(int capacity) {
        data = new int[capacity];
        top = -1;
    }

    public void push(int value) {
        if (top == data.length - 1) {
            throw new RuntimeException("栈已满");
        }
        data[++top] = value;
    }

    public int pop() {
        if (top == -1) {
            throw new RuntimeException("栈为空");
        }
        return data[top--];
    }

    public int peek() {
        if (top == -1) {
            throw new RuntimeException("栈为空");
        }
        return data[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }
}

1.4 栈的典型应用：函数调用栈

当程序调用函数时：

main()
 └─ A()
     └─ B()
         └─ C()

系统会把当前执行位置压入栈中，当函数执行完毕，系统从栈顶弹出返回地址继续执行。这种结构天然适合栈。

2. 队列（Queue）

2.1 队列的特点

队列是一种 先进先出（FIFO, First In First Out） 的数据结构。

2.2 队列的底层实现方式

普通数组实现队列会造成“假溢出”，因此通常链表或循环数组实现更高效。

示意图（循环队列）：

front → [ ] [ ] [x] [x] [x] ← rear

当 rear 到达数组末尾，可回绕到起点。

2.3 代码实战：循环队列（Java）

class MyQueue {
    private int[] data;
    private int front, rear, size;

    public MyQueue(int capacity) {
        data = new int[capacity];
        front = 0;
        rear = 0;
        size = 0;
    }

    public void enqueue(int value) {
        if (size == data.length) {
            throw new RuntimeException("队列已满");
        }
        data[rear] = value;
        rear = (rear + 1) % data.length;
        size++;
    }

    public int dequeue() {
        if (size == 0) {
            throw new RuntimeException("队列为空");
        }
        int value = data[front];
        front = (front + 1) % data.length;
        size--;
        return value;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

3. 浏览器前进/后退功能 —— 栈的经典应用

浏览器维护两个栈：

当点击后退：

• 当前页面压入 forwardStack
• 从 backStack 出栈成为当前页面

当点击前进：

• 回退操作逆向执行

3.1 模拟浏览器前进后退

import java.util.Stack;

public class Browser {
    Stack<String> back = new Stack<>();
    Stack<String> forward = new Stack<>();
    String current = "首页";

    public void visit(String url) {
        back.push(current);
        current = url;
        forward.clear();
        System.out.println("访问：" + current);
    }

    public void back() {
        if (!back.isEmpty()) {
            forward.push(current);
            current = back.pop();
            System.out.println("后退到：" + current);
        }
    }

    public void forward() {
        if (!forward.isEmpty()) {
            back.push(current);
            current = forward.pop();
            System.out.println("前进到：" + current);
        }
    }

    public static void main(String[] args) {
        Browser b = new Browser();
        b.visit("A");
        b.visit("B");
        b.visit("C");
        b.back();
        b.back();
        b.forward();
    }
}

输出示例：

访问：A
访问：B
访问：C
后退到：B
后退到：A
前进到：B

4. 总结

栈与队列虽然简单，但应用场景非常深远。理解其底层结构，将有助于我们编写更高效、更可靠的程序逻辑。

栈与队列虽然是数据结构中最基础的两个结构，但它们的思想贯穿在计算机系统的各个层面。栈的后进先出（LIFO） 特性使其天然适用于函数调用管理、表达式求值以及浏览器的后退功能；而 队列的先进先出（FIFO） 特性则让其成为任务调度、消息队列和广度优先搜索（BFS）等场景中的核心组件。理解它们的底层存储方式、操作规则及典型应用，不仅能够为编写高质量代码打下扎实基础，也能在系统设计和性能优化中提供重要思路。掌握基础，方能融会贯通，数据结构的力量也常常由此显现。