共计 1844 个字符，预计需要花费 5 分钟才能阅读完成。
1. 概述
前面说完了栈，接下来再看看另一种很基础的数据结构，队列。顾名思义，队列跟我们现实生活中的排队很相似：例如我们在食堂排队打饭，先来的先打到，后来的只能一次排在后面，不允许插队。很明显，队列的操作也是受限的，插入元素（入队）只能在队尾，删除元素（出队）只能在队头。结合下面的图就很容易理解了：
2. 队列实现
和栈一样，队列也有两种实现方式，使用数组实现的队列叫做顺序队列，使用链表实现的队列叫做链式队列。这里我实现了链式队列，你也可以根据其思想使用数组来实现。
public class LinkedListQueue {
private Node head;// 队头节点指针
private Node tail;// 队尾节点指针
private int size;// 队列中元素个数
public LinkedListQueue() {
this.head = null;
this.tail = null;
this.size = 0;
}
// 入队
public boolean enqueue(String value) {
Node node = new Node(value);
if(tail == null) {
head = tail = node;
this.size ++;
return true;
}
tail.next = node;
tail = node;
this.size ++;
return true;
}
// 出队列
public String dequeue() {
if(head == null) return null;// 队列为空
String result = head.getData();
head = head.next;
this.size –;
return result;
}
// 定义链表节点
public static class Node{
private String data;
private Node next;
public Node(String data) {
this.data = data;
this.next = null;
}
public String getData() {
return data;
}
}
}
3. 循环队列
在使用数组实现队列的时候，会出现一个问题，就是随着队头和队尾指针的后移，就算数组中还有空间，也不能进行入队操作了。这时候我们需要进行数据搬移，性能会受到影响，而循环队列解决了这个问题。
循环队列就是将数组首尾相连，形成了一个环形：
如上图，当指针 tail 到达数组末尾的时候，并不进行数据搬移，而是直接将指针向前移，到达了 0 这个位置。在进行一次入队，就变成了下面的样子：
可以看到，循环队列判断空的条件是 head == tail，而怎么判断队列满呢？答案是（tail + 1）== head 的时候，队列就满了，不能看出循环队列实际上浪费了一个存储空间。下面我给出了循环队列的代码实现：
public class CircularQueue {
private String[] items;
private int size;
private int head;
private int tail;
public CircularQueue(int capacity) {
this.items = new String[capacity];
this.size = 0;
this.head = 0;
this.tail = 0;
}
public CircularQueue() {
this(16);
}
// 入队列
public boolean enqueue(String value) {
if((tail + 1) % items.length == head) return false;// 队列已满
items[tail] = value;
//head 和 tail 指针的移动不是简单的加减 1 了
tail = (tail + 1) % items.length;
this.size ++;
return true;
}
// 出队列
public String dequeue() {
if(head == tail) return null;// 队列为空
String result = items[head];
head = (head + 1) % items.length;
this.size –;
return result;
}
// 队列中元素个数
public int size() {
return size;
}
// 打印队列中数据
public void print() {
int h = head;
int t = tail;
while(h != t) {
System.out.print(items[h] + ” “);
h = (h + 1) % items.length;
}
System.out.println();
}
}
