小码哥数据结构与算法(六): 队列

一、队列

• 队列是一种特殊的线性表, 只能在头尾两端操作
• 队尾(rear): 只能从队尾添加元素, 一般叫做enQueue, 入队
• 对头(front): 只能从对头移除元素, 一般叫做deQueue, 出队

二、接口设计

int size();
boolean isEmpty();
void clear();
void enQueue(E element);
E deQueue();
E fornt();

• 队列的内部实现可以用动态数组或链表实现, 链表优先使用双向链表

三、队列实现

public class Queue<E> {
    private LinkedList<E> list;
 	
    public Queue() {
    	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 fornt() {
    	return list.get(0);
    }
}

四、双端队列

• 双端队列是能在头尾两端添加、删除的队列

1、接口设计

// 元素的数量
int size();
// 是否为空
boolean isEmpty();
// 清空
void clear();
// 从队尾入队
void enQueueRear(E element);
// 从对头出队
E deQueueFront();
// 从对头入队
void enQueueFront(E element);
// 从队尾出队
E deQueueRear();
// 获取队列的头元素
E fornt();
// 获取队列的尾元素
E rear();

2、双端队列实现

public class Deque<E> {
    private LinkedList<E> list;
 	
    public Deque() {
    	list = new LinkedList<>();
    }
	
    // 元素的数量
    int size() {
    	return list.size();
    }
    // 是否为空
    boolean isEmpty() {
    	return list.isEmpty();
    }
    // 清空
    void clear() {
    	list.clear();
    }
    // 从队尾入队
    void enQueueRear(E element) {
    	list.add(element);
    }
    // 从对头出队
    E deQueueFront() {
    	return list.remove(0);
    }
    // 从对头入队
    void enQueueFront(E element) {
    	list.add(0, element);
    }
    // 从队尾出队
    E deQueueRear() {
    	return list.remove(list.size() - 1);
    }
    // 获取队列的头元素
    E fornt() {
    	return list.get(0);
    }
    // 获取队列的尾元素
    E rear() {
    	return list.get(list.size() - 1);
    }
}

五、循环队列

• 队列内部实现也可以用动态数组实现, 并且将各项接口优化到O(1)的时间复杂度, 这个用数组实现并优化之后的队列就叫做: 循环队列
• 使用一个索引变量front控制第0个元素所在位置, 每一次出栈, 就将front位置的元素取出并删除, 然后front向后+1
• 每一次入栈, 都根据front和当前元素数量计算出入栈元素应该存入的索引, 然后将元素存入到数组对应索引的位置上

1、接口设计

int size();
boolean isEmpty();
void clear();
void enQueue(E element);
E deQueue();
E fornt();

2、代码实现

public class CircleQueue<E> {
    // 记录第0个元素的索引
    private int front;
    // 当前队列存储的元素个数
    private int size;
    // 用来存储元素的数组
    private E[] elements;
    // elements默认容量
    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);
    	// 计算新元素应该添加的位置: (front + size) % elements.length
        elements[(front + size) % elements.length] = element;
        // 数量+1
        size++;
    }
    // 扩充容量
    private void ensureCapacity(int capacity) {
    	if (capacity <= elements.length) return;
    	capacity = capacity + (capacity >> 1);
    	E[] newElements = (E[]) new Object[capacity];
 		
    	for (int i = 0; i < size; i++) {
            // 计算元素在旧数组的位置 (i + front) % elements.length
            // 取出元素添加到新数组
            newElements[i] = elements[(i + front) % elements.length];
        }
        elements = newElements;
        front = 0;
    }
    // 出队
    public E deQueue() {
    	// 取出元素
    	E element = elements[front];
    	// 删除元素
    	elements[front] = null;
    	// front向后移动一位
    	front = (front + 1) % elements.length;
    	// 数量-1
    	size--;
    	return element;
    }
    // 查看第0个元素
    public E fornt() {
    	// 取出front位置的元素
    	return elements[front];
    }
    // 清空队列
    public void clear() {
    	for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
        front = 0;
    }
}