队列是什么？

队列是一种先进先出的数据结构。

跟栈一样，队列也是一种操作受限的线性表数据结构。

用数组实现一个队列

如果用数组来实现一个栈，我们只需要一个栈顶指针就够了。但是队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。

下面用代码来实现一个数组队列：

 1 // 用数组实现的队列
 2 public class ArrayQueue {
 3   // 数组：items，数组大小：n
 4   private String[] items;
 5   private int n = 0;
 6   // head 表示队头下标，tail 表示队尾下标
 7   private int head = 0;
 8   private int tail = 0;
 9 
10   // 申请一个大小为 capacity 的数组
11   public ArrayQueue(int capacity) {
12     items = new String[capacity];
13     n = capacity;
14   }
15 
16   // 入队
17   public boolean enqueue(String item) {
18     // 如果 tail == n 表示队列已经满了
19     if (tail == n) {
20         return false;
21     }
22     items[tail] = item;
23     ++tail;
24     return true;
25   }
26 
27   // 出队
28   public String dequeue() {
29     // 如果 head == tail 表示队列为空
30     if (head == tail) {
31         return null;
32     }
33     String ret = items[head];
34     ++head;
35     return ret;
36   }
37 }

用链表实现一个队列

基于链表实现的队列，同样需要两个指针：head 指针和 tail 指针，分别指向链表的第一个结点和最后一个结点。

下面用代码来实现一个链表队列：

 1 public class QueueBasedOnLinkedList {
 2 
 3   // 队列的队首和队尾
 4   private Node head = null;
 5   private Node tail = null;
 6 
 7   // 入队
 8   public void enqueue(String value) {
 9     if (tail == null) {
10       Node newNode = new Node(value, null);
11       head = newNode;
12       tail = newNode;
13     } else {
14       tail.next = new Node(value, null);
15       tail = tail.next;
16     }
17   }
18 
19   // 出队
20   public String dequeue() {
21     if (head == null) {
22       return null;
23     }
24     String value = head.data;
25     head = head.next;
26     if (head == null) {
27       tail = null;
28     }
29     return value;
30   }
31 
32   public void printAll() {
33     Node p = head;
34     while (p != null) {
35       System.out.print(p.data + " ");
36       p = p.next;
37     }
38     System.out.println();
39   }
40 
41   private static class Node {
42     private String data;
43     private Node next;
44 
45     public Node(String data, Node next) {
46       this.data = data;
47       this.next = next;
48     }
49 
50     public String getData() {
51       return data;
52     }
53   }
54 
55 }

循环队列

当我们用数组实现队列的时候，若 tail==n && head!=0 时，即队列末尾没有空间但整个队列未满的时候，会有数组搬移操作，这样入队操作性能就会受到影响，这种时候可以用循环队列来解决这个问题。

在用数组实现的非循环队列中，队满的判断条件是 tail==n，队空的判断条件是 head==tail。

针对循环队列，队空的判断条件仍然是 head==tail，但队列满的判断条件为 (tail+1)%n=head。

下面用代码来实现一个循环队列：

 1 public class CircularQueue {
 2   // 数组：items，数组大小：n
 3   private String[] items;
 4   private int n = 0;
 5   // head 表示队头下标，tail 表示队尾下标
 6   private int head = 0;
 7   private int tail = 0;
 8 
 9   // 申请一个大小为 capacity 的数组
10   public CircularQueue(int capacity) {
11     items = new String[capacity];
12     n = capacity;
13   }
14 
15   // 入队
16   public boolean enqueue(String item) {
17     // 队列满了
18     if ((tail + 1) % n == head) {
19       return false;
20     }
21     items[tail] = item;
22     tail = (tail + 1) % n;
23     return true;
24   }
25 
26   // 出队
27   public String dequeue() {
28     // 如果 head == tail 表示队列为空
29     if (head == tail) {
30       return null;
31     }
32     String ret = items[head];
33     head = (head + 1) % n;
34     return ret;
35   }
36 }