盐析白兔

这个屌丝很懒，什么也没留下！

热门标签

数据结构之栈和队列 - 超详细的教程，手把手教你认识并运用栈和队列_队列和栈

作者：盐析白兔 | 2024-07-23 08:18:25

踩

队列和栈

栈：后进先出

队列：先进先出

1. 栈(Stack)

1.1 概念

栈：是一种特殊的线性表，只允许在固定的一端插入或者删除元素，一个栈包含了栈顶和栈底。只能在栈顶插入或者删除元素。栈的底层是由数组实现的。

栈遵循先入后出原则，也就是先插入的元素得到后面才能删除，后面插入的元素比先插入的元素要更早的删除。可以理解成：后进先出

入栈：在栈顶插入元素。

出栈：在栈顶删除元素。

1.2 栈的使用

如下图，栈的常用方法有：

检查栈是否为空的意思是，看看栈里面是不是一个元素都没有。

栈的方法都挺简单，我就不一个个演示了，刷题的时候直接用即可


import java.util.Stack;
 
public class Main {
    public static void main(String[] args) {
        //创建一个栈
        Stack<Integer> stack = new Stack<>();
        //入栈
        stack.push(1);
        //看看栈顶元素但不删除
        int top = stack.peek();
        System.out.println(top);
        //删除栈顶元素
        stack.pop();
        //如果栈不为空，就看看栈里有几个元素
        if (!stack.empty()) {
            int size = stack.size();
            System.out.println(size);
        }
    }
}

1.3 栈的模拟实现

既然要实现一个栈，那我们可以先定义一个 MyStack 类，接下来只需要思考怎么完成 MyStack 类即可。

之前也说过，栈的底层是由一个数组实现的，所以我们可以定义一个数组，对栈进行操作就是对数组进行操作。

为了以后方便操作数组，我们还可以再定义一个 usedSize ，用来表示数组当前存放的元素个数。

因为我们待会还要提供 MyStack 的构造方法，就相当于给数组分配内存，所以我们可以定义一个默认容量，用来表示数组一开始的容量大小。

有了默认容量，我们就可以把 MyStack 的构造方法给写出来了。

栈要实现以下方法：


    //入栈
    public void push(int val) {
 
    }
 
    //出栈
    public int pop() {
        return -1;
    }
 
    //返回栈顶元素
    public int peek() {
        return -1;
    }
 
    //判空
    public boolean empty() {
        return false;
    }
 
    //返回栈的元素个数
    public int size() {
        return 0;
    }

我们可以先挑最简单的实现，比如 empty 和 size。

我们先实现 empty 方法，很简单，就是看数组有没有元素咯，元素个数不为 0 ，说明栈不空。

再来实现 size 方法，这个也简单，直接返回数组元素个数就好啦。

再来实现 pop 方法，出栈，就是出栈顶元素，也就是把数组的最后一个元素给删掉，那就得先判断数组里有没有元素，根据这个再来进行删除。

usedSize-- ，之后入栈的时候会把原来的元素给覆盖掉，相当于是变相删除了这个元素

再来实现 peek 方法，这个和 pop 方法同理，只是瞄一眼栈顶元素，但是不用删除栈顶元素。

最后再来实现 push 方法，首先，你得看看数组满没满，满了就要扩容，然后再来放元素。


import java.util.Arrays;
 
public class MyStack {
    private int[] elem;
    private int usedSize;//表示当前数组存放元素个数
 
    private static final int DEFAULT_CAPACITY = 10;//数组的默认容量
 
    public MyStack() {
        this.elem = new int[DEFAULT_CAPACITY];
    }
 
    //判空
    public boolean empty() {
        return this.usedSize == 0;
    }
 
    //返回栈的元素个数
    public int size() {
        return this.usedSize;
    }
 
 
    //出栈
    public int pop() {
        //栈为空，删不了
        if (empty()) {
            return -1;
        }
        //栈不为空，删除
        int top = this.elem[this.usedSize - 1];
        usedSize--;
        return top;
    }
 
 
    //返回栈顶元素
    public int peek() {
        //栈为空
        if (empty()) {
            return -1;
        }
        return elem[usedSize - 1];
    }
 
    //入栈
    public void push(int val) {
        //数组满了，得扩容
        if (this.usedSize == this.elem.length) {
            //扩容
            this.elem = Arrays.copyOf(this.elem, this.elem.length * 2);
        }
        this.elem[usedSize] = val;
        usedSize++;
    }
 
}

1.4 栈的应用场景

1. 改变元素的序列

1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1

选C

2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（）。

A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA

选B。

20. 有效的括号

思路：直接遍历 s ，因为是看看括号是否匹配，可以利用栈来完成，所以直接让右括号来跟左括号匹配即可

分两种情况，如果是左括号，那就直接入栈

如果是右括号，那就匹配，匹配之前得看看栈是不是为空，如果为空，说明就不匹配

如果匹配了，那就出栈。

最后遍历完 s ，如果栈为空，说明全部匹配成功，返回 true。


class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            //左括号
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else {
                //右括号
                if (!stack.empty()) {
                    char top = stack.peek();
                    if (top == '(' && ch == ')' 
                        || top == '{' && ch == '}' 
                        || top == '[' && ch == ']') {
                        stack.pop();
                    } else {
                        return false;
                    }
                } else {
                    //栈为空，没有左括号
                    return false;
                }
            }
        }
        if (!stack.empty()) {
            return false;
        }
        return true;
    }
}

150. 逆波兰表达式求值

思路：利用栈来完成，遍历数组，如果遇到数字，那就放进栈里，如果遇到运算符，就弹出栈的两个元素，

第一个弹出的元素作为运算符的右操作数，第二个作为左操作数，将计算完的值放入栈中


class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            //运算符
            if (tokens[i].equals("+")
                    || tokens[i].equals("-")
                    || tokens[i].equals("*")
                    || tokens[i].equals("/")) {
                int b = stack.pop();
                int a = stack.pop();
                switch (tokens[i]) {
                    case "+":
                        stack.push(a + b);
                        break;
                    case "-":
                        stack.push(a - b);
                        break;
                    case "*":
                        stack.push(a * b);
                        break;
                    case "/":
                        stack.push(a / b);
                        break;
                }
            } else {
                //数字
                int tmp = Integer.parseInt(tokens[i]);
                stack.push(tmp);
            }
        }
        return stack.pop();
    }
}

JZ31 栈的压入、弹出序列

你平常怎么判断出栈顺序的，现在就怎么写这个方法，思路是差不多的。

思路：这题利用栈来完成，遍历 push 数组，用 j 遍历 pop 数组，先把元素放入栈里，然后如果栈不为空并且栈顶元素和 pop[ j ] 相同的话，那就出栈，然后 j 往后走。

最后看看栈是否为空，如果为空，说明全都匹配成功，就返回 true ，否则返回 false


import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pushV int整型一维数组
     * @param popV int整型一维数组
     * @return bool布尔型
     */
    public boolean IsPopOrder(int[] push, int[] pop) {
        int j = 0;
        Stack<Integer> stack = new Stack<>();
        //用i遍历push数组，j遍历pop数组，
        //将push数组的所有数字都放入栈中，然后再peek栈
        //如果peek栈的元素和pop数组的j下标元素相同
        //就将该元素出栈
        //遍历完i后，如果栈不是空的就返回false
        for (int i = 0; i < push.length; i++) {
            //入栈
            stack.push(push[i]);
            //匹配
            while (!stack.empty() && j < pop.length && stack.peek() == pop[j]) {
                stack.pop();
                j++;
            }
        }
        if (stack.empty()) {
            return true;
        }
        return false;
    }
}

155. 最小栈

思路：定义两个栈，一个就是普通的栈，一个用来存放有可能是最小值的元素的栈(简称最小栈)

构造方法就是初始化这两个栈，

push 方法，那就得判断是不是第一次入栈，如果是第一次入栈，那就两个栈都要入，如果不是第一次，那就普通栈正常入栈，而最小栈就需要判断一下，如果要入的 val 小于等于最小栈的栈顶元素，那就入栈。

pop 方法，得看看是不是空栈，空栈出不了。如果栈不为空，那普通栈就正常出栈，但是得看看普通栈出的元素在最小栈中是否存在，如果存在，那最小栈也得出。

top 方法，看看是不是空栈，不是就正常返回栈顶元素

getMin 方法也同理。


class MinStack {
    private Stack<Integer> stack;//一个是普通栈
    private Stack<Integer> minStack;//一个存有可能是最小值的栈
 
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
 
    public void push(int val) {
        stack.push(val);
        if (minStack.empty()) {
            //如果是第一次入栈，那么两个栈都得入
            minStack.push(val);
        } else {
            int tmp = minStack.peek();
            //如果val小于等于minStack栈顶元素，那就入栈
            if (val <= tmp) {
                minStack.push(val);
            }
        }
    }
 
    public void pop() {
        if (stack.empty()) {
            return;
        }
        int top = stack.pop();
        int tmp = minStack.peek();
        if (tmp == top) {
            //如果普通栈和最小栈元素相等，那就都得出栈
            //不是的话就普通栈出栈
            minStack.pop();
        }
    }
 
    //获取普通栈的栈顶元素
    public int top() {
        if (stack.empty()) {
            return -1;
        }
        return stack.peek();
    }
 
    //获取普通栈的栈顶元素
    public int getMin() {
        if (minStack.empty()) {
            return -1;
        }
        return minStack.peek();
    }
}

1.5 概念区分

栈、虚拟机栈、栈帧有什么区别呢？

栈：一种数据结构。

虚拟机栈：内存当中的一块区域下，创建局部变量等会在虚拟机栈上分配内存

栈帧：调用方法时在内存中开辟的一块空间。

2. 队列(Queue)

先进先出的一种结构

2.1 概念

队列：如上图，只能在队尾插入元素，队头删除元素，是一种特殊的线性表，遵循先进先出原则。

2.2 队列的使用

在Java中，Queue是个接口，底层是通过链表实现的，所以在创建对象的时候，必须实例化 LinkedList 对象。

Queue 的常见方法有：

跟栈的使用方式差不多，我就不演示啦

2.3 队列模拟实现

队列可以使用顺序结构或者链式结构实现，更推荐使用链式结构实现，因为简单

和栈同理，既然要实现队列，那就先定义一个 MyQueue 类。

同时，既然是使用链表实现，那肯定得定义一个静态内部类 ListNode。

而一个队列还有队头和队尾，所以也要定义队头和队尾。

因为要实现的方法里包含 isEmpty 方法，所以可以额外定义一个 usedSize 来记录队列的元素个数

队列要实现的方法有这些：


    public void offer(int val) {
        
    }
 
    //出队列 相当于删除队尾结点
    public int poll() {
        return -1;
    }
 
    //获取队头
    public int peek() {
        return -1;
    }
 
    public int getUsedSize() {
        return 0;
    }
 
    public boolean isEmpty() {
        return false;
    }

同样的，我们先选择简单的方法来实现，比如 getUsedSize 方法和 isEmpty 方法。

我们先实现 getUsedSize 方法，这个简单，直接返回 usedSize 就行。

再来实现 isEmpty 方法，判断队列是否为空，就是判断队列里usedSize是否为零。

再来实现 offer 方法，分两种情况，

一种是队列为空，说明链表里面还没有元素，也就是说新增的元素是第一个元素，所以就让 front 和 rear 都指向新增的元素即可。

第二种是队列不为空，相当于链表的头插法。

再来实现 poll 方法，

分两种情况，第一种，如果队列为空，删不了

第二种，队列不为空，就得判断，队列里面是否只有一个节点，如果只有一个节点，那删了队列就空了，如果不是只有一个节点，那就相当于删除尾巴节点。

最后实现 peek 方法，与 poll 方法类似，先看看空不空，不为空，就直接返回 top，为空，就返回 -1。


public class MyQueue {
    static class ListNode {
        private int val;
        private ListNode prev;
        private ListNode next;
 
        public ListNode(int val) {
            this.val = val;
        }
    }
 
    private ListNode front;//队头
    private ListNode rear;//队尾
 
    private int usedSize;
 
    public void offer(int val) {
        ListNode node = new ListNode(val);
        if (front == null) {
            front = node;
            rear = node;
        } else {
            //采用头插法
            front.prev = node;
            node.next = front;
            front = node;
        }
        usedSize++;
    }
 
    //出队列 相当于删除队尾结点
    public int poll() {
        //头插尾删
        if (rear == null) {
            return -1;
        } else if (front == rear) {
            //只有一个结点
            int ret = rear.val;
            front = null;
            rear = null;
            usedSize--;
            return ret;
        } else {
            int ret = rear.val;
            rear = rear.prev;
            rear.next = null;
            usedSize--;
            return ret;
        }
    }
 
    //获取队头
    public int peek() {
        if (rear == null) {
            return -1;
        }
        //因为是头插尾删，所以返回的是队尾元素
        return rear.val;
    }
 
    public int getUsedSize() {
        return usedSize;
    }
 
    public boolean isEmpty() {
        if (usedSize == 0) {
            return true;
        }
        return false;
    }
}

2.4 循环队列

如下图，就是一个循环队列。环形队列通常使用数组实现。

该怎么区分循环队列到底满没满？

1. 可以定义一个 usedSize，如果 usedSize == elem.length，说明满了

2. 可以定义一个 flag ，如果满了，就标记为 true

3. 可以浪费一个空间，来区分

一般用第三种方法，因为比较简单。

那么该怎么让数组变成一个循环数组呢？

622. 设计循环队列

首先，循环队列的底层是一个数组，所以我们要定义一个数组，并且把 front，rear 也一起定义上。

然后实现构造方法，因为我们选择浪费一个空间来区分循环队列满没满，所以我们要多初始化一个空间给数组，不然数组就放不下那么多元素了。

再来实现 isEmpty 方法 ，如下图，很明显，当 front == rear 的时候，队列为空。

再来实现 isFull 方法，因为浪费了一个空间来区分满没满，根据前面讲过的，如下图：

再来实现 front 和 rear 方法

先判断空不空，不为空就返回，为空就返回 -1，返回队尾元素的时候得注意 rear 下标，假如 rear 刚好为 0 ，index = rear - 1；这显然是不对的，他的上一个应该是 len - 1下标才对，所以得做判断。

再来实现 enQueue 方法，首先判断满没满，没满就插入，满了就返回 false

再来实现 deQueue 方法，先判断空不空，不空就出队头，空就返回.


class MyCircularQueue {
 
    public int elem[];
    public int front;
    public int rear;//队尾进元素，所以增加元素的时候，就放到 rear 下标即可
 
    public MyCircularQueue(int k) {
        //因为我们浪费了一个空间来区别队列满没满
        //所以要多初始化一个空间
        this.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;
        }
        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() {
        if (front == rear) {
            return true;
        }
        return false;
    }
 
    public boolean isFull() {
        if (((rear + 1) % elem.length) == front) {
            return true;
        }
        return false;
    }
}

3. 双端队列 (Deque)

双端队列，就是两边都能进行出队入队操作的队列。元素可以从队头出队和入队，也可以从队尾出队和入队。

Deque 也是一个接口，实例化的时候也要创建LinkedList的对象。

4. 练习题

225. 用队列实现栈

思路：可以使用两个队列实现，只有当两个队列都为空的时候，栈才为空，因为队列是先进先出的结构，而栈是先进后出的结构，所以出栈的时候，就得出不为空的队列，将不为空的队列的所有元素出队放到另一个队列里，最后再出一次队即可，而入栈的时候也同理，就把元素放到不为空的队列里。


class MyStack {
    private Queue<Integer> qu1;
    private Queue<Integer> qu2;
 
    public MyStack() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }
 
    public void push(int x) {
        //入栈的时候入到不为空的队列里
        if (empty()) {
            qu1.offer(x);
        } else {
            if (!qu1.isEmpty()) {
                qu1.offer(x);
            }
            if (!qu2.isEmpty()) {
                qu2.offer(x);
            }
        }
 
    }
 
    public int pop() {
        if (empty()) {
            return -1;//栈为空
        }
        if (!qu1.isEmpty()) {
            int cnt = qu1.size() - 1;
            while (cnt != 0) {
                int tmp = qu1.poll();
                qu2.offer(tmp);
                cnt--;
            }
            return qu1.poll();
        }
        int cnt = qu2.size() - 1;
        while (cnt != 0) {
            int tmp = qu2.poll();
            qu1.offer(tmp);
            cnt--;
        }
        return qu2.poll();
    }
 
    public int top() {
        if (empty()) {
            return -1;
        }
        int tmp = 0;
        if (!qu1.isEmpty()) {
            int cnt = qu1.size();
            while (cnt != 0) {
                tmp = qu1.poll();
                qu2.offer(tmp);
                cnt--;
            }
            return tmp;
        }
        int cnt = qu2.size();
        while (cnt != 0) {
            tmp = qu2.poll();
            qu1.offer(tmp);
            cnt--;
        }
        return tmp;
    }
 
    public boolean empty() {
        //两个队列都为空表示栈为空
        if (qu1.isEmpty() && qu2.isEmpty()) {
            return true;
        }
        return false;
    }
}

232. 用栈实现队列

思路：利用两个栈来实现，假设一个叫 stack1，一个叫 stack2，简称 s1 和 s2。

固定入队就入 s1 ，出队首先判断队列是不是空，如果不是空，就出 s2，如果 s2 没元素，那就将 s1 的元素全部出到 s2 里，然后 s2 再来出栈。peek 也同理，只有当两个栈为空的时候，队列才为空。


class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
 
    public MyQueue() {
        stack1 = new Stack<>();//s1用来做输入栈
        stack2 = new Stack<>();//s2用来做输出栈
    }
 
    public void push(int x) {
        stack1.push(x);
    }
 
    public int pop() {
        if (empty()) {
            return -1;
        }
        if (stack2.empty()) {
            int size = stack1.size();
            while (size != 0) {
                int tmp = stack1.pop();
                stack2.push(tmp);
                size--;
            }
            return stack2.pop();//是top元素
        }
        return stack2.pop();//如果s2不为空，说明之前已经按顺序弹出元素了
    }
 
    public int peek() {
        if (empty()) {
            return -1;
        }
        if (stack2.empty()) {
            int size = stack1.size();
            while (size != 0) {
                int tmp = stack1.pop();
                stack2.push(tmp);
                size--;
            }
            return stack2.peek();//是top元素
        }
        return stack2.peek();
    }
 
    public boolean empty() {
        if (stack1.empty() && stack2.empty()) {
            return true;
        }
        return false;
    }
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/868991