【数据结构】队列(Queue)与队列的模拟实现

谁借莪１个温暖的怀抱￠ 2024-04-17 10:33 64阅读 0赞

#### 文章目录 ####

*  ?队列(Queue)的概念
 *  ?队列的使用
 *  ?队列的模拟实现
 *   *  ?创建队列
     *  ?入队列
     *  ?出队列
     *  ?获取队头元素
     *  ?获取队列长度
     *  ?判断是否为空
     *  ?完整代码
 *  ?双端队列 (Deque)
 *  ⭕总结

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

## ?队列(Queue)的概念 ##

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有==先进先出FIFO(FirstIn First Out) ==入队列：

进行插入操作的一端称为队尾（Tail/Rear） 出队列：

进行删除操作的一端称为队头（Head/Front）  
![在这里插入图片描述][8096a4334a0c4004a45ebcd37791393b.png]

## ?队列的使用 ##

在Java中，Queue是个接口，底层是通过链表实现的。  
![在这里插入图片描述][2631bf06b12d416db5f84721fe5992a4.png]  
队列在使用时有以下方法：  
![在这里插入图片描述][b4f96696ae0249479a6f5947a614a899.png]  
***注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。***

使用如下：

import java.util.LinkedList;
    import java.util.Queue;
    
    public class TestMain {
        
        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());
            }
        }
    }

运行结果如下：  
![在这里插入图片描述][e93868f1fc2c470d9c14deb5d1de98b5.png]

## ?队列的模拟实现 ##

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

这里博主为大家演示一个双链表模拟实现队列

### ?创建队列 ###

其实就是创建一个双链表，这里就不做过多赘述了，实现如下：

public static class ListNode {
        
            ListNode next;
            ListNode prev;
            int value;
    
            ListNode(int value) {
        
                this.value = value;
            }
        }
    
        ListNode first; // 队头
        ListNode last; // 队尾
        int size = 0;

### ?入队列 ###

向双向链表位置插入新节点，做法如下：

*  创建一个节点newNode接收传进来的元素
 *  判断该队列是否为null
 *  若为null，则该元素就是队头
 *  若不为null，则将该元素的前驱节点设置为last；
 *  last的后继节点变为newNode
 *  newNode变为新的尾节点
 *  size++

实现如下：

// 入队列
        public void offer(int e) {
        
            ListNode newNode = new ListNode(e);
            if (first == null) {
        
                first = newNode;
    // last = newNode;
            } else {
        
                last.next = newNode;
                newNode.prev = last;
    // last = newNode;
            }
            last = newNode;
            size++;
        }

### ?出队列 ###

将双向链表第一个节点删除掉，做法如下：

*  分为几种情况
 *  当队列为空时
 *  则直接返回队列为空的异常，自定义异常如下

public class EmptyException extends RuntimeException{
        
        public EmptyException() {
        
        }
    
        public EmptyException(String message) {
        
            super(message);
        }
    }

*  当队列中只有一个元素----链表中只有一个节点时—直接删除
 *  当队列中有多个元素—链表中有多个节点----将第一个节点删除

实现如下：

// 出队列---将双向链表第一个节点删除掉
        public int poll() {
        
    // 1. 队列为空
    // 2. 队列中只有一个元素----链表中只有一个节点---直接删除
    // 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
            int value = 0;
            if (first == null) {
        
                throw new EmptyException("队列为空");
            } else if (first == last) {
        
                last = null;
                first = null;
            } else {
        
                value = first.value;
                first = first.next;
                first.prev.next = null;
                first.prev = null;
            }
            --size;
            return value;
        }

### ?获取队头元素 ###

获取链表中第一个节点的值域

*  若队列为null，抛出异常
 *  若不为null，返回队头的元素

实现如下：

// 获取队头元素---获取链表中第一个节点的值域
        public int peek() {
        
            if (first == null) {
        
                throw new EmptyException("队列为空");
            }
            return first.value;
        }

### ?获取队列长度 ###

直接返回size就好

实现如下：

public int size() {
        
            return size;
        }

### ?判断是否为空 ###

直接判断对头是否为null，然后返回就好

实现如下：

public boolean isEmpty(){
        
            return first == null;
        }

### ?完整代码 ###

MyQueue实现如下：

public class MyQueue {
        
        // 双向链表节点
        public static class ListNode {
        
            ListNode next;
            ListNode prev;
            int value;
    
            ListNode(int value) {
        
                this.value = value;
            }
        }
    
        ListNode first; // 队头
        ListNode last; // 队尾
        int size = 0;
    
        // 入队列---向双向链表位置插入新节点
        public void offer(int e) {
        
            ListNode newNode = new ListNode(e);
            if (first == null) {
        
                first = newNode;
    // last = newNode;
            } else {
        
                last.next = newNode;
                newNode.prev = last;
    // last = newNode;
            }
            last = newNode;
            size++;
        }
    
        // 出队列---将双向链表第一个节点删除掉
        public int poll() {
        
    // 1. 队列为空
    // 2. 队列中只有一个元素----链表中只有一个节点---直接删除
    // 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
            int value = 0;
            if (first == null) {
        
                throw new EmptyException("队列为空");
            } else if (first == last) {
        
                last = null;
                first = null;
            } else {
        
                value = first.value;
                first = first.next;
                first.prev.next = null;
                first.prev = null;
            }
            --size;
            return value;
        }
    
        // 获取队头元素---获取链表中第一个节点的值域
        public int peek() {
        
            if (first == null) {
        
                throw new EmptyException("队列为空");
            }
            return first.value;
        }
        public int size() {
        
            return size;
        }
        public boolean isEmpty(){
        
            return first == null;
        }
    }

## ?双端队列 (Deque) ##

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列

deque 是 “double ended queue” 的简称。

那就说明元素可以从队头出队和入队，也可以从队尾出队和入队  
![在这里插入图片描述][1c883800d650436d8bcf562e45478e23.png]  
Deque是一个接口，使用时必须创建LinkedList的对象。  
![在这里插入图片描述][8d788a7227b74143b5f1c6ef03c6da84.png]  
在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口

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

## ⭕总结 ##

关于《 【数据结构】 栈（Stack）与栈的模拟实现》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！

[77909960e5564f7080d828c5781a094f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/6de835be8e8c4509bc5e023b81142e21.png
[8096a4334a0c4004a45ebcd37791393b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/9e6a30a77c9740f2b5c6839b8d0d59bf.png
[2631bf06b12d416db5f84721fe5992a4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/bef0d99082444a4f92c951866eb7a40d.png
[b4f96696ae0249479a6f5947a614a899.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/b7301d64680843fe924d466da3d38161.png
[e93868f1fc2c470d9c14deb5d1de98b5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/185dad55352b41c2b8758e91731c9659.png
[1c883800d650436d8bcf562e45478e23.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/a3eabdc4c05048009cb65ee9ce2c5074.png
[8d788a7227b74143b5f1c6ef03c6da84.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/7381c50f38f6485198865afbd7e3ce49.png