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

队列的基本概念

队列（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，从而实现顺序反转。

具体策略：

1. 入队时直接压入栈 A。
2. 出队或查看队首时，如果栈 B 为空，则将栈 A 的所有元素弹出并压入栈 B。此时栈 B 的栈顶即为最早进入的元素。
3. 如果栈 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();
    }
}

总结

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

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