• 队列(Queue)的顶级理解

    目录

    1.队列(Queue) 的概念

    2.单链表模拟实现队列

    2.1创建队列

    2.2入队列

    2.3判断是否为空

    2.4出队列

    2.5获取队头元素

    2.6完整代码：

    2.7双向链表模拟实现队列代码

    3.数组模拟实现队列代码

    3.1创建队列

     3.2判断是否为满

    3.3检查是否为空 

     3.4插入元素

     3.5删除元素

     3.6从队首获取元素

    3.7 从队尾获取元素

    4.双端队列 (Deque)

    1.队列(Queue) 的概念

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

    在Java中，Queue是个接口，底层是通过链表实现的。

    队列在使用时有以下方法：

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

    Queue<Integer> q = new LinkedList<>();

    2.单链表模拟实现队列

    2.1创建队列

    代码：

    1. public class Myqueue {
    2.     class Node{
    3.         public int val;
    4.         public Node next;
    5.         public Node(int val){
    6.             this.val=val;
    7.         }
    8.     }
    9.  
    10.     public Node head;
    11.     public Node last;
    12.     public int size;
    13. }

    2.2入队列

    (1)创建一个节点node。

    (2)判断该head是否为null,若为null，则该node就是head和last。

    (3)若不为null，则 last.next=node， last=node;

    (4)size++。

    代码：

    1.     public void offer(int val){
    2.         Node node = new Node(val);
    3.         if(head==null){
    4.             head=node;
    5.             last=node;
    6.         }else{
    7.             last.next=node;
    8.             last=node;
    9.         }
    10.         size++;
    11.     }

    2.3判断是否为空

    1.  public boolean empty(){
    2.         return size==0;
    3.     }

    2.4出队列

    （1）队列为空，则直接返回队列为空的异常。

    自定义异常如下：

    1. public class EmptyException extends RuntimeException{
    2.     public EmptyException(String message) {
    3.         super(message);
    4.     }
    5. }

    （2）队列为空不为，先ret=head.val，后删除头结点head=head.next;，再判断ihead是否为null。

    如果是last也要置空。

    （3）size--。

    代码：

    1.     public int poll(){
    2.         if(isEmpty()){
    3.             throw new EmptyException("栈是空的！");
    4.         }
    5.         int ret=head.val;
    6.         size--;
    7.         head=head.next;
    8.         if(head==null){
    9.             last=null;
    10.         }
    11.         return ret;
    12.     }

    2.5获取队头元素

    代码：

    1. public int peek(){
    2.         if(empty()){
    3.             throw new EmptyException("队列为空");
    4.         }
    5.         int ret=head.val;
    6.         return ret;
    7.     }

    2.6完整代码：

    1. public class Myqueue {
    2.     class Node{
    3.         public int val;
    4.         public Node next;
    5.         public Node(int val){
    6.             this.val=val;
    7.         }
    8.     }
    9.  
    10.     public Node head;
    11.     public Node last;
    12.     public int size;
    13.  
    14.     public void offer(int val){
    15.         Node node = new Node(val);
    16.         if(head==null){
    17.             head=node;
    18.             last=node;
    19.         }else{
    20.             last.next=node;
    21.             last=node;
    22.         }
    23.         size++;
    24.     }
    25.      public int poll(){
    26.         if(isEmpty()){
    27.             throw new EmptyException("栈是空的！");
    28.         }
    29.         int ret=head.val;
    30.         size--;
    31.         head=head.next;
    32.         if(head==null){
    33.             last=null;
    34.         }
    35.         return ret;
    36.     }
    37.     public boolean empty(){
    38.         return size==0;
    39.     }
    40.     public int peek(){
    41.         if(empty()){
    42.             throw new EmptyException("队列为空");
    43.         }
    44.         int ret=head.val;
    45.         return ret;
    46.     }
    47. }

    2.7双向链表模拟实现队列代码

    1. public class MyQueue {
    2.     // 双向链表节点
    3.     public static class ListNode {
    4.         ListNode next;
    5.         ListNode prev;
    6.         int value;
    7.  
    8.         ListNode(int value) {
    9.             this.value = value;
    10.         }
    11.     }
    12.  
    13.     ListNode first; // 队头
    14.     ListNode last; // 队尾
    15.     int size = 0;
    16.  
    17.     // 入队列---向双向链表位置插入新节点
    18.     public void offer(int e) {
    19.         ListNode newNode = new ListNode(e);
    20.         if (first == null) {
    21.             first = newNode;
    22. // last = newNode;
    23.         } else {
    24.             last.next = newNode;
    25.             newNode.prev = last;
    26. // last = newNode;
    27.         }
    28.         last = newNode;
    29.         size++;
    30.     }
    31.  
    32.     // 出队列---将双向链表第一个节点删除掉
    33.     public int poll() {
    34. // 1. 队列为空
    35. // 2. 队列中只有一个元素----链表中只有一个节点---直接删除
    36. // 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
    37.         int value = 0;
    38.         if (first == null) {
    39.             throw new EmptyException("队列为空");
    40.         } else if (first == last) {
    41.             last = null;
    42.             first = null;
    43.         } else {
    44.             value = first.value;
    45.             first = first.next;
    46.             first.prev.next = null;
    47.             first.prev = null;
    48.         }
    49.         --size;
    50.         return value;
    51.     }
    52.  
    53.     // 获取队头元素---获取链表中第一个节点的值域
    54.     public int peek() {
    55.         if (first == null) {
    56.             throw new EmptyException("队列为空");
    57.         }
    58.         return first.value;
    59.     }
    60.     public int size() {
    61.         return size;
    62.     }
    63.     public boolean isEmpty(){
    64.         return first == null;
    65.     }
    66. }

    3.数组模拟实现队列代码

    实际中我们有时还会使用一种队列叫循环队列，环形队列通常使用数组实现。

    循环队列icon-default.png?t=N7T8https://leetcode.cn/problems/design-circular-queue/description/描述：

      

    要解决循环队列的有如下几个难题：

    （1）数组的下标如何实现循环

    rear=(rear+1)%elem.length

     front=(front+1)%elem.length

    （2）区分空与满

    有三个方法：

    1. 通过添加 size 属性记录

    2. 保留一个位置

    3. 使用标记

    本博主采用第二个方法，如下图所示：

    3.1创建队列

    由于我们需要浪费一个空间来判断是否为满，在构造方法时多构造一个空间。

    1. class MyCircularQueue {
    2.     private int[] elem;
    3.     private int front;//表示队列的头
    4.     private int rear;//表示队列的尾
    5.  
    6.     public MyCircularQueue(int k) {
    7.      this.elem=new int[k+1];
    8.     }
    9. }

     3.2判断是否为满

    1.  public boolean isFull() {
    2.         return (rear+1)%elem.length==front;
    3.     }

    3.3检查是否为空 

    1. public boolean isEmpty() {
    2.         return rear == front;
    3.     }

     3.4插入元素

    (1)判断是否为满,若为满。返回false

    (2)若不为满，则在elem下标为rear处插入该元素

    (3)队尾向后走一步rear=(rear+1)%elem.length，返回true；

    1. public boolean enQueue(int value) {
    2.      if(isFull()){
    3.          return false;
    4.      }
    5.      elem[rear]=value;
    6.      rear=(rear+1)%elem.length;
    7.      return true;
    8.     }

     3.5删除元素

    判断是否为null

    (1)若为null。返回false

    (2)若不为null，队首向后走一步 front = (front+1)%elem.length;，返回true；

    1.     public boolean deQueue() {
    2.         if (isEmpty()){
    3.             return false;
    4.         }
    5.         front = (front+1)%elem.length;
    6.         return true;
    7.     }

     3.6从队首获取元素

    1.    public int Front(){
    2.         if(isEmpty()){
    3.             return -1;
    4.         }
    5.         return elem[front];
    6.     }

    3.7 从队尾获取元素

    (1)如果队列为空，返回-1

    (2)不为空，如果为队尾下标为0，返回下elem[elem.length-1]的值

    (3)下标不为0，返回数组下标为rear-1的值

    1.   public int Rear() {
    2.         if(isEmpty() ) {
    3.             return -1;
    4.         }
    5.         if(rear == 0) {
    6.             return elem[elem.length-1];
    7.         }
    8.         return elem[rear-1];
    9.     }

    3.8完整代码

    1. class MyCircularQueue {
    2.     private int[] elem;
    3.     private int front;//表示队列的头
    4.     private int rear;//表示队列的尾
    5.  
    6.     public MyCircularQueue(int k) {
    7.         this.elem = new int[k + 1];
    8.     }
    9.  
    10.     public boolean enQueue(int value) {
    11.         if (isFull()) {
    12.             return false;
    13.         }
    14.         elem[rear] = value;
    15.         rear = (rear + 1) % elem.length;
    16.         return true;
    17.     }
    18.  
    19.     public boolean deQueue() {
    20.         if (isEmpty()){
    21.             return false;
    22.         }
    23.         front = (front+1)%elem.length;
    24.         return true;
    25.     }
    26.  
    27.     //从队首获取元素。如果队列为空，返回 -1 。
    28.     public int Front() {
    29.         if(isEmpty() ) {
    30.             return -1;
    31.         }
    32.         return elem[front];
    33.     }
    34.  
    35.  
    36.     //从队尾获取元素。如果队列为空，返回 -1 。
    37.     public int Rear() {
    38.         if(isEmpty() ) {
    39.             return -1;
    40.         }
    41.         if(rear == 0) {
    42.             return elem[elem.length-1];
    43.         }
    44.         return elem[rear-1];
    45.     }
    46.  
    47.  
    48.     //检查循环队列是否为空。
    49.     public boolean isEmpty() {
    50.         return rear == front;
    51.     }
    52.  
    53.  
    54.     public boolean isFull() {
    55.         return (rear + 1) % elem.length == front;
    56.     }
    57. }

    4.双端队列 (Deque)

    双端队列（ deque ）是 指允许两端都可以进行入队和出队操作的队列 ， deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

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

     在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口

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

    以上为我个人的小分享，如有问题，欢迎讨论！！！ 

    都看到这了，不如关注一下，给个免费的赞 

     

  • 相关阅读:
    【C++】堆栈的使用 | 堆栈的大小 | 动静态分配问题
    golang中出于性能考虑的那些实用代码片段 |字符串篇
    SQL SERVER连接oracle数据库几种方法
    CentOS7卸载Nginx、最后有命令总结
    秋日有感之秋诉-于光
    【MATLAB教程案例32】基于matlab的交通标志检测分割算法的仿真——形态学处理,膨胀,腐蚀,形状检测,颜色模型,小波滤波等知识的综合应用
    Linux学习之远程拷贝数据命令
    PyQt5_QScrollArea内容保存成图片
    Linux：Jenkins：GitLab+Maven+Jenkins的部署
    MFC软件国际化的几个问题及其解决方案
  • 原文地址：https://blog.csdn.net/WHabc2002/article/details/132789463