【数据结构】之队列

悠悠 2022-01-30 10:17 355阅读 0赞

笔者日常：
感谢孤尽(花名)大侠今天给我解答线程安全的问题，在这里推荐孤大侠书籍《码出高效》，带你深入基础，走进阿里规范！

目录

队列基本知识

队列的常见实现方式

  1.      数组实现
  3.      链表实现

队列的常见分类

  1.     数组队列：基于数组的原理进行实现。
  3.     链表队列：基于链表的原理进行实现。

Java对上述队列的代码实现(示例)

  1.     对(数组)顺序队列的(简单)实现
  3.     对(数组)循环队列的(简单)实现
  5.     对链表队列的(简单)实现

队列基本知识：

  1.    队列是一种特殊的操作受限制的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，**进行插入操作的端称为队尾，进行删除操作的端称为队头**。队列的插入操作称为入队，删除操作称为出队。队列就像一列进入隧道的火车，隧道就是队列，火车车厢就是元素，进入隧道就是从隧道的这头(队尾)插入元素；出隧道就是从隧道的另一头(队头)删除元素。队列具有**先进先出(FIFO—first in first out)**的特点。

20190519022245198.png

队列的常见实现方式：

  1.    队列的实现方式较多，我们常见的主要有两种，分别是数组实现与链表实现。基于数组的队列效率较高，但有长度限制(当然可以在程序内部以新建数组的方式来变相达到动态扩容的效果)。基于链表的队列，要动态创建和删除节点，效率较低，但是可以动态增长。

数组实现：

20190519022336224.gif

链表实现：

20190519022400211.gif

队列的常见分类：

  1.     分类标准不同，队列分类也不一样。按照入队出队时是否阻塞可分为阻塞队列、非阻塞队列。按照实现方式来分的话，队列可分为数组队列、链表队列等。其中，数组队列按照空间是否可以重复利用来分的话，又可分为顺序队列和循环队列。

注：对于数组队列而言，循环队列要比顺序队列实用得多。

数组队列：基于数组的原理进行实现。

相关概念之溢出(图示说明)：

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70

顺序队列(主要以图示说明)：从队头删除元素，从队尾增加元素。被删除的元素空出来的位置，不会被后来增加的
元素重复利用。

第一种：队头不动，出队列时队头后的所有元素向前移动。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70 1

注：一旦有元素出队，那么所有元素都得移动，开销较大。

第二种：队头移动，出队列时队头向后移动一个位置。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70 2

注：此方式可能出现假溢出。

循环队列(主要以图示说明)：从队头删除元素，从队尾增加元素。被删除的元素空出来的位置，会被后来增加的元素重复利用。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70 3

链表队列：基于链表的原理进行实现。

2019051902290663.png

注：可结合上文中的链表实现gif动图进行理解。

Java对上述队列的代码实现(示例)：

声明**：**这里只是简单的实现，如果想要了解更全面实现方式的话，推荐阅读各种阻塞非阻塞队列的源码。

先给出一个下面三个队列实现中都会用到的异常类：

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70 4

对(数组)顺序队列的(简单)实现：

  1. import java.io.Serializable;
  2. import java.util.Arrays;
  4. /**
  5.  * (简单实现)顺序队列
  6.  *
  7.  * @author JustryDeng
  8.  * @date 2019/5/18 21:19
  9.  */
  10. public class SequenceQueue<E> implements Serializable{
  12.     private static final long serialVersionUID = -807097163996913371L;
  14.     /** 元素容器 */
  15.     private final Object[] items;
  17.     /** 队列的容量(即:数组的长度) */
  18.     private int capacity;
  20.     /** 队头 */
  21.     private int front;
  23.     /** 队尾 */
  24.     private int rear;
  26.     /**
  27.      * 构造器
  28.      *
  29.      * @param capacity
  30.      *            队列的容量
  31.      * @date 2019/5/18 21:55
  32.      */
  33.     public SequenceQueue(int capacity) {
  34.         this.capacity = capacity;
  35.         items = new Object[capacity];
  36.         front = 0;
  37.         rear = 0;
  38.     }
  40.     /**
  41.      * 入队
  42.      *
  43.      * @param e
  44.      *            入队的元素
  45.      * @date 2019/5/18 22:27
  46.      */
  47.     public void offer(E e) {
  48.         if (e == null) {
  49.             throw new IllegalArgumentException("arg must be not null!");
  50.         }
  51.         if (rear >= capacity) {
  52.             throw new MyQueueException("the queue already full!");
  53.         }
  54.         items[rear] = e;
  55.         rear++;
  56.     }
  58.     /**
  59.      * 出队
  60.      *
  61.      * @return  出队的那个元素
  62.      * @date 2019/5/18 22:25
  63.      */
  64.     public E poll() {
  65.         if (isEmpty()) {
  66.             throw new MyQueueException("the queue is empty!");
  67.         }
  68.         // 保留队列的front端的元素的值
  69.         E oldValue = itemAt(front);
  70.         // 释放队列的front端的元素
  71.         items[front] = null;
  72.         front++;
  73.         return oldValue;
  74.     }
  76.     /**
  77.      * 返回队列头元素,但不会将该元素出列
  78.      *
  79.      * @return 队列头元素
  80.      * @date 2019/5/18 22:07
  81.      */
  82.     public E peek() {
  83.         if (isEmpty()) {
  84.             throw new MyQueueException("the queue is empty!");
  85.         }
  86.         return itemAt(front);
  87.     }
  89.     /**
  90.      * 返回指定位置处的元素
  91.      *
  92.      * @param index
  93.      *          索引位置
  94.      *
  95.      * @return  返回index位置处的元素
  96.      * @date 2019/5/18 22:21
  97.      */
  98.     @SuppressWarnings("unchecked")
  99.     public E itemAt(int index) {
  100.         return (E) items[index];
  101.     }
  103.     /**
  104.      * 判断队列是否为空队列
  105.      *
  106.      * @return  是/否
  107.      * @date 2019/5/18 22:04
  108.      */
  109.     public boolean isEmpty() {
  110.         return rear == front;
  111.     }
  113.     /**
  114.      * 判断队列是否已满
  115.      *
  116.      * @return  是/否
  117.      * @date 2019/5/18 22:04
  118.      */
  119.     public boolean isFull() {
  120.         return rear >= capacity;
  121.     }
  123.     /**
  124.      * 获取队列的实际有效大小(即:获取队列中元素的个数)
  125.      *
  126.      * @return  获取当前队列的大小
  127.      * @date 2019/5/18 21:54
  128.      */
  129.     public int size() {
  130.         return rear - front;
  131.     }
  133.     /**
  134.      * 清空队列
  135.      *
  136.      * @date 2019/5/18 22:04
  137.      */
  138.     public void clear() {
  139.         // 将数组所有元素赋为null
  140.         Arrays.fill(items, null);
  141.         // 首尾指针重置
  142.         front = 0;
  143.         rear = 0;
  144.     }
  146.     @Override
  147.     public String toString() {
  148.         if (isEmpty()) {
  149.             return "[]";
  150.         } else {
  151.             StringBuilder sb = new StringBuilder("[");
  152.             for (int i = front; i < rear; i++) {
  153.                 sb.append(items[i].toString())
  154.                   .append( ", ");
  155.             }
  156.             int len = sb.length();
  157.             return sb.delete(len - 2, len).append("]").toString();
  158.         }
  159.     }
  161.     /**
  162.      * 测试一下
  163.      *
  164.      * @author JustryDeng
  165.      * @date 2019/5/19 1:14
  166.      */
  167.     public static void main(String[] args) {
  168.         SequenceQueue<String> queue = new SequenceQueue<>(5);
  169.         // 入队
  170.         queue.offer("A");
  171.         queue.offer("B");
  172.         queue.offer("C");
  173.         // 出队(出队后，元素就不在队列中了)
  174.         System.out.println(queue.poll());
  175.         System.out.println(queue.poll());
  176.         // 队列是否为空
  177.         System.out.println(queue.isEmpty());
  178.         // 队列中元素个数
  179.         System.out.println(queue.size());
  180.         // 获取队列中的头元素(此操作后，该元素仍然在队列中)
  181.         System.out.println(queue.peek());
  182.         // 入队
  183.         queue.offer("D");
  184.         queue.offer("E");
  185.         // 队列是否已满
  186.         System.out.println(queue.isFull());
  187.         // 验证queue的toString函数
  188.         System.out.println(queue);
  189.         // 清空队列
  190.         queue.clear();
  191.         queue.offer("F");
  192.         // 验证queue的toString函数
  193.         System.out.println(queue);
  194.         // 队列中元素个数
  195.         System.out.println(queue.size());
  196.     }
  197. }

注：这里以实现第二种顺序队列为例。

对(数组)循环队列的(简单)实现：

  1. import java.io.Serializable;
  2. import java.util.Arrays;
  4. /**
  5.  * (简单实现)循环队列
  6.  *
  7.  * @author JustryDeng
  8.  * @date 2019/5/18 18:58
  9.  */
  10. public class CircleQueue<E> implements Serializable {
  12.     /** 元素容器 */
  13.     private final Object[] items;
  15.     /** 队列的容量(即:数组的长度) */
  16.     private int capacity;
  18.     /** 队头 */
  19.     private int front;
  21.     /** 队尾 */
  22.     private int rear;
  24.     /**
  25.      * 构造器
  26.      *
  27.      * @param capacity
  28.      *         队列的容量
  29.      * @date 2019/5/18 21:55
  30.      */
  31.     public CircleQueue(int capacity) {
  32.         this.capacity = capacity;
  33.         items = new Object[capacity];
  34.         front = 0;
  35.         rear = 0;
  36.     }
  38.     /**
  39.      * 入队
  40.      *
  41.      * @param e
  42.      *         入队的元素
  43.      * @date 2019/5/18 22:27
  44.      */
  45.     public void offer(E e) {
  46.         if (e == null) {
  47.             throw new IllegalArgumentException("arg must be not null!");
  48.         }
  49.         if (rear - front >= capacity) {
  50.             throw new MyQueueException("the queue already full!");
  51.         }
  52.         int currIndex = rear % capacity;
  53.         items[currIndex] = e;
  54.         rear++;
  55.     }
  57.     /**
  58.      * 出队
  59.      *
  60.      * @return 出队的那个元素
  61.      * @date 2019/5/18 22:25
  62.      */
  63.     public E poll() {
  64.         if (isEmpty()) {
  65.             throw new MyQueueException("the queue is empty!");
  66.         }
  67.         int currIndex = front % capacity;
  68.         E oldValue = itemAt(currIndex);
  69.         items[currIndex] = null;
  70.         front++;
  71.         return oldValue;
  72.     }
  74.     /**
  75.      * 返回队列头元素,但不会将该元素出列
  76.      *
  77.      * @return 队列头元素
  78.      * @date 2019/5/18 22:07
  79.      */
  80.     public E peek() {
  81.         if (isEmpty()) {
  82.             throw new MyQueueException("the queue is empty!");
  83.         }
  84.         return itemAt(front % capacity);
  85.     }
  87.     /**
  88.      * 返回指定位置处的元素
  89.      *
  90.      * @param index
  91.      *         索引位置
  92.      * @return 返回index位置处的元素
  93.      * @date 2019/5/18 22:21
  94.      */
  95.     @SuppressWarnings("unchecked")
  96.     public E itemAt(int index) {
  97.         return (E) items[index];
  98.     }
  100.     /**
  101.      * 判断队列是否为空队列
  102.      *
  103.      * @return 是/否
  104.      * @date 2019/5/18 22:04
  105.      */
  106.     public boolean isEmpty() {
  107.         return rear == front;
  108.     }
  110.     /**
  111.      * 判断队列是否已满
  112.      *
  113.      * @return  是/否
  114.      * @date 2019/5/18 22:04
  115.      */
  116.     public boolean isFull() {
  117.         return rear - front >= capacity;
  118.     }
  120.     /**
  121.      * 获取队列的实际有效大小(即:获取队列中元素的个数)
  122.      *
  123.      * @return 获取当前队列的大小
  124.      * @date 2019/5/18 21:54
  125.      */
  126.     public int size() {
  127.         return rear - front;
  128.     }
  130.     /**
  131.      * 清空队列
  132.      *
  133.      * @date 2019/5/18 22:04
  134.      */
  135.     public void clear() {
  136.         // 将数组所有元素赋为null
  137.         Arrays.fill(items, null);
  138.         // 首尾指针重置
  139.         front = 0;
  140.         rear = 0;
  141.     }
  143.     @Override
  144.     public String toString() {
  145.         if (isEmpty()) {
  146.             return "[]";
  147.         } else {
  148.             StringBuilder sb = new StringBuilder("[");
  149.             int curIndex;
  150.             for (int i = front; i < rear; i++) {
  151.                 curIndex = i % capacity;
  152.                 sb.append(items[curIndex].toString())
  153.                   .append(", ");
  154.             }
  155.             int len = sb.length();
  156.             return sb.delete(len - 2, len).append("]").toString();
  157.         }
  158.     }
  160.     /**
  161.      * 测试一下
  162.      *
  163.      * @author JustryDeng
  164.      * @date 2019/5/19 1:14
  165.      */
  166.     public static void main(String[] args) {
  167.         CircleQueue<String> queue = new CircleQueue<>(5);
  168.         // 入队
  169.         queue.offer("A");
  170.         queue.offer("B");
  171.         queue.offer("C");
  172.         queue.offer("D");
  173.         // 出队(出队后，元素就不在队列中了)
  174.         System.out.println(queue.poll());
  175.         System.out.println(queue.poll());
  176.         // 队列是否为空
  177.         System.out.println(queue.isEmpty());
  178.         // 队列中元素个数
  179.         System.out.println(queue.size());
  180.         // 获取队列中的头元素(此操作后，该元素仍然在队列中)
  181.         System.out.println(queue.peek());
  182.         // 入队
  183.         queue.offer("E");
  184.         queue.offer("F");
  185.         queue.offer("G");
  186.         // 验证queue的toString函数
  187.         System.out.println(queue);
  188.         // 队列是否已满
  189.         System.out.println(queue.isFull());
  190.         // 清空队列
  191.         queue.clear();
  192.         // 验证queue的toString函数
  193.         System.out.println(queue);
  194.         // 队列是否已满
  195.         System.out.println(queue.isFull());
  196.     }
  198. }

对链表队列的(简单)实现：

  1. import java.io.Serializable;
  3. /**
  4.  * (简单实现)链式(链表)队列
  5.  *
  6.  * @author JustryDeng
  7.  * @date 2019/5/19 1:32
  8.  */
  9. public class LinkQueue<E> implements Serializable{
  11.     private static final long serialVersionUID = 3748038449750184916L;
  13.     /**
  14.      * 定义一个内部类Node，Node实例代表链队列的节点
  15.      *
  16.      * @author JustryDeng
  17.      * @date 2019/5/19 1:31
  18.      */
  19.     private class Node {
  21.         /** 此节点的数据 */
  22.         private E data;
  24.         /** 指向下个节点的引用 */
  25.         private Node next;
  27.         /** 全参构造 */
  28.         private Node(E data, Node next) {
  29.             this.data = data;
  30.             this.next = next;
  31.         }
  32.     }
  34.     /** 头节点 */
  35.     private Node front;
  37.     /** 尾节点 */
  38.     private Node rear;
  40.     /** 此链式队列中已包含的节点数 */
  41.     private int size;
  43.     /**
  44.      * 空链队列 构造
  45.      */
  46.     public LinkQueue() {
  47.         front = null;
  48.         rear = null;
  49.         size = 0;
  50.     }
  52.     /**
  53.      * 入队
  54.      *
  55.      * @param e
  56.      *         入队的元素
  57.      * @date 2019/5/19 1:36
  58.      */
  59.     public void offer(E e) {
  60.         // 如果该链队列还是空链队列
  61.         if (front == null) {
  62.             if (e == null) {
  63.                 throw new IllegalArgumentException("arg must be not null!");
  64.             }
  65.             front = new Node(e, null);
  66.             // 只有一个节点，front、rear都指向该节点
  67.             rear = front;
  68.         } else {
  69.             // 创建新节点
  70.             Node newNode = new Node(e, null);
  71.             // 让当前尾节点的next指向新增的节点
  72.             rear.next = newNode;
  73.             // 更新尾节点引用，以新节点作为新的尾节点
  74.             rear = newNode;
  75.         }
  76.         size++;
  77.     }
  79.     /**
  80.      * 出队
  81.      *
  82.      * @return 出队的那个元素
  83.      * @date 2019/5/18 22:25
  84.      */
  85.     public E poll() {
  86.         if (isEmpty()) {
  87.             throw new MyQueueException("the queue is empty!");
  88.         }
  89.         Node oldFront = front;
  90.         front = front.next;
  91.         oldFront.next = null;
  92.         size--;
  93.         return oldFront.data;
  94.     }
  96.     /**
  97.      * 返回队列头元素,但不会将该元素出列
  98.      *
  99.      * @return 队列头元素
  100.      * @date 2019/5/18 22:07
  101.      */
  102.     public E peek() {
  103.         if (isEmpty()) {
  104.             throw new MyQueueException("the queue is empty!");
  105.         }
  106.         return front.data;
  107.     }
  109.     /**
  110.      * 判断队列是否为空队列
  111.      *
  112.      * @return 是/否
  113.      * @date 2019/5/18 22:04
  114.      */
  115.     public boolean isEmpty() {
  116.         return size == 0;
  117.     }
  119.     /**
  120.      * 获取此链式队列中已包含的节点数
  121.      *
  122.      * @return  此链式队列中已包含的节点数
  123.      * @date 2019/5/19 1:36
  124.      */
  125.     public int size() {
  126.         return size;
  127.     }
  129.     /**
  130.      * 清空队列
  131.      *
  132.      * @date 2019/5/18 22:04
  133.      */
  134.     public void clear() {
  135.         front = null;
  136.         rear = null;
  137.         size = 0;
  138.     }
  140.     @Override
  141.     public String toString() {
  142.         // 链队列为空链队列时
  143.         if (isEmpty()) {
  144.             return "[]";
  145.         } else {
  146.             StringBuilder sb = new StringBuilder("[");
  147.             for (Node current = front; current != null; current = current.next) {
  148.                 sb.append(current.data.toString())
  149.                   .append(", ");
  150.             }
  151.             int len = sb.length();
  152.             return sb.delete(len - 2, len).append("]").toString();
  153.         }
  154.     }
  156.     /**
  157.      * 测试一下
  158.      *
  159.      * @author JustryDeng
  160.      * @date 2019/5/19 1:14
  161.      */
  162.     public static void main(String[] args) {
  163.         LinkQueue<String> queue = new LinkQueue<>();
  164.         // 入队
  165.         queue.offer("A");
  166.         queue.offer("B");
  167.         queue.offer("C");
  168.         // 出队(出队后，元素就不在队列中了)
  169.         System.out.println(queue.poll());
  170.         System.out.println(queue.poll());
  171.         // 队列是否为空
  172.         queue.offer("D");
  173.         queue.offer("E");
  174.         System.out.println(queue.isEmpty());
  175.         // 队列中元素个数
  176.         System.out.println(queue.size());
  177.         // 获取队列中的头元素(此操作后，该元素仍然在队列中)
  178.         System.out.println(queue.peek());
  179.         // 入队
  180.         queue.offer("F");
  181.         queue.offer("G");
  182.         // 验证queue的toString函数
  183.         System.out.println(queue);
  184.         // 清空队列
  185.         queue.clear();
  186.         // 验证queue的toString函数
  187.         System.out.println(queue);
  188.         // 队列中元素个数
  189.         System.out.println(queue.size());
  190.     }
  191. }

#

^_^ 如有不当之处，欢迎指正

^_^ 参考链接 https://baike.baidu.com/item/%E9%…7/14580481?fr=aladdin https://blog.csdn.net/zhang21722668/article/details/82155301 https://www.jb51.net/article/130858.htm

^_^ 学习视频 51CTO学院《数据结构与算法》，讲师张晨光

^_^ 本文已被收录进《程序员成长笔记(五)》，笔者JustryDeng

发表评论

表情：
评论列表 （有 0 条评论，355人围观）

还没有评论，来说两句吧...

相关阅读

    相关 数据结构之队列

    概述 在java5中新增加了[Java][].util.Queue接口，用以支持队列的常见操作。Queue接口与List、Set同一级别，都是继承了Collection接

    桃扇骨桃扇骨/ 0 赞/ 215 阅读

    相关 数据结构之队列

    一、 队列的顺序存储结构及实现 1.0 啥叫队列 栈就相当往杯子里放东西，而队列就相当于往管子里放水，只能这头进，那头出 队列就是只允许在一段进行插入操作，另一端

    旧城等待，旧城等待，/ 0 赞/ 256 阅读

    相关 数据结构之队列

    概念 可以把队列想象成排队买票，先来的人先买，后来的人站在队尾排队后买，不允许插队，先进者先出，这就是典型的“队列”。 特点 先进者先出，后进者后出，不允许在中间

    素颜马尾好姑娘i素颜马尾好姑娘i/ 0 赞/ 252 阅读

    相关 数据结构之队列

    数据结构队列的相关学习： 简介 队列是是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。 队列是一种先进先出的线性表，简称FIFO允许插入的以端称为队尾，

    小灰灰小灰灰/ 0 赞/ 295 阅读

    相关 【数据结构】之队列

    笔者日常：         感谢孤尽(花名)大侠今天给我解答线程安全的问题，在这里推荐孤大侠书籍《码出高效》，带你深入基础，走进阿里规范！ ---------------

    悠悠悠悠/ 0 赞/ 356 阅读