Java的栈与队列以及代码实现

Java中的栈与队列

• 栈的基本概念（Stack）
• 栈的实现方式
• 栈的代码实现
• 队列（Queue）
• 队列的模拟实现（双链表）
• 循环队列（循环数组实现）
• 使用队列实现栈
• 使用栈实现队列
• 总结

栈的基本概念（Stack）

栈是一种基本的线性数据结构，遵循后进先出（LIFO）的原则。这意味着最后加入的元素将是第一个被移除的。栈的应用非常广泛，包括内存分配、表达式求值、临时数据存储以及方法调用等。以子弹夹为例，最先装填的子弹位于底部（栈底），而最后装填的子弹位于顶部（栈顶）。只有当顶部的子弹被射出后，底部的子弹才有机会发射。

栈的实现方式

栈可以通过数组来实现，我们可以将其想象为一个连续的数组，元素的添加和移除都发生在数组的一端。以下是模拟栈操作的基本方法：push（向栈中添加元素），pop（从栈中移除顶部元素），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; // 索引从0开始
    }

    public void push(int item) {
        if (full()) {
            // 栈满时扩容
            elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        elem[++top] = item;
    }

    public int pop() {
        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）的原则。元素的添加操作在队列的尾部进行，而元素的移除操作在队列的头部进行。

队列的模拟实现（双链表）

```java
public class MyQueue {
static class QueueNode {
public int elem;
public QueueNode next;
public QueueNode prev;
public QueueNode(int elem) {
this.elem = elem;
}
}

public QueueNode head;
public QueueNode last;
public int size = 0;

public void offer(int val) {
    QueueNode queue = new QueueNode(val);
    if (head == null) {
        head = queue;
        last = queue;
        ++size;
        return;
    }
    last.next = queue;
    queue.prev = head;
    last = queue;
    ++size;
}

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

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

public int size() {
    return size;