知识前提
利用数组实现
普通队列
优化队列
循环队列
利于优化
利用链表实现
普通链表队列
不易优化
队列二要素：入队，出队
头结点：
- 删除指定位置元素
- 判断队列是否为空
尾结点：
- 指定新元素的插入位置
- 通过尾结点判断队列是否满了，如果满了，就禁止插入
- 判断队列是否为空
顺序队列
基础队列
public class Queue {
int n = 0;
String[] items;
int head;
int tail;
public Queue(int capacity) {
n = capacity;
items = new String[capacity];
}
public boolean enqueue(String item) {
//如果队列满
if (tail == n) return false;
items[tail++] = item;
return true;
}
public String dequeue() {
if (head == tail) return null;
return items[head++];
}
public static void main(String[] args) {
Queue a = new Queue(10);
a.enqueue("10");
a.enqueue("20");
String dequeItem = a.dequeue();
System.out.println(dequeItem.equals("10"));
a.enqueue("30");
System.out.println(a.items[a.head].equals("20"));
System.out.println(a.items[a.tail - 1].equals("30"));
}
}
加入数据迁移的队列
上一种队列会越用越小，就需要对数据进行迁移，实现队列的自动整理。
public class Queue {
private String[] items;
private int n = 0;
private int head = 0;
private int tail = 0;
public tmp(int capacity) {
n = capacity;
items = new String[n];
}
public boolean enqueue(String item) {
if (tail == n) {
if (head == 0) return false;
for (int i = head; i < tail; ++i) {
items[i-head] = items[i];
}
tail -= head;
head = 0;
}
items[tail] = item;
++tail;
return true;
}
public String dequeue() {
if (head == tail)
return null;
return items[head++];
}
public static void main(String[] args) {
Queue a = new Queue(3);
a.enqueue("10");
a.enqueue("20");
a.enqueue("30");
boolean result = a.enqueue("40");
System.out.println(!result);
String dequeItem = a.dequeue();
System.out.println(dequeItem.equals("10"));
a.enqueue("30");
System.out.println(a.items[0].equals("20"));
System.out.println(a.items[2].equals("30"));
}
}
链式队列
public class Queue {
Node head = null;
Node tail = null;
public void enqueue(String item) {
if (tail == null) {
Node newNode = new Node(item);
head = newNode;
tail = newNode;
}else {
tail.next = new Node(item);
tail = tail.next;
}
}
public String dequeue() {
if (head == null) return null;
String value = head.data;
head = head.next;
return value;
}
public static void main(String[] args) {
Queue a = new Queue();
a.enqueue("10");
a.enqueue("20");
a.enqueue("30");
String dequeItem = a.dequeue();
System.out.println(dequeItem == "10");
System.out.println(a.head.data == "20");
System.out.println(a.head.next.data == "30");
}
public static class Node {
String data;
Node next = null;
public Node(String data) {
this.data = data;
}
}
}
循环队列
public class Queue {
int n = 0;
String[] items;
int head = 0;
int tail = 0;
public Queue(int capacity) {
n = capacity;
items = new String[capacity];
}
public boolean enqueue(String item) {
if ((tail + 1) % n == head)
return false;
items[tail] = item;
tail = (tail + 1) % n;
return true;
}
public String dequeue() {
if (head == tail)
return null;
String value = items[head];
head = (head + 1) % n;
return value;
}
public static void main(String[] args) {
Queue a = new Queue(3);
a.enqueue("10");
a.enqueue("20");
boolean result = a.enqueue("30");
// 循环队列需要空出一格
System.out.println(!result);
String dequeItem = a.dequeue();
a.enqueue("30");
System.out.println(a.items[2] == "30");
result = a.enqueue("10");
System.out.println(result == false);
}
}
阻塞队列
入队和出队可以等待
并发队列
支持多线程的阻塞队列