一，最小栈（Min Stack）核心知识

1，定义：

                能够在O（1）时间复杂度内获取栈 的最小值的特殊栈结构

2，核心思想：

             使用双栈结构（普通栈加最小栈）

3，操作规则

普通栈：存储所有元素，执行常规入站，出栈操作

最小栈：仅存储当前最小值，与普通栈保持同步长度

              入栈：当元素小于等于最小栈的栈顶元素或最小栈为空时入栈

              出栈：当普通栈顶的元素等于最小栈顶元素时，同步出栈

4，时间复杂度

             所有操作（push pop top getMin ）时间复杂度均为O(1)

5，空间复杂度：

           O(n)最坏情况下需要存储所有元素

二，队列的核心知识

1，定义：

先进先出（FIFO）的数据结构，元素从队尾入队，从队头出队

2，分类：

• 普通队列：只能从队尾入队，队头出队
• 双端队列（Deque）：可从队头和队尾双向操作

3，Java中的队列

• Queue 是接口，常用实现类有 LinkedList、PriorityQueue 等
• Deque 接口继承自 Queue，提供更多操作方法

4，核心方法

操作	抛出异常	不抛出异常
入队	add（e）	offer(e)
出队	remove(e)	poll(e)
获取队头	element(e)	peek(e)

5，时间复杂度

• 链表实现：入队、出队均为 O (1)
• 数组实现：普通数组出队为 O (n)，循环数组为 O (1)

三，循环队列的关键技术点

1. 判断空满的三种方法：

   • 方法 1（推荐）：使用 size 变量，isEmpty() = (size == 0)，isFull() = (size == capacity)
   • 方法 2：保留一个空位置，isEmpty() = (front == rear)，isFull() = (rear + 1) % capacity == front
   • 方法 3：使用标记变量，如 boolean isFull 标记队列是否已满

2. 循环索引计算：

   • 队尾指针后移：rear = (rear + 1) % capacity
   • 队头指针后移：front = (front + 1) % capacity
   • 利用取模运算实现数组索引的循环复用

3. 优缺点：

   • 优点：充分利用数组空间，避免普通数组实现的空间浪费
   • 缺点：容量固定，无法动态扩容（需手动实现扩容逻辑）

四、链表与数组实现队列的对比

特性	链表实现	数组的实现
空间效率	不浪费空间	预先分配固定的空间
时间效率	所有操作O（1）	所有操作O（1）
动态扩容	容易实现	比较复杂
内存分配	分散分配	连续分配
使用场景	元素数量的不确定	元素数量可预估

五，代码合集

1.0最小栈的实现

import java.util.Stack;

/**
 * 最小栈实现类
 * 支持push、pop、top、getMin操作，所有操作时间复杂度均为O(1)
 */
public class MinStack {
    // 普通栈：存储所有元素
    private Stack<Integer> dataStack;
    // 最小栈：存储对应位置的最小值
    private Stack<Integer> minStack;

    /**
     * 构造方法：初始化两个栈
     */
    public MinStack() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }

    /**
     * 入栈操作
     * @param val 要入栈的元素
     */
    public void push(int val) {
        // 普通栈直接入栈
        dataStack.push(val);
        
        // 最小栈处理：
        // 1. 若最小栈为空，直接入栈
        // 2. 若不为空且当前元素小于等于最小栈顶元素，入栈
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        } else {
            // 否则重复压入当前最小值，保持与数据栈长度一致
            minStack.push(minStack.peek());
        }
    }

    /**
     * 出栈操作
     * 移除栈顶元素，两个栈同步出栈
     */
    public void pop() {
        // 栈为空时无需操作
        if (!dataStack.isEmpty()) {
            dataStack.pop();
            minStack.pop();
        }
    }

    /**
     * 获取栈顶元素
     * @return 栈顶元素值
     */
    public int top() {
        // 从数据栈获取栈顶元素
        return dataStack.peek();
    }

    /**
     * 获取当前栈中的最小值
     * @return 栈中的最小值
     */
    public int getMin() {
        // 从最小栈获取栈顶元素（即当前最小值）
        return minStack.peek();
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        
        // 此时最小值应为-3
        System.out.println(minStack.getMin()); // 输出: -3
        
        minStack.pop(); // 移除-3
        
        // 栈顶元素应为0
        System.out.println(minStack.top());    // 输出: 0
        
        // 此时最小值应为-2
        System.out.println(minStack.getMin()); // 输出: -2
    }
}

2.0队列的两种实现方式

/**
 * 基于循环数组的队列实现
 * 解决普通数组实现队列的空间浪费问题
 */
public class CircularArrayQueue {
    private int[] arr;      // 存储元素的数组
    private int front;      // 队头指针，指向队头元素
    private int rear;       // 队尾指针，指向队尾元素的下一个位置
    private int size;       // 队列中元素的数量
    private int capacity;   // 队列的容量
    
    /**
     * 构造方法：初始化指定容量的循环队列
     * @param capacity 队列的容量
     */
    public CircularArrayQueue(int capacity) {
        this.capacity = capacity;
        arr = new int[capacity];
        front = 0;
        rear = 0;
        size = 0;
    }
    
    /**
     * 入队操作：在队尾添加元素
     * @param val 要添加的元素
     * @return 成功返回true，队列满则返回false
     */
    public boolean offer(int val) {
        // 队列满了则无法入队
        if (isFull()) {
            return false;
        }
        
        // 在队尾位置添加元素
        arr[rear] = val;
        // 循环移动队尾指针：(rear + 1) % capacity
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }
    
    /**
     * 出队操作：移除并返回队头元素
     * @return 队头元素，队列为空返回-1
     */
    public int poll() {
        // 队列为空则无法出队
        if (isEmpty()) {
            return -1;
        }
        
        // 获取队头元素
        int val = arr[front];
        // 循环移动队头指针：(front + 1) % capacity
        front = (front + 1) % capacity;
        size--;
        return val;
    }
    
    /**
     * 获取队头元素但不移除
     * @return 队头元素，队列为空返回-1
     */
    public int peek() {
        if (isEmpty()) {
            return -1;
        }
        return arr[front];
    }
    
    /**
     * 判断队列是否为空
     * @return 空返回true，否则返回false
     */
    public boolean isEmpty() {
        return size == 0;
    }
    
    /**
     * 判断队列是否已满
     * @return 满返回true，否则返回false
     */
    public boolean isFull() {
        return size == capacity;
    }
    
    /**
     * 获取队列大小
     * @return 队列中元素的个数
     */
    public int size() {
        return size;
    }
    
    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 创建容量为3的循环队列
        CircularArrayQueue queue = new CircularArrayQueue(3);
        
        // 入队操作
        System.out.println("入队1: " + queue.offer(1));  // 输出: true
        System.out.println("入队2: " + queue.offer(2));  // 输出: true
        System.out.println("入队3: " + queue.offer(3));  // 输出: true
        System.out.println("入队4: " + queue.offer(4));  // 输出: false (队列已满)
        
        System.out.println("队头元素: " + queue.peek());  // 输出: 1
        System.out.println("队列大小: " + queue.size());  // 输出: 3
        
        // 出队操作
        System.out.println("出队元素: " + queue.poll());  // 输出: 1
        System.out.println("出队元素: " + queue.poll());  // 输出: 2
        
        // 再次入队
        System.out.println("入队4: " + queue.offer(4));  // 输出: true
        
        System.out.println("队列大小: " + queue.size());  // 输出: 2
        System.out.println("队头元素: " + queue.peek());  // 输出: 3
    }
}
=====================================================================================
======================================================================================
======================================================================================
/**
 * 基于双向链表的队列实现
 * 支持offer(入队)、poll(出队)、peek(获取队头)等操作
 */
public class LinkedListQueue {
    // 节点内部类
    private static class Node {
        int val;        // 节点值
        Node prev;      // 前驱节点
        Node next;      // 后继节点
        
        Node(int val) {
            this.val = val;
            this.prev = null;
            this.next = null;
        }
    }
    
    private Node head;  // 队头节点
    private Node tail;  // 队尾节点
    private int size;   // 队列大小
    
    /**
     * 构造方法：初始化空队列
     */
    public LinkedListQueue() {
        head = null;
        tail = null;
        size = 0;
    }
    
    /**
     * 入队操作：在队尾添加元素
     * @param val 要添加的元素
     * @return 成功返回true
     */
    public boolean offer(int val) {
        Node newNode = new Node(val);
        
        // 队列为空时，头节点和尾节点都指向新节点
        if (isEmpty()) {
            head = newNode;
            tail = newNode;
        } else {
            // 队列不为空时，在尾部添加新节点
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
        size++;
        return true;
    }
    
    /**
     * 出队操作：移除并返回队头元素
     * @return 队头元素，队列为空返回-1
     */
    public int poll() {
        if (isEmpty()) {
            return -1;  // 队列为空时返回-1
        }
        
        int val = head.val;
        // 只有一个节点时
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            // 多个节点时，移动头指针
            head = head.next;
            head.prev = null;  // 断开与前一个节点的连接
        }
        size--;
        return val;
    }
    
    /**
     * 获取队头元素但不移除
     * @return 队头元素，队列为空返回-1
     */
    public int peek() {
        if (isEmpty()) {
            return -1;  // 队列为空时返回-1
        }
        return head.val;
    }
    
    /**
     * 判断队列是否为空
     * @return 空返回true，否则返回false
     */
    public boolean isEmpty() {
        return size == 0;
    }
    
    /**
     * 获取队列大小
     * @return 队列中元素的个数
     */
    public int size() {
        return size;
    }
    
    /**
     * 测试方法
     */
    public static void main(String[] args) {
        LinkedListQueue queue = new LinkedListQueue();
        
        // 入队操作
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        
        System.out.println("队列大小: " + queue.size());  // 输出: 3
        System.out.println("队头元素: " + queue.peek());  // 输出: 1
        
        // 出队操作
        System.out.println("出队元素: " + queue.poll());  // 输出: 1
        System.out.println("出队元素: " + queue.poll());  // 输出: 2
        
        System.out.println("队列大小: " + queue.size());  // 输出: 1
        System.out.println("队头元素: " + queue.peek());  // 输出: 3
    }
}