队列
- 队列是一种特殊的线性表，只能在头尾两端进行操作
- 队尾（rear）：只能从队尾添加元素，一般叫做enQueue，入队
- 队头（front）：只能从队头移除元素，一般叫做deQueue，出队
- 先进先出的原则，First In First Out,FIFO
队列的接口设计
- int size(); //元素的数量
- boolean isEmpty(); //是否为空
- void enQueue(E element); //入队
- E deQueue(); //出队
- E front(); //获取队列的头元素
- void clear(); //清空
public class Queue<E> {
private List<E> list = new LinkedList<>();
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);
}
}
双端队列（Deque）
- 双端队列是能在头尾两端添加、删除的队列
- int size(); //元素的数量
- boolean isEmpty(); //是否为空
- void enQueueRear(E element); //从队尾入队
- E deQueueFront(); //从队头出队
- void enQueueFront(E element); //从队头入队
- E deQueueRear(); //从队尾从队
- E front(); //获取队列的头元素
- E rear(); //获取队列的尾元素
public class Deque<E> {
private List<E> list = new LinkedList<>();
public int size(){
return list.size();
}
public boolean isEmpty(){
return list.isEmpty();
}
public void enQueueRear(E element){
list.add(element);
}
public E deQueueFront(){
return list.remove(0);
}
public void enQueueFront(E element){
list.add(0,element);
}
public E deQueueRear(){
return list.remove(list.size()-1);
}
public E front(){
return list.get(0);
}
public E rear(){
return list.get(list.size()-1);
}
}
循环队列
- 循环队列底层用数组实现
public class CircleDeque<E> {
private int front;
private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
public CircleDeque() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
for (int i = 0; i < size; i++) {
elements[index(i)] = null;
}
front = 0;
size = 0;
}
/**
* 从尾部入队
* @param element
*/
public void enQueueRear(E element) {
ensureCapacity(size + 1);
elements[index(size)] = element;
size++;
}
/**
* 从头部出队
* @param element
*/
public E deQueueFront() {
E frontElement = elements[front];
elements[front] = null;
front = index(1);
size--;
return frontElement;
}
/**
* 从头部入队
* @param element
*/
public void enQueueFront(E element) {
ensureCapacity(size + 1);
front = index(-1);
elements[front] = element;
size++;
}
/**
* 从尾部出队
* @param element
*/
public E deQueueRear() {
int rearIndex = index(size - 1);
E rear = elements[rearIndex];
elements[rearIndex] = null;
size--;
return rear;
}
public E front() {
return elements[front];
}
public E rear() {
return elements[index(size - 1)];
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("capcacity=").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();
}
private int index(int index) {
index += front;
if (index < 0) {
return index + elements.length;
}
return index - (index >= elements.length ? elements.length : 0);
}
/**
* 保证要有capacity的容量
* @param capacity
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) 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;
}
}
