【前言】

栈和队列作为数据结构领域的“基石”，分别以“后进先出”和“先进先出”的独特机制，在算法设计、系统架构等场景中发挥着不可替代的作用。本文将从概念定义、核心操作、底层实现三个维度，深度拆解栈的压栈、出栈原理与链表实现，同时详解队列的循环队列、双端队列（Deque）等进阶设计，帮助读者从原理到实践，彻底掌握这两种基础结构的精髓。

一、栈（Stack）

1.栈的概念

栈：是一种特殊的线性表，遵循“==先进后出==” 的原则。==在栈顶进行插入和删除，栈底的元素保持不变（除非栈空）==。相当于一踏书，取和放的时候都得从最上面进行。

压栈：进行元素的扎入（栈顶）；
出栈：删除栈顶的元素；

2. 栈的基本特征

• ==有限容量==：栈通常有固定的大小限制
• ==操作受限==：只能在一端（称为栈顶）进行插入和删除操作
• ==动态变化==：随着元素的入栈和出栈，栈顶位置会不断变化

3. 栈方法的使用

3.1 方法及功能对照表

3.2 代码示例

public class Test {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        //压栈
        stack.push(11);
        stack.push(12);
        stack.push(13);
        //获取有效个数
        System.out.println(stack.size());
        //获取元素（不删除）
        System.out.println(stack.peek());
        //出栈
        System.out.println(stack.pop());
        //判断是否为空
        if(stack.empty()){
            System.out.println("栈空");
        }else {
            System.out.println(stack.size());
        }
    }
}

压栈进去三个元素后，打印元素个数为3，然后peek()获取栈顶元素13，但没有删除，所以下面用pop()出栈时的栈顶元素仍然是13，最后判断栈是否为空，不为空打印元素个数为2

4.栈的模拟实现

栈的底层就是==数组==，但是也可以用链表实现

public class MyStack {
    public int[] arr;
    public int usedSize;
    public static final int DEFAULT_CAPACITY = 3;
    //构造方法
    public MyStack(){
        arr = new int[DEFAULT_CAPACITY];
    }
}

先定义一个数组，然后定义它的有效元素，再给一个指定容量

4.1压栈

//压栈
    public void push(int val){
        if(isFull()){
            //扩容
            arr = Arrays.copyOf(arr,2*arr.length);
        }
        arr[usedSize] = val;
        usedSize++;
    }
    public boolean isFull(){
        return usedSize == arr.length;
    }

先判断栈是否已满，满了就扩容，不为空就再usedSize位置放要添加的元素val，最后让usedSize++方便后面继续添加

4.2 出栈

//出栈
    public int pop(){
        if(isEmpty()){
            return -1;
        }
        int ret = arr[usedSize-1];
        usedSize--;
        return ret;
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }

先判断栈是否为空，空的话可以自定义一个异常，不为空就先记录它要出栈的元素，然后让usedSize–,下次放的时候就会覆盖掉，这样就出栈了

4.3 获取栈顶元素（不删除）

 public int peek(){
        if(isEmpty()){
            return -1;
        }
        return arr[usedSize-1];
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }

跟出栈一样，获取栈顶元素，usedSize不–

5.链表实现栈

5.1单链表实现

• ==头插法==：入栈和出栈时间复杂度都是O(1)；（出栈也是从头出）
• ==尾插法==：入栈O(N),因为要遍历，如果标记last就是O(1)。出栈从头出是O(1),从尾巴出的话也是O(N),即使标记最后一个，但要找前一个还得遍历链表

5.2双向链表

两边都可以入栈和出栈，时间复杂度都是O(1)

二、队列

1.队列的概念

队列是一种常见的数据结构，遵循“先进先出”原则。类似于显示生活中的排队操作。

• ==入队列==：在队尾进行插入操作；
• ==出队列==：在对头进行删除操作；

2.队列的使用

Queue是个接口，底层是通过链表实现的，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue的接口

在==Queue接口==的方法中，add(E)和offerE()都是入队列，但offer(E)会更加友好：==队列满时，会返回false，而add(E)会直接抛出异常==。poll()和peek()也一样，都会更加安全

public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(11);
        q.offer(112);
        q.offer(113);
        q.offer(114);
        System.out.println(q.peek());//获取
        System.out.println(q.poll());//删除
        System.out.println(q.size());
        System.out.println(q.isEmpty());
    }

3.队列的模拟实现

==双链表实现：==

public class MyQueue {
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode first;
    public ListNode last;
    int size;
    //入队列
    public void offer(int s){
        ListNode newnode = new ListNode(s);
        if(first == null){
            first = last = newnode;
        }else {
            last.next = newnode;
            newnode.prev = last;
        }
        last = newnode;
        size++;
    }
    //出队列
    public int poll(){
        int val = first.val;
        //判断队列为空
        if(first == null){
            return -1;
        }else if(first == last){//队列只有一个元素
            last = first = null;
        }else {//队列有多个元素
            first = first.next;
            first.prev = null;
        }
        return val;

    }
    //获取队头元素
    public int peek(){
        if(first == null){
            return -1;
        }
        return first.val;
    }
    public int size(){
       ListNode cur = first;
       int count = 0;
       while (cur != null){
           cur = cur.next;
           count++;
       }
       return count;
    }
    public boolean isEmpty(){
        return first == null;
    }


}

public class Test {
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.offer(11);
        myQueue.offer(22);
        myQueue.offer(33);
        myQueue.offer(44);

        System.out.println(myQueue.poll());//出列
        System.out.println(myQueue.peek());//获取不删除
        System.out.println(myQueue.size());
        System.out.println(myQueue.isEmpty());

4.循环队列

循环队列通过将队列的==首尾相连==，使得==当队列尾部到达存储空间的末尾时，可以循环利用之前释放的存储空间==。环形队列通常使用==数组==实现

【两个问题：】

1.当队列满时，如何首尾相连，就是7下标到0 ？

==(rear + 1)%len==(任何位置都可用)

2.刚开始rear == front,后面满了时也是rear == front,如何区分？

• ==加size与数组长度进行比较==；
• ==标记==
  队列为空时，front=rear=0，标志位 isFull=false。每次⼊队检查rear是否与front重合，如果重合设置isFull=true，表⽰队列已满，否则，正常⼊队并移动rear出队时，移动front指针，设置isFull=false。
• ==浪费/预留一个空间==

5.双端队列(Deque)

双端队列允许在队列的两端任意进行插入和删除操作

栈和队列都可以使用Deque接口

 Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
 
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现
 

三、总结

本文围绕栈和队列的核心特性展开，从栈的“后进先出”操作（压栈、出栈、获取栈顶）及链表实现，到队列的“先进先出”机制、循环队列优化、双端队列拓展，完整覆盖了二者的知识体系。理解这些内容，不仅能让我们在面对算法题时快速找到解题思路，更能在实际开发中（如设计缓存、处理并发任务）灵活运用其特性优化程序，为进阶学习更复杂的数据结构（如树、图）和算法（如DFS、BFS）筑牢根基。