devbox
煮酒与君饮
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

队列知识点集合（概念，特性，应用，循环队列，模拟实现以及OJ题目，都在这里）^_^_队列知识点总结

作者：煮酒与君饮 | 2024-08-04 15:07:35

赞

踩

队列知识点总结

队列（Queue）的常用知识点集合

1. 队列的基本知识

1.1 概念及特性

队列概念：

队列：是一种只允许在一端进行数据的插入，在另一端进行数据的删除操作的特殊线性表，在Java中，队列（Queue）是个接口，继承自 Collection ，底层是通过链表来实现的；
将插入数据的一端称为队尾，删除数据的一端称为对头。
如下图所示：

在这里插入图片描述

队列特性：

队列遵循先进先出的原则，(First In First Out) ；
大神比喻：吃进去，拉出来

1.2 队列的使用

常用方法：

  • boolean offer(E e)：将元素 e入队列
  • E poll()：出队列
  • E peek()：获取队头元素
  • int size() ： 获取队列中有效元素个数
  • boolean isEmpty()： 检测队列是否为空
package day20211018;

import java.util.LinkedList;
import java.util.Queue;

public class TestQueue {
    //测试队列
    public static void main(String[] args) {
        Queue q=new LinkedList();
        //入队列：1 2 3 4
        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);
        System.out.println(q);  //[1, 2, 3, 4]
        //获取队头元素
        System.out.println(q.peek()); //1
        //获取队列中元素的个数
        System.out.println(q.size()); //4
        //出队头2个元素
        q.poll();
        q.poll();
        System.out.println(q); //[3, 4]
        //判断队列是否为空
        if(q.isEmpty()) {
            System.out.println("队为空");
        }else{
            System.out.println("队不为空");
        }
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

2. 模拟实现队列

package day20211023;

    //模拟实现队列--Queue
public class Queue <E>{
    public static class ListNode<E>{
        E value;
        ListNode<E> next;
        ListNode<E> prev;

        public ListNode(E val){
           this.value = val;

        }
    }
     ListNode<E> first; //标记表示队头元素
     ListNode<E> last; // 标记队尾元素
     int size=0; //队列中有效元素的个数

        //入队列--offer
     public boolean offer(E e){
         ListNode<E> newNode=new ListNode<>(e);
         if(first==null){
             //队列为空
             first=newNode;
             //last=newNode;
         }else{
             //队列不为空
             last.next=newNode;
             //last=newNode;
         }
         last=newNode;
         size++;
         return true;
        }

        //出队列-poll
        //实质：删除队头元素
        public E poll() {
            if(0 == size){
                return null;
            }
            ListNode<E> delNode = first;
            first = first.next;
            if(null == first){
                last = null;
            }
            size--;
            return delNode.value;
        }
           

        //获取队头元素
        public E peek() {
            if (first == null) {
                //说明队列中没有元素
                return null;
            }
            return first.value;
        }

        //获取有效元素的个数
        public int size(){
         return size;
        }

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

        public static void main(String[] args) {
            Queue<Integer> q=new Queue<>();
            //测试入队列 1 2 3 4 5
            q.offer(1);
            q.offer(2);
            q.offer(3);
            q.offer(4);
            q.offer(5);
            System.out.println(q.size()); //5
            System.out.println(q.peek()); //1
            //测试出队列
            q.poll();
            q.poll();
            q.poll();
            System.out.println(q.size()); //2
            System.out.println(q.peek()); //4

            //测试判空
           if(q.isEmpty()){
                System.out.println("队列为空");
            }else{
                System.out.println("队列不为空");
            }
      }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95

思考：

在 Java 中，队列是采用链表来实现的，如果采用连续空间是否能满足队列的所有操作的时间复杂度都为O(1)?

分析如下：

假设借助数组的一段连续空间来实现入队列、出队列和获取队头元素的的操作；
如下图所示：入队列：1 2 3 4 5 6 这 6 个元素，直接插入尾部即可，时间复杂度为O(1);
在这里插入图片描述

出队列时：由于队列具有先进先出的特性，因此只有该元素成为队头元素才可以实现出队列；

出队列方式一：

保持front不动，将后面5个元素整体往前搬移一个位置；再将rear往前移动一个位置；
注意：虽然这样可以实现出队列，但当有N个元素时，就需要搬移N-1次，所以时间复杂度为O(N)，不满足要求；

如下图所示：

在这里插入图片描述

那么，要保证队列的所有操作中，时间复杂度均为O(1)，要怎么实现呢？

方式二：

出队列时，让front往后移动一步即可实现；
原因：front每次标记的都是队头元素，因此当front往后移动时，就相当于将前面的元素移出队列了；
而且确保了出队列的时间复杂度为O(1)，但采用该种方式时，又会导致假溢出的现象。

假溢出：当想要再该空间进行数据插入时，由于rear已经指向了空间的末尾，因此不能插入。但实际上前面有三个元素已经出队列了，这部分是有剩余空间的，只是不能被使用而已。把这种现象称为队列的假溢出；

在这里插入图片描述
针对上面使用连续空间所出现的假溢出问题，提出了循环队列

3.循环队列

循环队列：就是将队列存储空间的最后一个位置绕回到第一个位置，形成逻辑上的环状空间，以便实现队列的循环使用，循环队列也是一种线性的数据结构，其操作表现是基于 FIFO（先进先出）的原则；如下图所示：

在这里插入图片描述

如上环形队列图所示：

入队列时：
将元素放在rear队尾的位置，然后将rear往后移动一步；
出队列时：front往后移动一步即可；

在上图中的5号位置再插入一个元素时，rear就指向了front的位置，那此时，如何判断队列是空还是满呢？

判断循环队列是空还是满的**三种方式**：

  • 使用 count 来计数

当count为0 时，循环队列就是空的；
当count为arr.length时，循环队列为满；

  • 少存储一个元素

当front等于rear时，队列为空；
当rear加1等于rear时，队列就为满
注意：当队列中的元素存储到最后一个位置时，再插入元素就回到了起始位置，所以队列满时判断条件为：

     (rear+1）% arr.length==front

  • 1
  • 设置标志位

起始状态，将flag设为false
入队列时，rear往下一个位置移动，同时flag=true；
出队列时：front往下一个位置移动，同时flag=false；
当front等于rear &&flag等于false时，队列为空；
当front等于rear &&flag等于true时，队列为满；

如何实现一个循环队列？

循环队列实现代码:

class MyCircularQueue {
    int[] array;
    int front=0;  //标记队头元素
    int rear=0;   //标记队尾元素
    int count=0;  //判断队列是满还是空
    int N; //队列的长度
    public MyCircularQueue(int k) {
        array=new int[k];
        N=k;
    }
    //入队列
    public boolean enQueue(int value) {
     if(isFull()){
         return false;
     }
        array[rear]=value;
        rear++;
        if(rear==N){
            rear=0;
        }
        count++;
        return true;
    }
    //出队列
    public boolean deQueue() {
     if(isEmpty()){
            return false;
        }
      
        front++;
        front %= N;
        count--;
        return true;
    }
    //获取队头元素
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return array[front];

    }
    //获取队尾元素
    public int Rear() {
        if(isEmpty()){
            return -1;
        } 

       return array[((rear-1)+N)%N];
    }
    
    public boolean isEmpty() {
        return 0==count;
    }
    
    public boolean isFull() {
        return count==array.length;
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

4. 双端队列

双端队列（Deque）是指允许两端都可以进行入队和出队操作的队列，底层也是通过 LinkedList 实现的； 集合框架中的结构图如下图所示：

在这里插入图片描述

常见队列笔试题

（很重要哦）

注：下面三道题点开蓝色链接查看原题 ！！！

第一题：队列实现栈

问题描述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false

解题思路：

使用两个队列q1 和 q2 ，q1 用来存储元素，q2 用来作为入栈的辅助队列；
入栈时：先将元素入队到q2中，然后再将q1的全部元素出队到q2中，再将两个队列中的元素互换，则q1的前端元素和后端为栈顶和栈底元素；
由于每次入栈操作都确保 q1 的前端元素为栈顶元素，因此，出栈操作只需要移除 q1 的前端元素并返回即可。
获取栈顶元素：只需要获得q1的前端元素并返回；
判断栈空：只需要q1是否为空；

class MyStack {
    //定义两个队列q1,q2，一个用来存储元素，一个用作为辅助队列
    Queue<Integer> q1=new LinkedList<>();  
    Queue<Integer> q2=new LinkedList<>(); 
    public MyStack() {

    }
       //入栈
    public void push(int x) {
         q2.offer(x);
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }
    //出栈
    public int pop() {
         return q1.poll();
    }
     
    //获取栈顶元素
    public int top() {
        return q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty();

    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

第二题：用栈实现队列

问题描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

解题思路：

使用两个栈s1和s2，s1用来模拟入队列，s2用来模拟出队列；
入队列时：直接将元素放入s1中；
出队列时：如果s2是空的，将s1中的所有元素导入到s2中，将s2栈顶元素删除；
获取队头元素：如果s2是空的，将s1中的所有元素导入到s2中，将s2栈顶元素返回；
在这里插入图片描述

代码实现：

class MyQueue {
    Stack<Integer> s1=new Stack<>();
    Stack<Integer> s2=new Stack<>();
    public MyQueue() {

    }
    //入队列
    public void push(int x) {
        s1.push(x);

    }
    //出队列
    public int pop() {
        if(s2.empty()){
            //将s1中的所有元素导入到s2中
            while(s1.size()>0){
             s2.push(s1.pop());  
            }  
        }
        return s2.pop();

    }
    
    public int peek() {
         if(s2.empty()){
            while(s1.size()>0){
            s2.push(s1.pop());
        }
      }
        return s2.peek();
    }
    
    public boolean empty() {
       return s1.isEmpty() && s2.isEmpty(); 

    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

第三题：实现一个最小栈

问题描述：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

  • push(x) —— 将元素 x 推入栈中
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。

解题思路：
在这里插入图片描述
入栈时：

当S2不空时，将元素在S1，S2中各放入一份；
若S2 不空，就将 val 与 S2 栈顶元素进行比较，当val小于等于S2的栈顶元素时，将val 在S1 和S2中个放入一份，当val大于S2的栈顶元素时，将val 放入S1中；

出栈时：

当S1 和S2栈顶元素相等时，S2出栈；
S1每次都要出栈一个元素；

栈顶元素就在S1中

最小值就在S2中

class MinStack {
    Stack<Integer> s1=new Stack<>();
    Stack<Integer> s2=new Stack<>();
    public MinStack() {

    }
    //入栈
    public void push(int val) {
        if(s2.empty() || val<=s2.peek()){
            s2.push(val);
        }
        s1.push(val);
    }
       //出栈
    public void pop() {
        if(s1.peek().equals(s2.peek())){
            s2.pop();
        }
         s1.pop();
    }
    
    public int top() {
        return s1.peek();
    }
    
    public int getMin() {
     return s2.peek();
    }  
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/928365
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号