队列

简介

队列是一种特殊的线性表，只能在头尾两端进行操作

• 队尾 (rear) : 只能从队尾添加元素，一般叫做 enQueue，入队
• 队头 (front) : 只能从队头移除元素，一般叫做 deQueue，出队
• 先进先出的原则，First In First Out，FIFO

接口设计

优先考虑双向链表

代码实现

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);
	}
}

Queue 源码分析

入队：boolean offer(E, e)

出队：E poll()

获取队头元素：E peek()

对比 LinkedList 和 Queue

	java.util.LinkedList<Interger> linkedList;
	java.util.Queue<Integer> queue;

其实 LinkedList 实现了 Deque 接口，而 Deque 接口又实现了 Queue 接口

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
}

总结：

根据源码，不难发现，队列(Queue) 就是通过 LinkedList 来实现的

双端队列(Deque)

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

deque（double ended queue）

接口设计

代码实现

基于链表实现接口功能

public class Deque<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 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 CircleQueue<E> {
	private int front;
	private int size;
	private E[] 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 clear() {
		for (int i = 0; i < size; i++) {
			elements[index(i)] = null;
		}
		front = 0;
		size = 0;
	}

	public void enQueue(E element) {
		ensureCapacity(size + 1);
		
		elements[index(size)] = element;
		size++;
	}

	public E deQueue() {
		E frontElement = elements[front];
		elements[front] = null;
		front = index(1);
		size--;
		return frontElement;
	}

	public E front() {
		return elements[front];
	}
	
	@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;
		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;
	}
}

循环双端队列

循环双端队列：可以进行两端添加、删除操作的循环队列

代码

主要代码部分：

• 从头部入队
• 从尾部出队

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;
	}
}

模运算优化

尽量避免使用【乘*、除/、模%、浮点数】运算，效率低下

代码修改

	// 循环队列
	private int index(int index) {
		index += front;
		return index - (index >= elements.length ? elements.length : 0);
	}

  // 循环双端队列
	private int index(int index) {
		index += front;
		if (index < 0) {
			return index + elements.length;
		}
		return index - (index >= elements.length ? elements.length : 0);
	}

注意前提条件：

• 已知 n >= 0，m > 0
• n % m 等价于 n - (m > n ? 0 : m) 的前提条件: n < 2m

循环队列 clear 细节

	public void clear() {
		for (int i = 0; i < size; i++) {
       // 获取真实索引元素
			elements[index(i)] = null;
		}
		front = 0;
		size = 0;
	}

练习

232.用栈实现队列

力扣地址：232. 用栈实现队列 - 力扣（LeetCode） (opens new window)

思路：

准备 2 个栈: inStack、outStack

1. 入队时，push 到 inStack 中

2. 出队时

   • 如果 outStack 为空，将 inStack 所有元素逐一弹出，push 到 outStack，outStack 弹出栈顶元素

   • 如果 outStack 不为空，outStack 弹出栈顶元素

代码实现：

class MyQueue {

	private Stack<Integer> inStack;
	private Stack<Integer> outStack;

    public MyQueue() {
    	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());
        	}
        }
    }
}

225.用队列实现栈

力扣地址：225. 用队列实现栈 - 力扣（LeetCode） (opens new window)