Java 栈与队列原理及手写实现

栈的核心概念

栈（Stack）是一种线性数据结构，核心特性是后进先出（LIFO）。想象一下子弹夹：最后装进去的子弹最先发射。栈底是最早放入的元素，栈顶则是最新进入的数据。

在实际应用中，栈常用于内存分配、表达式求值以及方法调用链的管理。理解栈的关键在于把握'栈顶'这一操作点的所有进出逻辑。

栈结构示意

数组模拟栈的实现

用数组实现栈非常直观，我们只需要一个指针 top 来标记当前栈顶位置。初始时 top 设为 -1，表示空栈。

主要操作包括：

push：入栈，元素放入 top+1 位置。
pop：出栈，返回 top 位置元素并将 top 减一。
peek：查看栈顶但不移除。
size / empty / full：辅助状态检查。

这里有个细节需要注意，当数组满了需要扩容。通常采用倍增策略，即容量翻倍，这样均摊时间复杂度更优。

import java.util.Arrays;

public class MyStack {
    private int[] elem;
    private int top; // 栈顶索引，也代表当前元素数量
    private static final int DEFAULT_CAPACITY = 10;

    public MyStack() {
        elem = new int[DEFAULT_CAPACITY];
        top = -1;
    }

    public void push(int item) {
        if (full()) {
            // 容量不足时扩容，通常是原来的两倍
            elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        elem[++top] = item;
    }

    public int pop() throws RuntimeException {
        if (empty()) {
            throw new RuntimeException("栈为空");
        }
        return elem[top--];
    }

    public int peek() {
        if (empty()) {
            throw new RuntimeException("栈为空");
        }
        return elem[top];
    }

    public int size() {
        return top + 1;
    }

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

    public boolean full() {
        return top == elem.length - 1;
    }
}

队列的基本概念

队列（Queue）遵循先进先出（FIFO）原则。数据从队尾（rear）进入，从队头（front）离开。就像排队买票一样，先来的人先处理。

队列操作主要包括入队（offer/enqueue）、出队（poll/dequeue）、查看队首（peek/front）等。

队列结构示意

双链表模拟队列

使用双链表实现队列可以避免数组扩容的问题，但空间开销稍大。我们需要维护 head 和 last 两个指针。

在插入新节点时，要注意双向链接的更新：新节点的 prev 指向原尾节点，原尾节点的 next 指向新节点，然后更新 last 指针。

public class MyQueue {
    static class Node {
        int elem;
        Node next;
        Node prev;

        Node(int elem) {
            this.elem = elem;
        }
    }

    private Node head;
    private Node last;
    private int size = 0;

    public void offer(int val) {
        Node queue = new Node(val);
        if (this.head == null) {
            this.head = queue;
            this.last = queue;
            ++size;
            return;
        }
        // 关键：更新尾部链接
        this.last.next = queue;
        queue.prev = this.last;
        this.last = queue;
        ++size;
    }

    public int poll() {
        if (this.head == null) {
            throw new RuntimeException("队列为空");
        }
        Node cur = this.head;
        if (this.head.next == null) {
            this.head = null;
            this.last = null;
        } else {
            this.head = this.head.next;
            this.head.prev = null;
        }
        size--;
        return cur.elem;
    }

    public int peek() {
        if (this.head != null) {
            return this.head.elem;
        }
        return 0;
    }

    public int size() {
        return size;
    }
}

循环队列（数组实现）

普通数组实现队列在频繁出队后会产生大量空隙，造成空间浪费。循环队列通过取模运算 (index + 1) % length 让下标回到数组头部，从而复用空间。

这里有一个经典陷阱：如何区分队满和队空？通常约定牺牲一个存储单元，或者增加一个 count 变量。下面的实现采用了牺牲一个单元的方式，即 rear 永远指向下一个可插入位置。

public class MyCircularQueue {
    private int[] array;
    private int front;
    private int rear;

    public MyCircularQueue(int k) {
        // 多开一个空间用于区分队空和队满
        array = new int[k + 1];
        front = 0;
        rear = 0;
    }

    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        array[rear] = value;
        rear = (rear + 1) % array.length;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % array.length;
        return true;
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return array[front];
    }

    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        // rear 指向下一个空位，所以实际最后一个元素是 (rear - 1 + len) % len
        int temp = (rear == 0) ? array.length - 1 : rear - 1;
        return array[temp];
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return (rear + 1) % array.length == front;
    }
}

用队列实现栈

既然队列是 FIFO，而栈是 LIFO，单靠一个队列无法直接实现栈的弹出顺序。我们需要借助两个队列协作。

思路很简单：每次压入新元素时，将其放入辅助队列，然后将主队列的所有元素依次移到辅助队列中，最后交换两个队列的引用。这样，新元素就始终位于'队头'，弹出时自然符合后进先出。

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

public class StackByQueue {
    Queue<Integer> q1;
    Queue<Integer> q2;

    public StackByQueue() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        // 将新元素放入非空队列或辅助队列
        q2.offer(x);
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        // 交换引用，确保 q1 始终是当前有效的栈
        Queue<Integer> tmp = q1;
        q1 = q2;
        q2 = tmp;
    }

    public int pop() {
        return q1.poll();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}

用栈来实现队列

反过来，用两个栈模拟队列也是经典面试题。利用栈的倒序特性，我们可以把数据从栈 A 倒入栈 B，从而实现顺序反转。

具体策略：

入队时直接压入栈 A。
出队或查看队首时，如果栈 B 为空，则将栈 A 的所有元素弹出并压入栈 B。此时栈 B 的栈顶即为最早进入的元素。
如果栈 B 不为空，直接从栈 B 弹出，无需再次搬运。

这种惰性转移的策略保证了每个元素最多被移动两次，效率较高。

import java.util.Stack;

public class QueueByStack {
    Stack<Integer> A;
    Stack<Integer> B;

    public QueueByStack() {
        A = new Stack<>();
        B = new Stack<>();
    }

    public void push(int x) {
        A.push(x);
    }

    public int pop() {
        int check = peek();
        B.pop();
        return check;
    }

    public int peek() {
        if (!B.isEmpty()) {
            return B.peek();
        }
        if (A.isEmpty()) {
            return -1;
        }
        while (!A.isEmpty()) {
            B.push(A.pop());
        }
        return B.peek();
    }

    public boolean empty() {
        return A.isEmpty() && B.isEmpty();
    }
}

总结

栈和队列是基础数据结构中的基石。栈强调'后进先出'，适合回溯、递归场景；队列强调'先进先出'，适合任务调度、广度优先搜索。

手写实现时，重点在于边界条件的判断（如空栈/空队列）以及指针的移动逻辑。无论是数组扩容还是循环取模，都需要仔细处理索引计算，避免越界或死循环。掌握这些底层逻辑，对后续学习复杂算法至关重要。