队列中典型的就是遵循先进先出原则的，队列是操作受限制的线性表结构。
一、队列的特点
队列最大的特点就是先进先出，主要有两个操作入列和出列。
跟栈一样，既可以用数组实现，又可以用链表实现，用数组实现叫顺序队列，用链表实现，叫链式队列，特别是一个长的像环的循环队列。
在数组实现队列的时候，会有数据搬移操作，要想解决数据搬移的问题，我们就需要像环一样的循环队列。
二、基于数组实现的队列
1 public class ArrayQueue { 2 3 // 数组：items 数组的大小：n 4 private String[] items; 5 6 private int n = 0; 7 8 // head表示对头下标 tail表示队尾下标 9 private int head = 0; 10 11 private int tail = 0; 12 13 /** 14 * 申请一个大小为capacity的数组 15 * 16 * @param capacity 17 */ 18 public ArrayQueue(int capacity) { 19 this.items = new String[capacity]; 20 this.n = capacity; 21 } 22 23 /** 24 * 入列操作 25 * 26 * @param item 27 * @return 28 */ 29 public boolean enqueue(String item) { 30 // 如果tail == n 表示队列满了 31 if (tail == n) { 32 return false; 33 } 34 this.items[tail] = item; 35 ++tail; 36 return true; 37 } 38 39 /** 40 * 出列操作 41 * 42 * @return 43 */ 44 public String dequeue() { 45 // 如果 head == tail 表示队列为空 46 if (this.head == this.tail) { 47 return null; 48 } 49 String ret = this.items[head]; 50 ++head; 51 return ret; 52 } 53 54 /** 55 * 随着不停的入列，出列操作，当tail移动到最后一个数组位置的时候，即使数组中前面还有空余空间也无法在队列中添加数据了，解决这个问题的 56 * 办法是进行数据搬移，将队列后面的数据搬移到前面空余的位置中，改造入队操作，若空间不足，触发数据搬移 57 * 58 */ 59 60 /** 61 * 改造之后的入列操作 62 * 63 * @param item 64 * @return 65 */ 66 public boolean enqueue2(String item) { 67 // tail == n 表示队列中没有剩余空间了 68 if (tail == n) { 69 // tail == n && head == 0表示整个队列都占满了 70 if (head == 0) { 71 return false; 72 } 73 // 数据搬移 74 for (int i = head; head < tail; ++i) { 75 this.items[i - head] = this.items[i]; 76 } 77 // 搬移之后重新更新 head tail 向前移动了head距离 78 tail -= head; 79 head = 0; 80 } 81 this.items[tail] = item; 82 ++tail; 83 return true; 84 } 85 86 }
三、基于链表实现的队列
1 public class QueueBasedOnLinkedList { 2 3 //队列的队首 和 队尾 4 private Node head = null; 5 private Node tail = null; 6 7 /** 8 * 入列操作 9 * 10 * @param value 11 */ 12 public void enqueue(String value){ 13 if(tail == null){ 14 Node newNode = new Node(value, null); 15 head = newNode; 16 tail = newNode; 17 }else{ 18 tail = new Node(value, null); 19 tail.next = tail; 20 } 21 } 22 23 /** 24 * 出列操作 25 * 26 * @return 27 */ 28 public String dequeue(){ 29 if(head == null){ 30 return null; 31 } 32 String value = head.data; 33 head = head.next; 34 if(head == null){ 35 tail = null; 36 } 37 return value; 38 } 39 40 public void printAll(Node node){ 41 while(node != null){ 42 System.out.print(node.data + " "); 43 node = node.next; 44 } 45 System.out.println(); 46 } 47 48 public static class Node{ 49 private String data; 50 private Node next; 51 52 public Node(String data, Node next){ 53 this.data = data; 54 this.next = next; 55 } 56 57 public String getData(){ 58 return this.data; 59 } 60 } 61 }
四、环形队列
1 public class CircularQueue { 2 3 // 数组：items 数组长度：n 4 private String[] items; 5 private int n = 0; 6 7 // head 表示对头下标 tail表示队尾下标 8 private int head = 0; 9 private int tail = 0; 10 11 /** 12 * 申请一个大小为capacity 的数组 13 * 14 * @param capacity 15 */ 16 public CircularQueue(int capacity) { 17 this.items = new String[capacity]; 18 this.n = capacity; 19 } 20 21 /** 22 * 入列操作 23 * 24 * @return 25 */ 26 public boolean enqueue(String item) { 27 // 队列满了 28 if ((tail + 1) % n == head) { 29 return false; 30 } 31 this.items[tail] = item; 32 tail = (tail + 1) % n; 33 return true; 34 } 35 36 /** 37 * 出列操作 38 * 39 * @return 40 */ 41 public String dequeue() { 42 // 如果head = tail 表示队列为空 43 if (head == tail) { 44 return null; 45 } 46 String ret = items[head]; 47 head = (head + 1) % n; 48 return ret; 49 } 50 51 }
此大部分内容来自极客时间专栏，王争老师的《数据结构与算法之美》
极客时间：https://time.geekbang.org/column/intro/126