思维导图：
1. 队列（双向链表实现）
接口设计
int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void clear(); // 清空
void enQueue(E element); // 入队
E deQueue(); // 出队
E front(); // 获取队列的头元素
优先使用双向链表实现，因为队列主要是往头尾操作元素
public class Queue<E> {
private final List<E> list=new LinkList<>();
/**
* 元素的数量
*/
public int size(){
return list.size();
}
/**
* 判断队列是否空
*/
public boolean isEmpty(){
return list.isEmpty();
}
/**
* 入队
*/
public void enQueue(E element){
list.add(element);
}
/**
* 出队
*/
public E deQueue(){
return list.remove(0);
}
/**
* 获取队列的头元素
*/
public E front(){
return list.get(0);
}
/**
* 清空队列
*/
public void clear(){
list.clear();
}
}
2. 队列（栈实现）
思路：
实现：
public class _232_用栈实现队列 {
private final Stack<Integer> inStack = new Stack<>();
private final Stack<Integer> outStack = new Stack<>();
public void push(int x) {
inStack.push(x);
}
public int pop() {
checkOutStack();
return outStack.pop();
}
//获取队头元素
public int peek() {
checkOutStack();
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}
private void checkOutStack() {
if (outStack.isEmpty()) {
//将inStack所有元素逐一弹出，push到outStack
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
}
}
3. 双端队列（双向链表实现）
双端队列是能在头尾两端添加、删除的队列。英文
deque是double ended queue的简称
接口设计：
int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void clear(); // 清空
void enQueueRear(E element); // 从队尾入队
E deQueueFront(); // 从队头出队
void enQueueFront(E element); // 从队头入队
E deQueueRear(); // 从队尾出队
E front(); // 获取队列的头元素
E rear(); // 获取队列的尾元素
实现：
public class DeQue<E> {;
private final List<E> list = new LinkedList<>();
/**
* 元素的数量
*/
public int size(){
return list.size();
}
public boolean isEmpty(){
return list.isEmpty();
}
/**
* 队头入队
*/
public void enQueueFront(E element){
list.add(0,element);
}
/**
* 队尾入队
*/
public void enQueueRear(E element){
list.add(element);
}
/**
* 出队
*/
public E deQueue(){
return list.remove(0);
}
/**
* 获取队列的头元素
*/
public E front(){
return list.get(0);
}
/**
* 获取队列的尾元素
*/
public E rear(){
return list.get(list.size() - 1);
}
/**
* 清空队列
*/
public void clear(){
list.clear();
}
}
4. 循环队列
循环队列，没有固定的头
public class CircleQueue<E> {
private int size;
private E[] elements;
private int front;//记录队列首元素的位置
private static final int DEFAULT_CAPACITY = 10;//默认队列大小
public CircleQueue() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
/**
* 元素的数量
*/
public int size() {
return size;
}
/**
* 判断队列是否空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 入队，循环队列需要取模
*/
public void enQueue(E element) {
ensureCapacity(size + 1);
elements[(front + size) % elements.length] = element;
size++;
}
/**
* 确保容量充足，不足扩容1.5倍
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (capacity < oldCapacity) return;
//扩容1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[(i + front) % elements.length];
}
elements = newElements;
//重置front的位置
front = 0;
}
/**
* 出队
*/
public E deQueue() {
E element = elements[front];
elements[front] = null;
front = (front + 1) % elements.length;
size--;
return element;
}
/**
* 获取队列的头元素
*/
public E front() {
return elements[front];
}
/**
* 清空队列
*/
public void clear() {
for (int i = 0; i < size; i++) {
elements[index(i)] = null;
}
front = 0;
size = 0;
}
/**
* 返回循环队列中的真实索引
*/
private int index(int index) {
index += front;
return index - (index >= elements.length ? elements.length : 0);
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("capacity=").append(elements.length)
.append(" size=").append(size)
.append(" front=").append(front)
.append(", [");
for (int i = 0; i < elements.length; i++) {
if (i != 0) {
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
}
5. 循环双端队列
实现：
public class CircleDeQueue<E> {
private int size;
private E[] elements;
private int front;//记录队列首元素的位置
private static final int DEFAULT_CAPACITY = 10;//默认队列大小
public CircleDeQueue() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
/**
* 从尾部出队
*/
public E deQueueRear() {
int rearIndex = index(size - 1);
E element = elements[rearIndex];
elements[rearIndex] = null;
size--;
return element;
}
/**
* 从尾部入队
*/
public void enQueueRear(E element) {
ensureCapacity(size + 1);
elements[index(size)] = element;
size++;
}
/**
* 从头部出队
*/
public E deQueueFront() {
E element = elements[front];
elements[front] = null;
front = index(1);
size--;
return element;
}
/**
* 从头部入队
*/
public void enQueueFront(E element) {
ensureCapacity(size + 1);
front = index(-1);
elements[front] = element;
size++;
}
/**
* 获得头部的元素
*/
public E front() {
return elements[front];
}
/**
* 获取尾部的元素
*/
public E rear() {
return elements[index(size - 1)];
}
/**
* 元素的数量
*/
public int size() {
return size;
}
/**
* 判断队列是否空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 返回循环队列中的真实索引
*/
private int index(int index) {
index += front;
if (index < 0) {
index += elements.length;
}
return index - (index >= elements.length ? elements.length : 0);
}
/**
* 确保容量充足，不足扩容1.5倍
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (capacity < oldCapacity) return;
//扩容1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[index(i)];
}
elements = newElements;
//重置front的位置
front = 0;
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("capacity=").append(elements.length)
.append(" size=").append(size)
.append(" front=").append(front)
.append(", [");
for (int i = 0; i < elements.length; i++) {
if (i != 0) {
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
}