《数据结构与算法之美》——队列《数据结构与算法之美》—

什么是队列

队列是一种线性表数据结构，和栈类似
它操作受限，表现为先进先出，后进后出
它有头指针和尾指针之分，删除元素从head操作，添加元素从tail操作

基于以上特点，我们看到队列是这样的

文章图片
image.png 常见的队列
队列的花样比较多，这源于它的灵活性和众多的应用场景。
比如当初在学习数据结构这门课的时候，肯定听说过循环队列。
了解Java并发的时候，肯定知道并发队列
顺序队列和链式队列
和前面的栈数据结构一样，使用数组实现的队列就是顺序队列，使用链表实现的队列就是链式队列。
使用数组结构实现的队列

package com.jackie.algo.geek.time.chapter9_queue; /** * @Author: Jackie * @date 2018/12/15 * * 基于数组数据结构的队列实现 */ public class ArrayQueue { // 数组items private String[] items; // 数组大小 private int n = 0; // 数组头下标 private int head = 0; // 数组尾下标 private int tail = 0; public ArrayQueue(int capacity) { items = new String[capacity]; n = capacity; } /** * 入队 */ public boolean enqueue(String ele) { // 队列满了 if (tail == n) { return false; } items[tail++] = ele; return true; } /** * 出队 */ public String dequeue() { if (head == tail) { return null; } return items[head++]; } /** * 打印所有队列元素 */ public void printAll() { for (int i = head; i < tail; i++) { System.out.print(items[i] + " "); } System.out.println(); } }

使用链表结构实现的队列

package com.jackie.algo.geek.time.chapter9_queue; /** * @Author: Jackie * @date 2018/12/15 * * 基于链表数据结构的队列实现 * 注意：和基于数据实现的队列{@link ArrayQueue}不同，这里没有n这个参数， * 因为基于链表实现是无界的，基于数据实现需要定于数组的大小 */ public class LinkedQueue { // 头指针 private Node head = null; // 尾指针 private Node tail = null; /** * 入队 */ public void enqueue(String ele) { if (head == null) { Node node = new Node(ele, null); head = node; tail = node; } else { tail.next = new Node(ele, null); tail = tail.next; } } /** * 出队 */ public String dequeue() { if (head == null) { return null; } String ret = head.data; head = head.next; // 如果出队后，头指针head为null，则同时置tail为null if (head == null) { tail = null; } return ret; } public void printAll() { Node p = head; if (p != null) { System.out.print(p.data + " "); p = p.next; } System.out.println(); } private static class Node { private String data; private Node next; public Node(String data, Node next) { this.data = https://www.it610.com/article/data; this.next = next; } public String getData() { return data; } } }

具体代码，参见GitHub项目rome
顺序队列和链式队列的不同点

顺序队列使用数组实现，所以有数组大小的限制，在数据结构中有对应的属性n
顺序队列队空条件为：head == tail; 队满条件为：tail == n。
链式队列队空条件为：head == null; 队满条件要取决于队列的长度

数据搬移在队列中，随着数据的进进出出，head和tail会不断移动，就顺序队列举例来说，当tail == n是就无法入队了，会出现空闲内存，如下图

文章图片
image.png 这样下去，会造成更多的内存浪费，无法存储更多的数据。所以，需要进行数据搬移，具体过程如下

文章图片
image.png 代码实现也比较简单，具体如下

// 入队操作，将 item 放入队尾 public boolean enqueue(String item) { // tail == n 表示队列末尾没有空间了 if (tail == n) { // tail ==n && head==0，表示整个队列都占满了 if (head == 0) return false; // 数据搬移 for (int i = head; i < tail; ++i) { items[i-head] = items[i]; } // 搬移完之后重新更新 head 和 tail tail -= head; head = 0; } items[tail] = item; ++tail; return true; }

循环队列
针对上面提到的tail == n无法入队的情况，除了数据搬移，还可以使用这里的循环队列来解决。
循环队列是将上面提到的队列首尾相接形成的环形队列。
不同于顺序队列的队空条件head==tail和队满条件tail==n。
【《数据结构与算法之美》——队列】循环队列的队空条件依然是head==tail，队满的条件为：（tail+1）%n = head