一、什么是队列
队列是一种特殊的线性表，只能在头尾两端进行操作，特点是先进先出；就像排队买票一样，先来的先买
二、接口设计
三、代码实现
可以使用动态数组、链表等实现；这里两种实现栈与双向链表
1、栈
public class Queue {
private Stack<Integer> inStack;
private Stack<Integer> outStack;
public Queue() {
inStack = new Stack<>();
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()) {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
}
}
2、双向链表实现
public class Queue<E> {
private List<E> list = new LinkedList<>();//自己实现的类与接口，详细看单链表（一）
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}
public void clear() {
list.clear();
}
public void enQueue(E element) {
list.add(element);
}
public E deQueue() {
return list.remove(0);
}
public E front() {
return list.get(0);
}
}