一、栈

栈是一种遵循**先进后出（LIFO, Last In First Out）**原则的数据结构，仅允许在栈的一端（称为栈顶）进行元素的插入（压栈）和删除（出栈）操作，另一端（栈底）则固定不可操作。下面我们从模拟实现和实际使用两个方面深入了解 Stack<>。

栈的模拟实现

要实现一个基础的栈，我们可以借助数组来存储元素，通过一个变量记录栈中已使用的元素个数（即栈顶位置），核心实现压栈、出栈、获取栈顶元素等功能。

import java.util.Arrays;

public class MyStack {
    // 存储栈元素的数组
    public int[] elem;
    // 记录栈中已使用的元素个数（同时标记栈顶下一个可插入位置）
    public int usedSized;

    // 构造方法：初始化栈的容量为10
    public MyStack() {
        this.elem = new int[10];
    }

    /**
     * 压栈：向栈顶添加元素
     * @param data 要添加的元素
     */
    public void push(int data) {
        // 栈满时进行扩容（扩容为原容量的2倍）
        if (usedSized == elem.length) {
            this.elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        // 将元素存入栈顶，更新已使用元素个数
        elem[usedSized] = data;
        usedSized++;
    }

    /**
     * 出栈：删除并返回栈顶元素
     * @return 栈顶元素；栈为空时返回-1
     */
    public int pop() {
        if (isEmpty()) {
            return -1;
        }
        // 获取栈顶元素（注意usedSized是下一个可插入位置，栈顶元素索引为usedSized-1）
        int tmp = elem[usedSized - 1];
        // 更新已使用元素个数（模拟出栈，无需真正删除数组元素，后续压栈会覆盖）
        usedSized--;
        return tmp;
    }

    /**
     * 查看栈顶元素：仅返回栈顶元素，不删除
     * @return 栈顶元素；栈为空时返回-1
     */
    public int peak() {
        if (isEmpty()) {
            return -1;
        }
        return elem[usedSized - 1];
    }

    /**
     * 判断栈是否为空
     * @return 栈为空返回true，否则返回false
     */
    public boolean isEmpty() {
        return usedSized == 0;
    }

    /**
     * 获取栈中元素个数
     * @return 栈的大小
     */
    public int size() {
        return usedSized;
    }
}

实际使用

Java 集合框架中提供了 java.util.Stack 类来实现栈功能，不过该类是早期实现，推荐后续使用双端队列 Deque 替代。下面先演示 Stack 类的基础使用方法。

import java.util.Stack;

public class StackTest {
    public static void main(String[] args) {
        // 创建一个存储Integer类型元素的栈
        Stack<Integer> s = new Stack<>();
        
        // 压栈：向栈顶添加元素
        s.push(12);
        s.push(23);
        s.push(34);
        s.push(45);
        
        // 出栈：删除并返回栈顶元素（此时栈顶为45，输出45）
        System.out.println(s.pop());
        
        // 查看栈顶元素：返回当前栈顶元素（此时栈顶为34，输出34），不删除
        System.out.println(s.peek());
        
        // 获取栈的大小（此时栈中剩余12、23、34，输出3）
        System.out.println(s.size());
        
        // 判断栈是否为空（此时栈非空，输出false）
        System.out.println(s.empty());
    }
}

二、队列

队列是一种遵循**先进先出（FIFO, First In First Out）**原则的数据结构，仅允许在队列的一端（队尾）插入元素，在另一端（队头）删除元素，类似于日常生活中的排队场景。

队列的模拟实现

队列的实现方式有多种，其中双向链表实现较为灵活，无需考虑扩容问题，下面借助双向链表模拟实现一个基础队列，核心实现入队、出队、获取队头元素等功能。

public class MyQueue {
    // 定义双向链表节点类，存储元素值和前后节点引用
    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;

        // 节点构造方法，初始化元素值
        public ListNode(int val) {
            this.val = val;
        }
    }

    // 队列的队头指针
    public ListNode head;
    // 队列的队尾指针
    public ListNode last;
    // 记录队列中元素个数
    public int usedSize;

    /**
     * 入队：向队尾添加元素
     * @param val 要添加的元素值
     */
    public void offer(int val) {
        // 创建新节点
        ListNode node = new ListNode(val);
        
        // 队列为空时，队头和队尾都指向新节点
        if (head == null) {
            head = node;
            last = node;
        } else {
            // 队列非空时，将新节点链接到队尾，更新队尾指针
            last.next = node;
            node.prev = last;
            last = last.next;
        }
        
        // 更新队列元素个数
        this.usedSize++;
    }

    /**
     * 出队：删除并返回队头元素
     * @return 队头元素；队列为空时返回-1
     */
    public int poll() {
        // 队列为空，返回-1
        if (head == null) {
            return -1;
        }
        
        // 记录队头元素值
        int val = head.val;
        
        // 队列中仅有一个元素时，清空队头和队尾指针
        if (head.next == null) {
            head = null;
            last = null;
        } else {
            // 队列中有多个元素时，更新队头指针，断开原队头节点的引用
            head = head.next;
            head.prev = null;
        }
        
        // 更新队列元素个数
        this.usedSize--;
        return val;
    }

    /**
     * 查看队头元素：仅返回队头元素，不删除
     * @return 队头元素；队列为空时返回-1
     */
    public int peek() {
        if (head == null) {
            return -1;
        }
        return head.val;
    }

    /**
     * 判断队列是否为空
     * @return 队列为空返回true，否则返回false
     */
    public boolean isEmpty() {
        return this.usedSize == 0;
    }

    /**
     * 获取队列中元素个数
     * @return 队列的大小
     */
    public int size() {
        return usedSize;
    }
}

常用方法

Java 集合框架中 Queue 是一个接口，无法直接实例化，通常使用其实现类 LinkedList（基于双向链表）来创建队列对象。下面演示 Queue 的核心常用方法。

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

public class QueueTest {
    public static void main(String[] args) {
        // 创建一个存储Integer类型元素的队列，使用LinkedList作为实现类
        Queue<Integer> queue = new LinkedList<>();
        
        // 入队：向队尾添加元素（依次添加12、23）
        queue.offer(12);
        queue.offer(23);
        
        // 出队：删除并返回队头元素（此时队头为12，输出12）
        System.out.println(queue.poll());
        
        // 查看队头元素：返回当前队头元素（此时队头为23，输出23），不删除
        System.out.println(queue.peek());
    }
}

双端队列

双端队列（Deque，全称 Double Ended Queue）是一种增强型的队列，打破了普通队列“仅能队尾入、队头出”的限制，允许在队头和队尾两端同时进行插入和删除操作。

它既可以模拟栈的先进后出特性，也可以模拟普通队列的先进先出特性，功能更为灵活，Java 中提供了 ArrayDeque（基于数组）和 LinkedList（基于双向链表）两个主要实现类。

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class DequeTest {
    public static void main(String[] args) {
        // 1. 基于数组实现的双端队列（查询效率高，增删首尾元素效率高）
        Deque<Integer> arrayDeque = new ArrayDeque<>();
        
        // 2. 基于双向链表实现的双端队列（增删元素灵活，无容量限制）
        Deque<Integer> linkedListDeque = new LinkedList<>();
        
        // 3. 用双端队列模拟栈（推荐使用，替代传统Stack类）
        Deque<Integer> stackByDeque = new LinkedList<>();
        
        // 双端队列模拟栈的压栈操作（向队尾添加元素，等价于栈顶压入）
        stackByDeque.offerLast(10);
        stackByDeque.offerLast(20);
        
        // 双端队列模拟栈的出栈操作（删除并返回队尾元素，等价于栈顶弹出）
        System.out.println(stackByDeque.pollLast()); // 输出20
    }
}

总结

栈（Stack）遵循先进后出，核心操作是压栈（push）和出栈（pop），可通过数组模拟实现，Java 中推荐用 Deque 替代传统 Stack 类。
队列（Queue）遵循先进先出，核心操作是入队（offer）和出队（poll），常用 LinkedList 作为实现类。
双端队列（Deque）支持两端增删元素，兼具栈和普通队列的功能，有 ArrayDeque（数组实现）和 LinkedList（链表实现）两种常用实现。

栈与队列

一、栈