队列是什么？
队列是一种先进先出的数据结构。
跟栈一样，队列也是一种操作受限的线性表数据结构。
用数组实现一个队列
如果用数组来实现一个栈，我们只需要一个栈顶指针就够了。但是队列需要两个指针：一个是 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 }
阻塞队列和并发队列
阻塞队列就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有数据了才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
并发队列就是在多线程情况下，实现的一个避免线程安全问题的队列。最简单的实现方式就是在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。
内容小结
- 队列最大的特点就是先进先出，主要的两个操作是入队和出队。
- 队列和栈一样，既可以用数组来实现，也可以用链表来实现。
（PS：最近比较忙，没那么多时间认真学习算法课程，就先看一下课程大概内容，记一些笔记而已，起码掌握一下算法思想，等忙完这段时间再进行补充。）
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
