【数据结构】栈和队列的深度探索，从实现到应用详解

💎所属专栏：数据结构与算法学习 

💎 欢迎大家互三：2的n次方_

🍁1. 栈的介绍

栈是一种后进先出的数据结构，栈中的元素只能从栈顶进行插入和删除操作，类似于叠盘子，最后放上去的盘子最先拿下来。

🍁2. 栈的基本操作

• 压栈（Push）：将一个元素压入栈顶。
• 出栈（Pop）：移除并返回栈顶元素。
• 栈顶元素（Peek）：返回栈顶元素但不移除。
• 判空（IsEmpty）：检查栈是否为空。
• 栈的大小（Size）：返回栈中的元素个数。

栈的定义方法也是和ArrayList一样的，然后就是使用对象去调用栈的方法

public class Text {
    public static void main(String[] args) {
        Stack<Integer> stack1 = new Stack<>();
        stack1.push(1);
        stack1.push(2);
        stack1.push(3);
        System.out.println(stack1.pop());
        System.out.println(stack1.peek());
        System.out.println(stack1.isEmpty());
        System.out.println(stack1.size());
    }
}

🍁3. 栈的实现

首先，栈是通过数组实现的，就像之前实现的顺序表一样

public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack() {
        this.elem = new int[10];
    }
}

接下来实现一些栈的基本操作

🍁3.1 push()

当1 2 3 4依次入栈时，如下图

入栈其实很简单，只需要把元素放进去，接着usedSize++就可以了，但是学习数据结构我们的思维要严谨，如果栈满了怎么办，所以还需要处理栈满的情况，栈满之后就扩容，扩容也是和之前的顺序表一样的，判断是否栈满了也很简单，只需要判断数组的长度和usedSize是否相等就可以了

   public void push(int val) {
        if(isFull()) {
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;
   }
   public boolean isFull() {
        return usedSize == elem.length;
   }

🍁3.2 pop()

遵循后进先出的原则，第一次出栈取到的元素是4

那怎么去实现这个效果呢

只需要定义一个val，把栈顶的元素取出来，赋值给val，进行返回，同时出栈之后usedSize的值要减1

之后还需要考虑栈为空的情况，如果栈为空，肯定是不能再进行出栈的操作了，此时就需要抛出一个异常

    public int pop() {
        if(isEmpty()){
            throw new EmptyStackException();
        }
        int val = elem[usedSize - 1];
        usedSize--;
        return val;
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }

判断栈为空只需要判断usedSize是否为空

🍁3.3 peek()

peek(）是获取栈顶元素，但是不删除，这个其实更简单，只需要把下标为usedSize的元素进行返回就可以了，也不需要usedSize--

同时，还是需要处理一下栈为空的情况

    public int peek() {
        if(usedSize == 0){
            throw new EmptyStackException();
        }
        return elem[usedSize - 1];
    }

接下来把之前写的方法测试一下：

public class Text {
    public static void main(String[] args) {
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.print(stack.pop() + " ");
        System.out.print(stack.pop() + " ");
        System.out.print(stack.peek() + " ");
    }
}

🍁4. 栈的使用场景

🍁4.1 链表实现栈

问题：单链表是否可以实现栈？

单链表其实是可以实现栈的，用链表实现的栈叫做链式栈

入栈：如果采用尾插法入栈，入栈的时间复杂度为O(n)，如果给出last节点为O(1),出栈的时间复杂度为O(n),因为需要遍历到末尾才能入栈

如果采用头插法，入栈和出栈的时间复杂度都是O(1)

既然单链表可以实现栈了，那么双向链表肯定也可以实现栈，不论是头插还是尾插，双链表实现的栈出栈和入栈时间复杂度都是O(1)。

而且会发现，LinkedList也定义了栈的一些基本操作，可以当作栈来使用

🍁4.2 将递归转化为循环

一个典型的例子就是逆序打印链表，我们都知道，正常情况下，单链表是不能逆序打印的，递归的调用就类似于栈，最外面的一层先被打印，也就是最末尾元素最先打印，还可以通过栈来模拟递归

    //递归方式
    private void printList1(MySingleList.ListNode head){
        if(head!=null){
            printList1(head.next);
            System.out.print(head.value + " ");
        }
    }
    //循环方式
    private void printList2(MySingleList.ListNode head){
        if(head == null) return;
        Stack<MySingleList.ListNode> s = new Stack<>();
        MySingleList.ListNode cur = head;
        //将节点保存在栈中
        while(cur!=null){
            s.push(cur);
            cur = cur.next;
        }
        //打印栈中节点
        while(!s.empty()){
            System.out.print(s.pop().value + " ");
        }
    }

🍁5. 队列的介绍

队列是一种先进先出的数据结构。队列中的元素只能从队尾插入，从队首移除，类似于排队买票，最先排队的人最先买到票。

 Java中的Queue是一个接口，Deque叫做双端队列

🍁6. 队列的基本操作

1. 入队（offer）：将一个元素插入队尾。
2. 出队（poll）：移除并返回队首元素。
3. 队首元素（Peek）：返回队首元素但不移除。
4. 判空（IsEmpty）：检查队列是否为空。
5. 队列的大小（Size）：返回队列中的元素个数。

由于Queue是一个接口，不能直接创建对象，所以这里通过LinkedList来创建对象 

public class Text {
    public static void main(String[] args) {
        //使用接口的实现类LinkedList创建对象
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        //出队
        System.out.println(q.poll());
        //获取对头元素
        System.out.println(q.peek());
    }
}

🍁7. 队列的实现

🍁7.1 双向链表实现队列

双向链表的话，和栈一样，入队和出队的操作时间复杂度为O(n)，因为队列是先进先出的原则，入队就采用尾插的方法，出队也就是头删的方法

public class MyQueue {
    //双向链表
    static class ListNode {
        public int val;
        ListNode pre;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    ListNode first = null;
    ListNode last = null;
    public int usedSize = 0;
    //尾插的方法进行入队
    public void offer(int val) {
        ListNode node = new ListNode(val);
        if (isEmpty()) {
            first = last = node;
        } else {
            last.next = node;
            node.pre = last;
            last = last.next;
        }
        usedSize++;
    }
    //头删的方法进行出队
    public int poll() {
        if (first == null) {
            throw new EmptyQueueException("队列为空");
        }
        int value = first.val;
        first = first.next;
        if(first!=null){
            first.pre = null;
        }
        usedSize--;
        return value;
    }
    //获取队头元素
    public int peek() {
        if (first == null) {
            throw new EmptyQueueException("队列为空");
        }
        return first.val;
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }
}

🍁7.2 数组实现的循环队列

如果采用正常的数组来实现队列的话就会有以下的弊端，

这样出队之后，数组前面的空间就会空出来，造成空间的浪费，那如何把这些空间也利用起来呢

使用这样的循环结构，就可以解决这个问题，也就是循环队列

front和rear在同一个位置时，表示队列为空，那么队列满了也是这样的情况，此时怎么区分呢？

1.定义一个size专门判断

2.添加标记，定义一个boolean类型的flag，表示走过没有

3.空出一个空间，此时rear.next == front就表示队列已满 

此时还有一个问题：对于以上的例子，怎么解决下标的问题，例如从7下标是怎么到0下标的

 也就是下标最后再往后怎么表示：

公式：(数组下标 - 偏移量) % 数组长度 

7 ~ 0  可以通过 （7 + 1）% 8 来表示

还有一种情况：下标最前再往前

例如 2 下标往前走到 7 下标

公式：(数组下标 + 数组长度 - 偏移量) % 数组长度 

（2 + 9 - 4）% 9，加上数组长度也就是为了避免负数的情况

代码

测试用例

测试用例

测试结果

622. 设计循环队列

我们通过力扣上的这道题来实现一下：

class MyCircularQueue {
    public int front;
    public int rear;
    public int[] elem;

    public MyCircularQueue(int k) {
        elem = new int[k + 1];//由于有一个位置空出来了，所以要额外再多一个位置
    }

    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        elem[rear] = value;
        rear = (rear + 1) % elem.length;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % elem.length;
        return true;
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        } else {
            return elem[front];
        }
    }

    public int Rear() {
        if (isEmpty())
            return -1;
        int index = (rear == 0 )? elem.length - 1 : rear - 1;
        return elem[index];
    }

    public boolean isEmpty() {
        return rear == front;
    }

    public boolean isFull() {
        return (rear + 1) % elem.length == front;
    }
}

🍁8. 双端队列 

在Java中，Deque（双端队列）是一个接口，它扩展了Queue接口。Deque支持在两端插入和删除元素，提供了比Queue更丰富的操作集合。可以使用Deque作为栈（后进先出）、队列（先进先出）、或者两者兼有。

Java提供了几种Deque的实现，其中最常见的是ArrayDeque和LinkedList。ArrayDeque是基于数组的双端队列，它在大多数操作中都提供了更好的性能。而LinkedList也实现了Deque接口，但由于其基于链表的结构，它在添加和删除元素时可能不如ArrayDeque高效。

public class DequeDemo {
    public static void main(String[] args) {
        //线性实现
        Deque<Integer> deque = new ArrayDeque<>();
        deque.add(1);
        deque.add(2);
        deque.add(3);
        for(int i : deque){
            System.out.println(i);
        }
        //链式实现
        Deque<Integer> ldeque = new LinkedList<>();
        ldeque.add(1);
        ldeque.add(1);
        ldeque.add(1);
        for(int i : ldeque){
            System.out.println(i);
        }
    }
}