数据结构之队列（Queue）

冷不防 2023-09-28 05:22 134阅读 0赞

**目录**

1.队列（Queue）之概念

2.队列（Queue）之模拟实现

3.队列（Queue）之使用

4.队列（Queue）之循环队列

5.队列（Queue）之双端队列(Deque)

6.力扣中的练习题

6.1 用队列实现栈

6.2 用栈实现队列

6.3 最小栈

--------------------

## 1.队列（Queue）之概念 ##

> **定义：****队列是一种特殊的线性表，它只允许在一端进行插入（队尾）数据操作，在另一端进行删除（队头）数据操作。**
> 
> **队列具有****先进先出****的特点**
> 
> **队列的实现也是有两种方式**
> 
> **数组实现，链表实现**

![9b1d4a06642b406ba993ebccea14f02e.png][]

--------------------

## 2.队列（Queue）之模拟实现 ##

以单链表实现，并且做一点改动

![440ab0fd4ef843fe957ce3f18eabebc7.png][]

**先写一个上面这样结构的单链表**

static class Node {
            public int val;
            public Node next;
            public Node(int val) {
                this.val = val;
            }
        }
        public Node head;//队列头
        public Node tail;//队列尾

**（1）入队offer()**

public void offer(int val) {
            Node node = new Node(val);
            if (head == null) {
                head = node;
                tail = node;
            }else {
                tail.next = node;
                tail = tail.next;
            }
        }

**（2）出队poll()**

public int poll() {
            if(head == null) {
                return -1;
            }
            int oldVal = head.val;
            if (head.next == null) {
                head = tail = null;
            }else {
                head = head.next;
            }
            return oldVal;
        }

**（3）查看当前对头元素peek()**

public int peek() {
            if(head == null) {
                return -1;
            }
            return head.val;
        }

--------------------

## 3.队列（Queue）之使用 ##

![e9cc45c8b6d3477797a3bb5cd55a64e4.png][]

public static void main(String[] args) {
            java.util.Queue<Integer> queue = new LinkedList<>();
            queue.offer(1);
            queue.offer(5);
            queue.offer(7);
            queue.offer(45);
            System.out.println(queue.size());
            System.out.println(queue.peek());
            queue.poll();
            System.out.println(queue.poll());
        }

--------------------

## 4.队列（Queue）之循环队列 ##

**先看顺序队列中元素的入队出队操作，因为队列元素出队是在对头，**

**那也就是，队列中所有元素的移动都是在向前移动，而这样向前移动就会出现这样的问题**

![914ffe7cf8e547019d701b7d1a463c75.png][]

**所以，相对来说 对于****队列最好的方法是使用链表实现****，否则就会造成假溢出**

> **那么java中对于假溢出解决的办法是使用循环队列**

**正常情况下，顺序队列中会发生假溢出，也就是开辟的数组空间还有剩余空间，却因为rear越界表现为溢出，**

> **使用循环队列，就是将队列的首尾相连，这样rear移动到LENGTH时，就会再从0开始循环**

**1. 那么如何区分队列的空与满 因为当rear== front时，既表示空又表示满**

![186dba142bed4236a3d34763bed89aec.png][]

**（1）最直接的方法就是计数**

**（2）****牺牲一个存储空间** **front前面不存数据，当rear在front前面的时候就是满了（尾在头前就是满了）**

![a6738b624fbf4c7b807e1469b9c85b2d.png][]![f462b4352ceb4c3ea9fbf35094a9821d.png][]

**（3）** **是设置一个标志变量flag，****当front == rear,且flag = 0时为队列空，当front == rear,且flag= 1时为队列满**

**看一个练习题**

[链接622. 设计循环队列 - 力扣（LeetCode）][622. _ - _LeetCode]

**题目要求**  ![9d067ba7ca7f4febad6aa3b7653c59a6.png][]**分析一下**

**入队和出队除了要考虑队满和队空的条件，还要考虑，当这一圈转完，到下一圈，不能时不能只加加，还要模个数组长度，得出第二圈的下标**

**上代码**

class MyCircularQueue {
        public int[] elem;
        public int front;//队头下标
        public int rear;//队尾下标
    
        public MyCircularQueue(int k) {
            this.elem = new int[k+1];
        }
        //入队
        public boolean enQueue(int value) {
            if (isFull()) {
                return false;
            }
            this.elem[rear] = value;
            rear = (rear+1) % elem.length;
            return true;
        }
        //出队
        public boolean deQueue() {
            if (isEmpty()) {
                return false;
            }
            front = (front+1) % elem.length;//如果是K到0那就要%
            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() {
            return rear == front;
        }
        
        public boolean isFull() {
            return (rear+1) % elem.length == front;
        }
    }

--------------------

## 5.队列（Queue）之双端队列(Deque) ##

> **双端队列（Deque）是指在两端都可以进行入队和出队的操作的队列**
> 
> **不过需要注意的是，不能将一个数据，在一端进行入队和出队操作，不然这样就成了栈**

![2e5cf30c868c4f87abd7b49a6f78b667.png][] ![a2fb6750f87c4c39a876d7e85f1db8bf.png][]

Deque是一个接口，使用时必须要创建LinkedList的对象

Deque<Integer> myQueue2 = new LinkedList<>();

--------------------

## 6.力扣中的练习题 ##

### 6.1 用队列实现栈 ###

**链接** [225. 用队列实现栈 - 力扣（LeetCode）][225. _ - _LeetCode]

**题目要求**

![9fa99bbc2cf2431eb6a756788a98a503.png][]

**分析一下**

![c451b109fee94d729caa037ba048f3aa.png][]

**上代码**

class MyStack {
        Queue<Integer> qu1;
        Queue<Integer> qu2;
        public int usedSize;
        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);
            }
            usedSize++;
        }
        
        public int pop() {
            if(empty()) {
                return -1;
            }
            if(!qu1.isEmpty()) {
                int curSize = qu1.size();
                for(int i = 0; i < curSize-1; i++) {
                    qu2.offer(qu1.poll());
                }
                usedSize--;
                return qu1.poll();
            }else {
                int curSize = qu2.size();
                for(int i = 0; i < curSize-1; i++) {
                    qu1.offer(qu2.poll());
                }
                usedSize--;
                return qu2.poll();
            }
    
        }
        
        public int top() {
              if(empty()) {
                return -1;
            }
            if(!qu1.isEmpty()) {
                int curSize = qu1.size();
                int ret = -1;
                for(int i = 0; i < curSize; i++) {
                    ret = qu1.poll();
                    qu2.offer(ret);
                }
                return ret;
            }else {
                int curSize = qu2.size();
                int ret = -1;
                for(int i = 0; i < curSize; i++) {
                     ret = qu2.poll();
                    qu1.offer(ret);
                }
                return ret;
            }
        }
        
        public boolean empty() {
            return usedSize == 0;
        }
    }

--------------------

### 6.2 用栈实现队列 ###

**链接** [232. 用栈实现队列 - 力扣（LeetCode）][232. _ - _LeetCode]

**题目要求**

![745cdb21abbd4bf1bd4380c43cb75773.png][]

**分析一下**

![da6154fbcd98433690f9eb4f5b87b263.png][]

**上代码**

class MyQueue {
        Stack<Integer> s1;
        Stack<Integer> s2;
        public MyQueue() {
            s1 = new Stack<>();
            s2 = new Stack<>();
        }
        
        public void push(int x) {
            s1.push(x);
        }
        
        public int pop() {
            if(empty()) {
                return -1;
            }
            if(s2.empty()) {
                //将s1中所有元素倒过来
                while(!s1.empty()) {
                    s2.push(s1.pop());
                }
            }
            return s2.pop();
        }
        
        public int peek() {
            if(empty()) {
                return -1;
            }
            if(s2.empty()) {
                //将s1中所有元素倒过来
                while(!s1.empty()) {
                    s2.push(s1.pop());
                }
            }
            return s2.peek();
        }
        
        public boolean empty() {
            return s1.empty() && s2.empty();
        }
    }

### 6.3 最小栈 ###

**链接** [155. 最小栈 - 力扣（LeetCode）][155. _ - _LeetCode]

**题目要求**

![713dc1a48b7f4ae0ab7a6ffc61042562.png][]

**分析一下**

![4bf1634b739149efac4a247b86c1e58a.png][]

![822db8ceed76409087e0303df97e6a51.png][] **上代码**

class MinStack {
        private Stack<Integer> s;//普通栈
        private Stack<Integer> minStack;//最小栈
    
        public MinStack() {
            s = new Stack<>();
            minStack = new Stack<>();
        }
        
        public void push(int val) {
            s.push(val);
            if(minStack.empty()) {
                //最小栈为null，直接放
                minStack.push(val);
            }else {
                int peekV = minStack.peek();
                if(val <= peekV) {
                    minStack.push(val);
                }
            }
        }
        
        public void pop() {
                int popV = s.pop();
                int peekVMinS = minStack.peek();
                if(popV == peekVMinS) {
                    minStack.pop();
                }
        }
        
        public int top() {
                return s.peek();
        }
        
        public int getMin() {
                return minStack.peek();
        }
    }

--------------------

[9b1d4a06642b406ba993ebccea14f02e.png]: https://img-blog.csdnimg.cn/9b1d4a06642b406ba993ebccea14f02e.png
[440ab0fd4ef843fe957ce3f18eabebc7.png]: https://img-blog.csdnimg.cn/440ab0fd4ef843fe957ce3f18eabebc7.png
[e9cc45c8b6d3477797a3bb5cd55a64e4.png]: https://img-blog.csdnimg.cn/e9cc45c8b6d3477797a3bb5cd55a64e4.png
[914ffe7cf8e547019d701b7d1a463c75.png]: https://img-blog.csdnimg.cn/914ffe7cf8e547019d701b7d1a463c75.png
[186dba142bed4236a3d34763bed89aec.png]: https://img-blog.csdnimg.cn/186dba142bed4236a3d34763bed89aec.png
[a6738b624fbf4c7b807e1469b9c85b2d.png]: https://img-blog.csdnimg.cn/a6738b624fbf4c7b807e1469b9c85b2d.png
[f462b4352ceb4c3ea9fbf35094a9821d.png]: https://img-blog.csdnimg.cn/f462b4352ceb4c3ea9fbf35094a9821d.png
[622. _ - _LeetCode]: https://leetcode.cn/problems/design-circular-queue/
[9d067ba7ca7f4febad6aa3b7653c59a6.png]: https://img-blog.csdnimg.cn/9d067ba7ca7f4febad6aa3b7653c59a6.png
[2e5cf30c868c4f87abd7b49a6f78b667.png]: https://img-blog.csdnimg.cn/2e5cf30c868c4f87abd7b49a6f78b667.png
[a2fb6750f87c4c39a876d7e85f1db8bf.png]: https://img-blog.csdnimg.cn/a2fb6750f87c4c39a876d7e85f1db8bf.png
[225. _ - _LeetCode]: https://leetcode.cn/problems/implement-stack-using-queues/
[9fa99bbc2cf2431eb6a756788a98a503.png]: https://img-blog.csdnimg.cn/9fa99bbc2cf2431eb6a756788a98a503.png
[c451b109fee94d729caa037ba048f3aa.png]: https://img-blog.csdnimg.cn/c451b109fee94d729caa037ba048f3aa.png
[232. _ - _LeetCode]: https://leetcode.cn/problems/implement-queue-using-stacks/
[745cdb21abbd4bf1bd4380c43cb75773.png]: https://img-blog.csdnimg.cn/745cdb21abbd4bf1bd4380c43cb75773.png
[da6154fbcd98433690f9eb4f5b87b263.png]: https://img-blog.csdnimg.cn/da6154fbcd98433690f9eb4f5b87b263.png
[155. _ - _LeetCode]: https://leetcode.cn/problems/min-stack/
[713dc1a48b7f4ae0ab7a6ffc61042562.png]: https://img-blog.csdnimg.cn/713dc1a48b7f4ae0ab7a6ffc61042562.png
[4bf1634b739149efac4a247b86c1e58a.png]: https://img-blog.csdnimg.cn/4bf1634b739149efac4a247b86c1e58a.png
[822db8ceed76409087e0303df97e6a51.png]: https://img-blog.csdnimg.cn/822db8ceed76409087e0303df97e6a51.png