一、队列的实现
1. 队列抽象接口
package com.douma.line.queue;
public interface Queue<E> {
/**
* 查询队列中的元素个数
* @return
*/
int getSize();
/**
* 判断队列是否为空
* @return
*/
boolean isEmpty();
/**
* 入队
* @param e
*/
void enqueue(E e);
/**
* 出队
* @return
*/
E dequeue();
/**
* 查看队首的元素
* @return
*/
E getFront();
}
2. 数组实现队列
将数组的左端当队首，右端当做队尾。
还有一个问题就是，我们应该用动态数组还是静态数组？ 使用动态数组。
public class ArrayQueue<E> implements Queue<E> {
private ArrayList<E> data; //使用动态数组。
public ArrayQueue() {
data = new ArrayList<>();
}
@Override
public int getSize() {
return data.getSize();
}
@Override
public boolean isEmpty() {
return data.isEmpty();
}
@Override
public void enqueue(E e) { // O(1)
data.addLast(e);
}
@Override
public E dequeue() { // O(n)
return data.removeFirst();
}
@Override
public E getFront() {
return data.getFirst();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Queue：队首 [");
for (int i = 0; i < data.getSize(); i++) {
res.append(data.get(i));
if (i != data.getSize() - 1) {
res.append(", ");
}
}
res.append("]");
return res.toString();
}
}
3. 链表实现队列
这里使用表尾作为队尾，表头为队头。
public class LinkedListQueue<E> implements Queue<E> {
private LinkedList<E> data;
public LinkedListQueue() {
data = new LinkedList<>();
}
@Override
public int getSize() {
return data.getSize();
}
@Override
public boolean isEmpty() {
return data.isEmpty();
}
@Override
public void enqueue(E e) { // 入队，队尾入队
data.addLast(e); // O(n)
}
@Override
public E dequeue() { // 出队
return data.removeFirst(); // O(1)
}
@Override
public E getFront() {
return data.getFirst();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Queue：队首 [");
for (int i = 0; i < data.getSize(); i++) {
res.append(data.get(i));
if (i != data.getSize() - 1) {
res.append(", ");
}
}
res.append("]");
return res.toString();
}
}
二、 循环队列（优化数组实现队列）
public class LoopQueue<E> implements Queue<E> {
private E[] data;
private int head; //head指针指向第一个元素的位置
private int tail; // tail指针指向最后一个元素的下一个位置
private int size;
public LoopQueue() {
this(20);
}
public LoopQueue(int capacity) {
data = (E[])new Object[capacity];
head = tail = 0;
size = 0;
}
// 当前队列的容量
public int getCapacity() {
return data.length - 1;
}
@Override
public int getSize() {
return size;
}
@Override
public void enqueue(E e) {
if ((tail + 1) % data.length == head) {
// 队列满了 tail + 1 == head 表明队列已满，
// 这里浪费一个存储空间。
// tail + 1 有可能越界
resize(getCapacity() * 2);
}
data[tail] = e;
size++;
tail = (tail + 1) % data.length;
}
@Override
public E dequeue() { // O(1)
if (isEmpty()) {
throw new RuntimeException("dequeue error, No Element for dequeue");
}
E res = data[head];
data[head] = null;
size--;
head = (head + 1) % data.length;
if (size == getCapacity() / 4) {
resize(getCapacity() / 2);
}
return res;
}
// 扩容
private void resize(int newCapacity) {
E[] newData = (E[])new Object[newCapacity + 1];
for (int i = 0; i < size; i++) {
// 怎么赋值呢？newData 从0开始，拷贝Date的head开始
newData[i] = data[(i + head) % data.length];
}
data = newData;
head = 0;
tail = size;
}
@Override
public E getFront() {
return data[head];
}
@Override
public boolean isEmpty() {
return head == tail;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(String.format("Queue：size = %d, capacity = %d\n", size, getCapacity()));
sb.append(" 队首 [");
for (int i = head; i != tail ; i = (i + 1) % data.length) {
sb.append(data[i]);
if ((i + 1) % data.length != tail) {
sb.append(",");
}
}
sb.append("]");
return sb.toString();
}
}
三、优化链表实现队列
public class LinkedListQueue2<E> implements Queue<E> {
private class Node {
E e;
Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
public Node() {
this(null, null);
}
@Override
public String toString() {
return e.toString();
}
}
private Node head;
private Node tail;
private int size;
public LinkedListQueue2() {
head = null;
tail = null;
size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void enqueue(E e) { // O(1)
Node newNode = new Node(e);
if (tail == null) {
tail = newNode;
head = tail;
} else {
tail.next = newNode;
tail = newNode;
}
size++;
}
@Override
public E dequeue() { // O(1)
if (isEmpty()) {
throw new RuntimeException("dequeue error, no element");
}
// 先记住第一个节点
Node delNode = head;
head = head.next;
delNode.next = null;
// 如果队列中只有一个元素
if (head == null) {
tail = null;
}
size--;
// 出队
return delNode.e;
}
// 拿到队首元素
@Override
public E getFront() {
if (isEmpty()) {
throw new RuntimeException("getFront error, no element");
}
return head.e;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Queue：队首 [");
Node curr = head;
while (curr != null) {
res.append(curr + "->");
curr = curr.next;
}
res.append("null]");
return res.toString();
}
}
四、Java中的队列
1. 队列的容量
没有容量限制的队列：数组队列、链表队列、循环队列。易导致内存溢出，有风险。
有容量限制的队列：队列只能存储指定个数的元素。使用场景更加广泛。
2. 双端队列（Deque：Double ends queue）
在队列的两端都可进行入队出队操作。
3. Java内置队列的继承实现体系
Java Queue（队列）中方法讲解：
java.util.Queue<E>
-
add() offer()
add 和 offer方法 的作用都是入队，它们的区别是：（1）如果队列的容量是没有限制的，那么使用add和offer效果一样。（2）当队列的容量是有限制的，那么：当队列还没满的时候，offer和add效果一样；当队列已经满了，调用add的时候会抛 IllegalSateException异常，而offer不会抛异常，只是返回false。
remove 和 poll的方法都是出队，它们的区别在于队列为空的时候：（1）对空队列进行remove会抛NoSuchElementException异常。（2）对空队列进行poll，会返回null。
element 和 peek方法的作用都是看一眼队首元素，它们的区别在于队列为空的时候：（1）对空队列进行element会抛NoSuchElementException异常。(2) 对空队列进行peek则返回null。
Java Queue（双端队列）中方法讲解：
java.util.Deque<E>
继承 Queue 的方法
addFirst(E e):void
addLast(E e):void
offerFirst(E e):boolean
offerLast(E e):boolean
removeFirst(E e):E
removeLast(E e):E
pollFirst():E
pollLast():E
getFirst():E
getLast():E
peekFirst():E
peekLast():E
push(E e): void
-
pop():E
后两个是栈的接口方法。因为在双端队列中，可以在同一端进行出队和入队，所有可以使用双端队列实现栈这样的数据结构。(基于双端队列实现栈)// Stack<Integer> stack = new Stack<>(); Deque<Integer> stack = new ArrayDeque<>(); // 推荐使用这种
两种实现：实现Deque的接口方法
基于队列的 java.util.ArrayDeque<E>
基于链表的 java.util.LinkedList<E>
五、练习
剑指offer9:
https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
class CQueue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public CQueue() {
//创造一个队列
this.stack1 = new Stack<>();
this.stack2 = new Stack<>();
}
public void appendTail(int value) {
// 入队 O(n)
while (!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
stack1.push(value);
}
public int deleteHead() {
// 出队 O(n)
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
if (stack2.isEmpty()) {
return -1;
}
return stack2.pop();
}
}
还有其他方案吗？如何改进？
class CQueue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public CQueue() {
//创造一个队列
this.stack1 = new Stack<>();
this.stack2 = new Stack<>();
}
public void appendTail(int value) {
// 入队 O(1) 降低了时间复杂度
stack1.push(value);
}
public int deleteHead() {
// 出队 O(n)
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
if(stack2.isEmpty()) {
return -1;
} else {
return stack2.pop();
}
}
}
