Java - 数据结构，队列

刺骨的言语ヽ痛彻心扉 2024-03-26 13:10 76阅读 0赞

## 一、什么是队列 ##

普通队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）  
![在这里插入图片描述][1e9cc782a9a54db5a1b9e00ae3b2e164.png]  
双端队列：可以在对头或者队尾进行插入或者删除操作。  
![在这里插入图片描述][8e846759123b4fb2aa6eb5cd0e8e4607.png]  
普通队列和双端队列  
![在这里插入图片描述][9af9969bee5440beb48f80d73612931b.png]  
从上面知道双向列表可以当普通队列使用，也可以当双端队列使用，也可以当栈使用。

## 二、队列常用的方法 ##

### 2.1、Queue ###

![在这里插入图片描述][d7c61986f1a14cc9b34abc1c737103bf.png]  
**注意add函数和offer函数**  
![在这里插入图片描述][6a50f6605cb6443cbfe14fa565476489.png]

public static void main(String[] args) {
        
            Queue<Integer> queue = new LinkedList<>();
            queue.add(1);//添加元素
            queue.add(2);//添加元素
            queue.add(3);//添加元素
            queue.offer(4);//添加元素
            queue.offer(5);//添加元素
            queue.offer(6);//添加元素
            System.out.println(queue.peek());//获取对头元素，但是不删除
            System.out.println(queue.element());//获取对头元素，但是不删除
            System.out.println(queue.poll());//获取对头元素，并且删除对头元素
            System.out.println(queue.remove());//获取对头元素，并且删除对头元素
        }

### 2.2、Deque ###

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

public static void main(String[] args) {
        
            Deque<Integer> deque = new LinkedList<>();
            deque.add(1);//默认在队尾添加元素
            deque.addFirst(2);//在对头添加元素
            deque.addLast(3);//在队尾添加元素
            deque.offer(4);//在队尾添加元素
            deque.offerLast(5);//在队尾添加元素
            deque.offerFirst(6);//在队头添加元素
            System.out.println(deque);
            System.out.println(deque.peek());//获取元素，但是不删除
            System.out.println(deque.peekFirst());//获取队头元素，但是不删除
            System.out.println(deque.peekLast());//获取队尾元素，但是不删除
            System.out.println(deque.poll());//获取队头元素，并且删除
            System.out.println(deque.pollFirst());//获取队头元素，并且删除
            System.out.println(deque);
        }

## 三、单链表模拟实现队列 ##

![在这里插入图片描述][810d218bb1b04a2db41a18b451348c8a.png]  
单链表可以实现队列，那双向链表也可以实现队列  
使用单链表第三种方式实现队列  
**offer（）- 在队列里面添加元素**

/**
         * 在队列里面添加元素，实际上就是尾插法
         * @param val
         */
        public void offer(int val){
        
            //要插入节点，那就要先创造一个节点
            Node node = new Node(val);
            //这时候就要分两种情况：1、如果是第一次插入 2、不是第一次插入
            if(head == null){
        
                //head == null说明是第一次插入
                head = node;
                last = node;
            }else {
        
                last.next = node;
                last = last.next;
            }
        }

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

**poll（） - 出队列**

/**
         * 出队列，并且删除元素
         * @return
         */
        public int poll(){
        
            //出队列就是删除头结点，但是如果链表里面没有节点那就不能删除
            if(isEmpty()){
        
                throw new RuntimeException("队列为空！");
            }
            int oldVal = head.val;
            head = head.next;
            return oldVal;
        }
    
        /**
         * 判断队列是否为空，如果队列为空那就返回true，否则返回FALSE
         * @return
         */
        public boolean isEmpty(){
        
            return this.head == null;
        }

**使用的单链表实现简单的队列**

//使用单链表实现队列，首先就要定义节点
    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);
            //这时候就要分两种情况：1、如果是第一次插入 2、不是第一次插入
            if(head == null){
        
                //head == null说明是第一次插入
                head = node;
                last = node;
            }else {
        
                last.next = node;
                last = last.next;
            }
        }
    
        /**
         * 出队列，并且删除元素
         * @return
         */
        public int poll(){
        
            //出队列就是删除头结点，但是如果链表里面没有节点那就不能删除
            if(isEmpty()){
        
                throw new RuntimeException("队列为空！");
            }
            int oldVal = head.val;
            head = head.next;
            return oldVal;
        }
    
        /**
         * 判断队列是否为空，如果队列为空那就返回true，否则返回FALSE
         * @return
         */
        public boolean isEmpty(){
        
            return this.head == null;
        }
    
        /**
         * 获取对头的元素
         * @return
         */
        public int peek(){
        
            //出队列就是删除头结点，但是如果链表里面没有节点那就不能删除
            if(isEmpty()){
        
                throw new RuntimeException("队列为空！");
            }
            return head.val;
        }
    }

## 四、循环队列 ##

我们说了可以利用链表实现队列，那能不能利用数组实现队列？？？  
![在这里插入图片描述][b3f3d86c0d644e968f417abea6036cba.png]  
上图转载于：[https://blog.csdn.net/DarkAndGrey/article/details/122511544][https_blog.csdn.net_DarkAndGrey_article_details_122511544]

### 队列面试题 ###

#### [设计循环队列][Link 1] ####

![在这里插入图片描述][996a977a3eed4195934a511637bd33ad.png]  
![在这里插入图片描述][3234bd6b1c124354843b01647225cb84.png]  
上图转载于：[https://blog.csdn.net/DarkAndGrey/article/details/122511544][https_blog.csdn.net_DarkAndGrey_article_details_122511544]

**代码如下：**

public class MyCircularQueue {
        
        //我们知道循环队列是有数组实现的，所以要创建一个数组，并且还有表示对头和队尾的下标
        public int[] elem;
        public int front;//对头的下标
        public int rear;//队尾的下标
    
        /**
         * 构造方法，初始化数组的大小
         * @param k
         */
        public MyCircularQueue(int k) {
        
            this.elem = new int[k+1];
        }
    
        /**
         * 入队列
         * @param value
         * @return
         */
        public boolean enQueue(int value) {
        
            //在入队列的时候先判断队列是否满，满了不能入
            if(isFull()){
        
                return false;
            }
            elem[rear] = value;
            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];
        }
    
        /**
         * 获取队尾元素
         * @return
         */
        
    
        public int Rear() {
        
            if(isEmpty()){
        
                return -1;
            }
            int index = 0;
            if(rear == 0){
        
                index = elem.length - 1;
            }else{
        
                index = rear - 1;
            }
            return elem[index];
        }
        
        public boolean isEmpty() {
        
            //front的下一个是rear，那就说明空了
            return front == rear;
        }
    
        /**
         * 判断队列是否满
         * @return
         */
        public boolean isFull() {
        
            //rear的下一个如果是front，那这个队列就满了
            if((rear+1) % elem.length == front){
        
                return true;
            }
            return false;
        }
    }

#### [用队列实现栈][Link 2] ####

![在这里插入图片描述][2b917397e59e44d99f0fe4af116f9882.png]  
![在这里插入图片描述][afda65a94c8d4a9a95bb39cc78567ab8.png]

**代码如下：**

class MyStack {
        
        private Queue<Integer> qu1;
        private Queue<Integer> qu2;
    
        public MyStack() {
        
            qu1 = new LinkedList<>();
            qu2 = new LinkedList<>();
        }
    
        /**
         * 添加元素，将要添加的元素放入不为空的栈里面
         * @param x
         */
        public void push(int x) {
        
            if(!qu1.isEmpty()){
        
                //如果qu1不为空，那就插入元素
                qu1.offer(x);
            }else if(!qu2.isEmpty()){
        
                //如果qu2不为空，那就插入元素
                qu2.offer(x);
            }else{
        
                //第一次插入的时候，两个都为空的时候，那就指定队列插入元素
                qu1.offer(x);
            }
        }
    
        /**
         * 弹出元素
         * @return
         */
        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 = 0;
                //要记录这个size ，不然当出一个元素的时候这个函数都会变化，得到的值也会变化
                int size = qu1.size();
                for (int i = 0; i < size; i++) {
        
                    val = qu1.poll();
                    qu2.offer(val);
                }
                return val;
            }
            if(!qu2.isEmpty()){
        
                int val = 0;
                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();
        }
    }

#### [用栈实现队列][Link 3] ####

![在这里插入图片描述][0912e81fa455452f9968fdf0774c8d02.png]  
栈 的特性是：先进后出。也就是说第一个入栈的数据，将是最后一个出栈，我们利用两个栈来实现这题。  
![在这里插入图片描述][698dc2f47c824474930e87e14c82e3ac.png]  
**代码如下：**

class MyQueue {
        
    
        Stack<Integer> stack1;
        Stack<Integer> stack2;
        public MyQueue() {
        
            stack1 = new Stack<>();
            stack2 = new Stack<>();
        }
    
        public void push(int x) {
        
            stack1.push(x);
        }
    
        public int pop() {
        
            if(stack2.isEmpty()){
        
                while(!stack1.isEmpty()){
        
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    
        public int peek() {
        
            // 防止 别人一开始 就调用 peek，所以 peek 也需要 写 stack1 导入 stack2 的程序
            if(stack2.isEmpty()){
        
                while(!stack1.isEmpty()){
        
                    stack2.push(stack1.pop());
                }
            }
            return stack2.peek();
        }
    
        public boolean empty() {
        // 如果模拟的队列 将全部数据出队，那么 stack1 和 stack2 都为空
            return stack1.isEmpty() && stack2.isEmpty();
        }
    }

[1e9cc782a9a54db5a1b9e00ae3b2e164.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/df341828709d49cd814a28e5d2245188.png
[8e846759123b4fb2aa6eb5cd0e8e4607.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/8eda13f53d6040088fcb24156640319c.png
[9af9969bee5440beb48f80d73612931b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/29babbce1c6f4a009b6aca6f1f2127e5.png
[d7c61986f1a14cc9b34abc1c737103bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/460338ed222b483ebe504dada04640fa.png
[6a50f6605cb6443cbfe14fa565476489.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/c1608cd645fc48fdafd23d4557454e05.png
[991ffd6fe41a45ecbfe6864eb301f957.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/dacb8f32813043a989261c8eaab30157.png
[810d218bb1b04a2db41a18b451348c8a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/02f08e62990b49c4ab069f0bae601790.png
[2df0cac09fd04e998d67605e007e1046.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/a8ae8bd5d68041fd916a12fd9bd5d9e2.png
[b3f3d86c0d644e968f417abea6036cba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/838b16cf28cb4ef78deec4daef952ff0.png
[https_blog.csdn.net_DarkAndGrey_article_details_122511544]: https://blog.csdn.net/DarkAndGrey/article/details/122511544
[Link 1]: https://leetcode.cn/problems/design-circular-queue/
[996a977a3eed4195934a511637bd33ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4e16afb2d54840e79b4a6a5ba1c69e4d.png
[3234bd6b1c124354843b01647225cb84.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/1aa5e3770d7349c2899e73b1c210a61e.png
[Link 2]: https://leetcode.cn/problems/implement-stack-using-queues/
[2b917397e59e44d99f0fe4af116f9882.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/6a73d3ffaf6d4d988ee2991b277d6779.png
[afda65a94c8d4a9a95bb39cc78567ab8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/d20a532ce66047c79a0fc134bcdff176.png
[Link 3]: https://leetcode.cn/problems/implement-queue-using-stacks/
[0912e81fa455452f9968fdf0774c8d02.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/94186fe6738841498c82114b3228e222.png
[698dc2f47c824474930e87e14c82e3ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/f6c862feddcd4e32ba1d12931a014246.png