【数据结构】队列-Queue

客官°小女子只卖身不卖艺 2024-04-23 20:29 5阅读 0赞

> ⭐ 作者：小胡\_不糊涂  
> 🌱 作者主页：[小胡\_不糊涂的个人主页][Link 1]  
> 📀 收录专栏：[浅谈数据结构][Link 2]  
> 💖 持续更文，关注博主少走弯路，谢谢大家支持 💖

#### 队列 ####

*  1.什么是队列
 *  2. 队列的使用
 *  3. 队列的模拟实现
 *  4. 循环队列
 *  5. 双端队列(Deque)

![在这里插入图片描述][60da9afe2d2347bc92b0f1081848462c.gif_pic_center]

## 1.什么是队列 ##

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

![在这里插入图片描述][ceaa1345358f4e08b4242cbb1a9db13f.png]

## 2. 队列的使用 ##

在Java中，Queue是个接口，底层是通过链表实现的：  
![在这里插入图片描述][60f442133908493db8ff7464e1528e6b.png]

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>功能</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>boolean offer(E e)</td> 
   <td>入队列</td> 
  </tr> 
  <tr> 
   <td>E poll()</td> 
   <td>出队列</td> 
  </tr> 
  <tr> 
   <td>peek()</td> 
   <td>获取队头元素</td> 
  </tr> 
  <tr> 
   <td>int size()</td> 
   <td>获取队列中有效元素个数</td> 
  </tr> 
  <tr> 
   <td>boolean isEmpty()</td> 
   <td>检测队列是否为空</td> 
  </tr> 
 </tbody> 
</table>

`Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。`

上述方法的实现：

import java.util.LinkedList;
    import java.util.Queue;
    public class Main {
        
        //方法的实现
        public static void main(String[] args) {
        
            Queue<Integer> q = new LinkedList<>();
            q.offer(1);
            q.offer(2);
            q.offer(3);
            q.offer(4);
            q.offer(5); // 从队尾入队列
            System.out.println(q.size());
            System.out.println(q.peek()); // 获取队头元素
            q.poll();
            System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回
            if(q.isEmpty()){
        
                System.out.println("队列空");
            }else{
        
                System.out.println(q.size());
            }
        }
    }

## 3. 队列的模拟实现 ##

我们知道队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过线性表可以了解到常见的空间类型有两种：**顺序结构**和**链式结构**。

![在这里插入图片描述][9e6c8f6829c341daa083c1c1eb947bfb.png]  
模拟实现队列：

public class MyQueue {
        
        //双向链表节点
        static class ListNode {
        
            public int val;
            public ListNode next;
            public ListNode prev;
    
            public ListNode(int val) {
        
                this.val = val;
            }
        }
    
        public ListNode head;//队头
        public ListNode last;//队尾
        public int usedSize;//队列元素个数
    
        // 入队列---向双向链表位置插入新节点
        public boolean offer(int val) {
        
            ListNode node = new ListNode(val);
            if(head == null) {
        
                head = node;
                last = node;
            }else {
        
                last.next = node;
                node.prev = last;
                last = last.next;
            }
            usedSize++;
            return true;
        }
    
        // 出队列---将双向链表第一个节点删除掉
        // 1. 队列为空
        // 2. 队列中只有一个元素----链表中只有一个节点---直接删除
        // 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
        public int poll() {
        
            if(head == null) {
        
                return -1;
            }
            int retVal = head.val;
            if(head.next == null) {
        
                head = null;
                last = null;
                return retVal;
            }
            head = head.next;
            head.prev = null;//第一个节点删除
            usedSize--;
            return retVal;
        }
    
        // 获取队头元素---获取链表中第一个节点的值域
        public int peek() {
        
            if(head == null) {
        
                return -1;
            }
            return head.val;
        }
    
        public boolean empty() {
        
            return head == null;
        }
    
        public int size() {
        
            return usedSize;

## 4. 循环队列 ##

循环队列顾名思义就是首位相连的队列，自然界中的生产者消费者分解者模型可以使用循环队列来描述。而环形队列通常使用数组实现。  
![在这里插入图片描述][4c7a0aa350c4402c947c10ee19e34d3d.png]  
**数组下标循环的小技巧**

1.  下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length  
    ![在这里插入图片描述][4fdbb351c24842d5a6e54804257c3544.png]
2.  下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) %array.length  
    ![在这里插入图片描述][3181430108054c99b16e5456c8b77266.png]

> 如何区分空与满？
> 
> 1.  通过添加 size 属性记录
> 2.  保留一个位置
> 3.  使用标记  
>     ![在这里插入图片描述][70f072aa05eb4bc6a8fd96b42e81cc46.png]

**循环队列的实现：**

class MyCircularQueue {
        
        public int[] elem;
        public int front;//队头
        public int rear;//队尾
        
        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;
            }
            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 front == rear;
        }
    
        public boolean isFull() {
        
            return (rear+1)%elem.length == front;
        }
    }

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

> \*\*双端队列（deque）\*\*是指允许两端都可以进行入队和出队操作的队列。![在这里插入图片描述][d481bb25500542c08895996abb7a4fb4.png]  
> Deque是一个接口，使用时必须创建LinkedList的对象:

![在这里插入图片描述][ea49766603034207ae855814cea37f77.png]  
在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口:

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

[Link 1]: https://blog.csdn.net/iLoyo_
[Link 2]: http://t.csdnimg.cn/pu3jy
[60da9afe2d2347bc92b0f1081848462c.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/e61ee00b74c4412cad656b9e7de3c840.gif
[ceaa1345358f4e08b4242cbb1a9db13f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/8547e89a1b514d0287dd1783a487b261.png
[60f442133908493db8ff7464e1528e6b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/1adfaaabcbc54395860518d6b52a8f77.png
[9e6c8f6829c341daa083c1c1eb947bfb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/d23a6d9607584f12bca6e4f9aedc318e.png
[4c7a0aa350c4402c947c10ee19e34d3d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5f9afad178374c11bf8b95876ccebfd2.png
[4fdbb351c24842d5a6e54804257c3544.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/4ff2719b3caa4d48820fff7a3a08418a.png
[3181430108054c99b16e5456c8b77266.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/ac247fbd3f3a4590a04426bb2e95529c.png
[70f072aa05eb4bc6a8fd96b42e81cc46.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/b25472be2d1d4bfeb08364bfd359fc6c.png
[d481bb25500542c08895996abb7a4fb4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/3c0b441e442043a78de557df2b99e003.png
[ea49766603034207ae855814cea37f77.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5d8aad0b70b5469e9c1ea0641da8e986.png