Java栈和队列·下

╰+哭是因爲堅強的太久メ 2024-04-28 07:36 66阅读 0赞

#### Java栈和队列·下 ####

*  2. 队列(Queue)
 *   *  2.1 概念
     *  2.2 实现
     *  2.3 相似方法的区别
     *  2.4 循环队列
 *  3. 双端队列 (Deque)
 *   *  3.1 概念
 *  4.java中的栈和队列
 *  5. 栈和队列面试题

**大家好，我是晓星航。今天为大家带来的是 Java栈和队列·下 的讲解！?**

**继上一个讲完的栈后，我们这次开始讲解队列！**

## 2. 队列(Queue) ##

### 2.1 概念 ###

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有**先进先出**FIFO(First In First Out) 入队列：进行插入操作的一端称为**队尾（Tail/Rear）** 出队列：进行删除操作的一端称为**队头（Head/Front）**

![202303161944396.png][]

在idea中看Queue(队列的底层逻辑代码)时 按下 alt + 7 可以查看它包含的所有方法：

![202303161945146.png][]

### 2.2 实现 ###

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

![202303161945310.png][] ![202303161946484.png][] ![202303161946413.png][] ![202303161946457.png][] ![202303161946311.png][]

class Node {
        
        public int val;
        public Node next;
        public Node(int val) {
        
            this.val = val;
        }
    
    }
    public class MyQueue {
        
        public Node head;
        public Node last;
    
        /**
         * 尾插法
         * @param val
         */
        public void offer(int val) {
        
            Node node = new Node(val);
            if (head == null) {
        
                head = node;
                last = node;
            } else {
        
                last.next = node;
                last = last.next;
            }
        }
    
        public int poll() {
        
            if (isEmpty()) {
        
                throw new RuntimeException("队列为空");
            }
            int oldVal = head.val;
            head = head.next;
            return oldVal;
        }
        public boolean isEmpty() {
        
            return this.head == null;
        }
    
        public int peek() {
        
            if (isEmpty()) {
        
                throw new RuntimeException("队列为空");
            }
            return head.val;
        }
    
    }

下面为测试代码：

public class TestDemo {
        
        public static void main(String[] args) {
        
            MyQueue queue = new MyQueue();
            queue.offer(1);
            queue.offer(2);
            queue.offer(3);
            System.out.println(queue.peek());
            System.out.println(queue.poll());
            System.out.println(queue.poll());
            System.out.println(queue.poll());
            System.out.println(queue.poll());
        }

![202303161947146.png][]

> Queue中方法总结：  
> **add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常  
> remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常  
> element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常  
> offer 添加一个元素并返回true 如果队列已满，则返回false  
> poll 移除并返问队列头部的元素 如果队列为空，则返回null  
> peek 返回队列头部的元素 如果队列为空，则返回null  
> put 添加一个元素 如果队列满，则阻塞  
> take 移除并返回队列头部的元素**

### 2.3 相似方法的区别 ###

1、add()和offer()区别:

add()和offer()都是向[队列][Link 1]中添加一个元素。一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，调用 add() 方法就会抛出一个 unchecked 异常，**而调用 offer() 方法会返回 false。因此就可以在程序中进行有效的判断**！

2、poll()和remove()区别：

remove() 和 poll() 方法都是从队列中删除第一个元素。如果队列元素为空，调用remove() 的行为与 Collection 接口的版本相似会抛出异常，**但**是新的 \*\*poll() 方法在用空集合调用时只是返回 null。\*\*因此新的方法更适合容易出现异常条件的情况。

3、element() 和 peek() 区别：

element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，**而 peek() 返回 null。**

### 2.4 循环队列 ###

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。

![202303161948328.png][]

**数组下标循环的小技巧**

1.  1.  下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length

![202303161948187.png][]

1.  下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length

![202303161948585.png][]

**如何区分空与满**

![202303161948561.png][]

1.  通过添加 size 属性记录 使用size和数组长度比较，确定满或者空

![202303161949510.png][]

1.  使用标志位flag，最开始falg = false，
    
    入队列时，每放一个元素，falg就置为true
    
    出队列时，每出一个元素，falg就置为false
    
    当front和rear相遇时，falg为true则队列为满，falg为false则队列为空。

![202303161950029.png][]

1.  浪费一个格子来区分空和满，每次存放元素之前，都先检查一下rear的下一个是不是front。如果是，那么就是满的

空：frontNext == rear

满：rearNext == front

![202303161950610.png][] ![202303162006322.png][]

## 3. 双端队列 (Deque) ##

### 3.1 概念 ###

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

双端队列的所有方法：

![202303161950298.png][]

## 4.java中的栈和队列 ##

![202303161951828.png][] ![202303161951600.png][]

栈的方法：

![202303161951682.png][]

普通队列方法：

![202303161951296.png][]

双端队列方法：

![202303161952415.png][] ![202303162007604.png][]

## 5. 栈和队列面试题 ##

1.  括号匹配问题。[OJ链接][OJ]

![202303161954840.png][]

import java.util.Stack;
    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()) {
        
                        //右括号多
                        System.out.println("右括号多！");
                        return false;
                    }
                    char top = stack.peek();
                    if (top == '(' && ch == ')' || top == '[' && ch == ']' || top == '{' && ch == '}') {
        
                        //如果左括号和右括号匹配 则弹出这个左括号
                        stack.pop();
                    } else {
        
                        //左右括号不匹配
                        System.out.println("左右括号不匹配");
                        return false;
                    }
                }
            }
            if (!stack.empty()) {
        
                //左括号多
                System.out.println("左括号多！");
                return false;
            }
            return true;
        }
    }

题目描述的很清楚，左右括号如果不匹配，无非是以下几种情况：

1、左括号多余右括号

2、右括号多余左括号

3、左右括号顺序不想匹配

在使用代码将这几种情况考虑完全后，便可轻易通过测试。

思路如下：

如果是左括号我们直接使其进栈，如果是右括号我们先判断右括号是否比左括号多，再看其是否相匹配，匹配则弹出相对应的左括号继续下一个括号的判断，如果不匹配则返回不匹配错误，在右括号全部判断完毕后，我们判断一下栈此时是否为空，如果为空则我们所有的括号都匹配成功即正确，如果不为空则是左括号比右括号要多，我们就返回false。

![202303161954884.png][]

1.  用队列实现栈。[OJ链接][OJ 1]

![202303162002855.png][] ![202303162003698.png][]

public class MyStack {
        
        private Queue<Integer> qu1;
        private Queue<Integer> qu2;
        public MyStack() {
        
            qu1 = new LinkedList<>();
            qu2 = new LinkedList<>();
        }
    
        public void push(int x) {
        
            if (!qu1.isEmpty()) {
        
                qu1.offer(x);
            } else if (!qu2.isEmpty()){
        
                qu2.offer(x);
            } else {
        
                qu1.offer(x);
            }
        }
    
        public int pop() {
        
            if (empty()) {
        
                return -1;
            }
            if (!qu1.isEmpty()) {
        
                int size = qu1.size();
                for (int i = 0; i < size - 1; i++) {
        
                    int val = qu1.poll();
                    qu2.offer(val);
                }
                return qu1.poll();
            }
            if (!qu2.isEmpty()) {
        
                int size = qu2.size();
                for (int i = 0; i < size - 1; i++) {
        
                    int val = qu2.poll();
                    qu1.offer(val);
                }
                return qu2.poll();
            }
            return -1;
        }
    
        public int top() {
        
            if (empty()) {
        
                return -1;
            }
            if (!qu1.isEmpty()) {
        
                int val = -1;
                int size = qu1.size();
                for (int i = 0; i < size; i++) {
        
                    val = qu1.poll();
                    qu2.offer(val);
                }
                return val;
            }
            if (!qu2.isEmpty()) {
        
                int val = -1;
                int size = qu2.size();
                for (int i = 0; i < size; i++) {
        
                    val = qu2.poll();
                    qu1.offer(val);
                }
                return val;
            }
            return -1;
        }
    
        public boolean empty() {
        
            return qu1.isEmpty() && qu2.isEmpty();
        }
    }

1、入栈的时候，入到不为空的队列，刚开始都为空指定入到一个队列。

2、出栈的时候，找到不为空的队列，出size-1个元素到另一个队列，剩下这个元素就是出栈的元素。

注意：这里有一个小问题我们很容易疏忽，就是在使用top和pop方法进行移动时我们qu1和qu2中的元素个数时变化的，因此我们的qu1.size() qu2.size()也会跟着变化，为了避免这个情况，我们在for循环的外面自己定义一个Int size = qu1.size(); int size = qu2.size();在之后的for循环中我们只需要让i小于size即可，此时的size就不是一个会变动的值了。

![202303162003217.png][]

1.  用栈实现队列。[OJ链接][OJ 2]

![202303162003395.png][] ![202303162003058.png][]

class MyQueue {
        
    
        public Stack<Integer> stack1;
        public Stack<Integer> stack2;
        public MyQueue() {
        
            stack1 = new Stack<>();
            stack2 = new Stack<>();
        }
    
        public void push(int x) {
        
            stack1.push(x);
        }
    
        public int pop() {
        
            if (empty()) {
        
                return -1;
            }
            if (stack2.empty()) {
        
                while (!stack1.isEmpty()) {
        
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    
        public int peek() {
        
            if (empty()) {
        
                return -1;
            }
            if (stack2.empty()) {
        
                while (!stack1.isEmpty()) {
        
                    stack2.push(stack1.pop());
                }
            }
            return stack2.peek();
        }
    
        public boolean empty() {
        
            return stack1.isEmpty() && stack2.isEmpty();
        }
    }

思路：1、入队的时候，统一入到第1个栈

2、出队的时候，同一出第2个栈里面的元素，如果第2个为空，那么把第一个栈里面所有的元素，全部倒过来，然后再出栈顶的元素。

![202303162004988.png][]

1.  实现一个最小栈。[OJ链接][OJ 3]

![202303162004929.png][] ![202303162004550.png][]

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()) {
        
                int top = minStack.peek();
                //比较 小于等于的话 也要放进来
                if (val <= top) {
        
                    minStack.push(val);
                }
            } else {
        
                minStack.push(val);
            }
        }
    
        public void pop() {
        
            int popVal = stack.pop();
            if (!minStack.empty()) {
        
                int top = minStack.peek();
                if (top == popVal) {
        
                    minStack.pop();
                }
            }
        }
    
        public int top() {
        
            return stack.peek();
        }
    
        public int getMin() {
        
            return minStack.peek();
        }
    }

思路：这里我们采取了使用两个栈(一个普通栈 一个最小栈)来比较的方法，例如我们在push元素时，普通栈我们是直接放进去的，而最小栈我们则是通过比较，如果要放的元素比我们最小栈栈顶的元素小或等于我们便在最小栈也放入一份。

在pop弹出栈顶元素时我们同样是直接弹出普通栈的栈顶元素，然后比较这个弹出的元素和最小栈栈顶元素的大小是否相等，如果相等我们则还需要再pop一次最小栈的栈顶元素。

top方法和我们stack栈中的peek方法一样，我们直接返回stack的peek方法即可。

getMin方法是返回栈中最小元素，我们这里有两个栈，而最小栈的原理就是将最小的元素通过压栈(头插)的方式进入最小栈，因此我们最小栈的最小值永远是栈顶的元素，我们直接返回最小栈的栈顶元素即可。

![202303162005379.png][]

1.  设计循环队列。[OJ链接][OJ 4]

![202303162005333.png][] ![202303162005547.png][]

class MyCircularQueue {
        
        public int[] elem;
        public int front;//队头下标
        public int rear;//队尾下标
        public MyCircularQueue(int k) {
        
            this.elem = new int[k + 1];
        }
    
        /**
         * 入队操作
         * @param value
         * @return
         */
        public boolean enQueue(int value) {
        
            if (isFull()) {
        
                return false;
            }
            this.elem[rear] = value;
            //rear++;
            rear = (rear + 1) % elem.length;
            return true;
        }
    
        /**
         * 出队操作
         * @return
         */
        public boolean deQueue() {
        
            if (isEmpty()) {
        
                return false;
            }
            front = (front + 1) % elem.length;
    
            return true;
        }
    
        /**
         * 得到队头元素
         * @return
         */
        public int Front() {
        
            if (isEmpty()) {
        
                return -1;
            }
            return elem[front];
        }
    
        public int Rear() {
        
            if (isEmpty()) {
        
                return -1;
            }
            int index = -1;
            if (rear == 0) {
        
                index = elem.length - 1;
            } else {
        
                index = rear - 1;
            }
            return elem[index];
        }
    
        public boolean isEmpty() {
        
            return front == rear;
        }
    
        public boolean isFull() {
        
            //rear的下一个是front
            if ((this.rear + 1) % elem.length == front) {
        
                return true;
            }
            return false;
        }
    }

解答思路：我们这里的数组元素为k个，但是所能用的位置只有k-1个，为了满足题目要求我们将数组大小改为了k+1，故我们所能用的元素变为了k个。这里因为我们是循环队列，因此当数组为空时，或者数组占满时我们的front和rear是相等的，为了避免数组占满，而要计算rear要循环回我们的首元素地址0时，我们采取了rear = (rear + 1) % elem.length的操作，如果rear的下标已经时数组下标的最大值，再加1就会自动归为首元素的下标0。

![202303162005408.png][] ![202303162008652.png][]

*感谢各位读者的阅读，本文章有任何错误都可以在评论区发表你们的意见，我会对文章进行改正的。如果本文章对你有帮助请动一动你们敏捷的小手点一点赞，你的每一次鼓励都是作者创作的动力哦！?*

[202303161944396.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/73ee4985d9e2450eb90f933ffe06bb5d.png
[202303161945146.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/ae05f20e9c8749688c1c3d2637f91abd.png
[202303161945310.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303161945310.png
[202303161946484.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303161946484.png
[202303161946413.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303161946413.png
[202303161946457.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303161946457.png
[202303161946311.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/200321f627ee47ed89e9f6d7deb07095.png
[202303161947146.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/88a9320a7a554993882d3d0a3ef9d8ad.png
[Link 1]: https://so.csdn.net/so/search?q=%E9%98%9F%E5%88%97&spm=1001.2101.3001.7020
[202303161948328.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/462d970e1f19411bb877b86944e7d39b.png
[202303161948187.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/2a4d0af416b24d78bbece5dbb13e0241.png
[202303161948585.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/298ede7cccc14d79a11a27f41e92782c.png
[202303161948561.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/62b42bdf66864c88a9577b6601de6eb8.png
[202303161949510.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/1ddf49ab9c614ff6ad1576d2b41218f4.png
[202303161950029.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/b3138de3b3024f9b9f9e4d16019bc6ac.png
[202303161950610.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303161950610.png
[202303162006322.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/d66f93a3607245d29d5050c5bf39cbf4.png
[202303161950298.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/bd0cd4bfb71c4b5a846d455b3058a11f.png
[202303161951828.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303161951828.png
[202303161951600.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/08598b9a65ae4c5f8e6a4924e40a0aaa.png
[202303161951682.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/1d352dcdcfde46f48057c9b049933305.png
[202303161951296.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/0fec71dae24d4776b1cda60088945102.png
[202303161952415.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303161952415.png
[202303162007604.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/96b8f3706336442482b272c56224ecd4.png
[OJ]: https://leetcode.cn/problems/valid-parentheses/
[202303161954840.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/9a20d3307e8d41268f9feae92cae457d.png
[202303161954884.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/e5be114a274143289dc222d1f54c6f47.png
[OJ 1]: https://leetcode.cn/problems/implement-stack-using-queues/
[202303162002855.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303162002855.png
[202303162003698.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/c8c4e20782884fa2bcce49be9a47c270.png
[202303162003217.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/da0f727aef864d6fbdca20da355fc779.png
[OJ 2]: https://leetcode.cn/problems/implement-queue-using-stacks/
[202303162003395.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303162003395.png
[202303162003058.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/6fb2d61c7c9f4309a403db74582c24c6.png
[202303162004988.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/cf18ffacfaf9442eb1e06a3565309247.png
[OJ 3]: https://leetcode.cn/problems/min-stack/
[202303162004929.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303162004929.png
[202303162004550.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/3e5c2ea035834ba8a8472be2dd591a0d.png
[202303162005379.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/871f5fb0ecee459f9400f1a5fe9ece93.png
[OJ 4]: https://leetcode.cn/problems/design-circular-queue/
[202303162005333.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303162005333.png
[202303162005547.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/0e5ea416303e4ba4bb7ed769f9a64460.png
[202303162005408.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303162005408.png
[202303162008652.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/147fbe80d08a471cb9625dc570d0653a.png