博信信息网第五章 队列（Queue）
队列是一种特殊的线性表，只能在头尾两端进行操作；
队尾（rear）：只能从队尾添加元素，一般叫做enQueue，入队队头（front）：只能从队头移除元素，一般叫做deQueue，出队先进先出的原则，First In First Out，FIFO队列的接口设计
int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void clear(); // 清空
void enQueue(E element); // 入队
E deQueue(); // 出队
E front(); // 获取队列的头元素
队列的内部实现是否可以直接利用以前学过的数据结构？
动态数组、链表优先使用双向链表，因为队列主要是往头尾操作元素队列源码List接口类
package cn.xx.java.list;
/**
* @author xiexu
* @create 2021-07-13 9:59 上午
*/
public interface List<E> {
static final int ELEMENT_NOT_FOUND = -1;
/**
* 清除所有元素
*/
void clear();
/**
* 元素的数量
*
* @return
*/
int size();
/**
* 是否为空
*
* @return
*/
boolean isEmpty();
/**
* 是否包含某个元素
*
* @param element
* @return
*/
boolean contains(E element);
/**
* 添加元素到尾部
*
* @param element
*/
void add(E element);
/**
* 获取index位置的元素
*
* @param index
* @return
*/
E get(int index);
/**
* 设置index位置的元素
*
* @param index
* @param element
* @return 原来的元素ֵ
*/
E set(int index, E element);
/**
* 在index位置插入一个元素
*
* @param index
* @param element
*/
void add(int index, E element);
/**
* 删除index位置的元素
*
* @param index
* @return
*/
E remove(int index);
/**
* 查看元素的索引
*
* @param element
* @return
*/
int indexOf(E element);
}
AbstractList抽象类
package cn.xx.java.list;
/**
* @author xiexu
* @create 2021-07-13 10:08 上午
*/
public abstract class AbstractList<E> implements List<E> {
protected int size; //元素的数量
/**
* 元素的数量
*
* @return
*/
public int size() {
return size;
}
/**
* 是否为空
*
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含某个元素
*
* @return
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 添加元素到尾部
*
* @param element
*/
public void add(E element) {
add(size, element);
}
//抛出异常
protected void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index：" + index + ", Size：" + size);
}
/**
* 检查范围
*
* @param index
*/
protected void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}
/**
* 检查添加到指定位置元素的范围
*
* @param index
*/
protected void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
}
LinkedList类
package cn.xx.java.list;
/**
* @author xiexu
* @create 2021-07-13 9:52 上午
*/
public class LinkedList<E> extends AbstractList<E> {
private Node<E> first;
private Node<E> last;
@Override
public void clear() {
size = 0;
first = null;
last = null;
}
@Override
public E get(int index) {
/**
* 最好：O(1)
* 最坏：O(n)
* 平均：O(n)
*/
return node(index).element;
}
@Override
public E set(int index, E element) {
/**
* 最好：O(1)
* 最坏：O(n)
* 平均：O(n)
*/
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if (index == size) { //往最后面添加元素
Node<E> oldLast = last; //之前的last
last = new Node<>(element, oldLast, null);
if (oldLast == null) { //这是链表添加的第一个元素
first = last;
} else {
oldLast.next = last;
}
} else {
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(element, prev, next);
next.prev = node;
if (prev == null) { //等价于index == 0
first = node;
} else {
prev.next = node;
}
}
size++;
}
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> node = node(index);
Node<E> prev = node.prev;
Node<E> next = node.next;
if (prev == null) { //等价于index == 0
first = next;
} else {
prev.next = next;
}
if (next == null) { //等价于 index == size - 1
last = prev;
} else {
next.prev = prev;
}
size--;
return node.element;
}
/**
* 查看元素的索引
*
* @param element
* @return
*/
@Override
public int indexOf(E element) {
Node<E> node = first;
//null值的判断
if (element == null) {
for (int i = 0; i < size; i++) {
if (node.element == null) {
return i;
}
node = node.next;
}
} else {
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) {
return i;
}
node = node.next;
}
}
return ELEMENT_NOT_FOUND; //找不到就返回-1
}
/**
* 获取index位置对应的结点
*
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheck(index);
if (index < (size >> 1)) { //索引小于一半从前往后找
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else { //索引大于一半从后往前找
Node<E> node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
//Node内部类
private static class Node<E> {
E element;
Node<E> prev;
Node<E> next;
public Node(E element, Node<E> prev, Node<E> next) {
this.element = element;
this.prev = prev;
this.next = next;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
if (prev != null) {
sb.append(prev.element);
} else {
sb.append("null");
}
sb.append("_").append(element).append("_");
if (next != null) {
sb.append(next.element);
} else {
sb.append("null");
}
return sb.toString();
}
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size = ").append(size).append(", [");
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(node);
node = node.next;
}
string.append("]");
return string.toString();
}
}
Queue类
package cn.xx.java;练习用栈实现队列
import cn.xx.java.list.LinkedList;
import cn.xx.java.list.List;
/**
* @author xiexu
* @create 2021-07-24 10:56 上午
*/
public class Queue<E> {
private List<E> list = new LinkedList<>();
/**
* 入队
*
* @param element
*/
public void enQueue(E element) {
list.add(element);
}
/**
* 出队
*
* @return
*/
public E deQueue() {
return list.remove(0);
}
/**
* 清空队列
*/
public void clear() {
list.clear();
}
/**
* 元素的数量
*
* @return
*/
public int size() {
return list.size();
}
/**
* 是否为空
*
* @return
*/
public boolean isEmpty() {
return list.isEmpty();
}
/**
* 队头元素
*
* @return
*/
public E top() {
return list.get(0);
}
}
232_用栈实现队列：https://leetcode-cn.com/problems/implement-queue-using-stacks/
思路分析
package 队列;双端队列 Deque双端队列接口设计
import java.util.Stack;
/**
* @author xiexu
* @create 2021-07-25 9:36 上午
*/
public class _232_用栈实现队列 {
private Stack<Integer> inStack;
private Stack<Integer> outStack;
/**
* Initialize your data structure here.
*/
public _232_用栈实现队列() {
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());
}
}
}
}
int size(); // 元素的数量双端队列源码
boolean isEmpty(); // 是否为空
void clear(); // 清空
void enQueueRear(E element); // 从队尾入队
E deQueueFront(); // 从队头出队
void enQueueFront(E element); // 从队头入队
E deQueueRear(); // 从队尾出队
E front(); // 获取队列的头元素
E rear(); // 获取队列的尾元素
package cn.xx.java;循环队列 Circle Queue
import cn.xx.java.list.LinkedList;
import cn.xx.java.list.List;
/**
* @author xiexu
* @create 2021-07-25 9:57 上午
*/
public class Deque<E> {
private List<E> list = new LinkedList<>();
/**
* 元素的数量
*
* @return
*/
public int size() {
return list.size();
}
/**
* 是否为空
*
* @return
*/
public boolean isEmpty() {
return list.isEmpty();
}
/**
* 清空队列
*/
public void clear() {
list.clear();
}
/**
* 从队尾入队
*
* @param element
*/
public void enQueueRear(E element) {
list.add(element);
}
/**
* 从队头出队
*
* @return
*/
public E deQueueFront() {
return list.remove(0);
}
/**
* 从队头入队
*
* @param element
*/
public void enQueueFront(E element) {
list.add(0, element);
}
/**
* 从队尾出队
*
* @return
*/
public E deQueueRear() {
return list.remove(size() - 1);
}
/**
* 获取队头元素
*
* @return
*/
public E front() {
return list.get(0);
}
/**
* 获取队尾元素
*
* @return
*/
public E rear() {
return list.get(size() - 1);
}
}
其实队列底层也可以使用动态数组实现，并且各项接口也可以优化到 O(1) 的时间复杂度；
这个用数组实现并且优化之后的队列也叫做：循环队列循环队列实现package cn.xx.java.circle;索引映射封装
/**
* @author xiexu
* @create 2021-07-25 10:32 上午
*/
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];
}
/**
* 获取队列元素的数量
*
* @return
*/
public int size() {
return size;
}
/**
* 判断队列是否为空
*
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 清空队列
*/
public void clear() {
for (int i = 0; i < size; i++) {
elements[index(i)] = null;
}
size = 0;
front = 0;
}
/**
* 入队操作
*
* @param element
*/
public void enQueue(E element) {
ensureCapacity(size + 1);
elements[((front + size) % elements.length)] = element;
size++;
}
/**
* 出队操作
*
* @return
*/
public E deQueue() {
E frontElement = elements[front];
elements[front] = null;
front = ((front + 1) % elements.length);
size--;
return frontElement;
}
/**
* 获取队头元素
*
* @return
*/
public E front() {
return elements[front];
}
/**
* 扩容
*/
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[((i + front) % elements.length)];
}
elements = newElements;
//重置front
front = 0;
}
@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();
}
}
可以发现循环队列中经常有 (front + size) % elements.length 的操作，那是因为如果 front 在队尾了，而又要往后移则会回到开头，该代码就是根据 front 的真实索引计算出在循环队列上的索引。
我们可以将这个封装为一个方法，实际上这个写法使用 % 运算符，性能十分低，后面会对此做优化。
// 将front真实索引转换为循环队列上的索引
private int index(int index) {
return (front + index) % elements.length;
}
则循环队列中的其他方法可以修改为如下：
/**
* 扩容
*/
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;
}
/**
* 入队操作
*
* @param element
*/
public void enQueue(E element) {
ensureCapacity(size + 1);
elements[index(size)] = element;
size++;
}
/**%运算符优化
* 出队操作
*
* @return
*/
public E deQueue() {
E frontElement = elements[front];
elements[front] = null;
front = index(1);
size--;
return frontElement;
}
尽量避免使用 乘*、除/、模%、浮点数运算，效率低下；
原理：已知 n >= 0，m > 0：
n % m 等价于n – (m > n ? 0 : m) ；前提条件：n < 2m
由于我们已经封装了索引映射的方法，%运算符优化只需要修改 index 方法即可：
// 将真实索引转换为循环队列上的索引
private int index(int index) {
index += front;
// 10%8 = 2 10-8 = 2
// 11%10 = 1 11-10 = 1
return index - (index >= elements.length ? elements.length : 0);
}
完整代码
package cn.xx.java.circle;循环队列测试
/**
* @author xiexu
* @create 2021-07-25 10:32 上午
*/
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];
}
/**
* 获取队列元素的数量
*
* @return
*/
public int size() {
return size;
}
/**
* 判断队列是否为空
*
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 清空队列
*/
public void clear() {
for (int i = 0; i < size; i++) {
elements[index(i)] = null;
}
size = 0;
front = 0;
}
/**
* 入队操作
*
* @param element
*/
public void enQueue(E element) {
ensureCapacity(size + 1);
elements[index(size)] = element;
size++;
}
/**
* 出队操作
*
* @return
*/
public E deQueue() {
E frontElement = elements[front];
elements[front] = null;
front = index(1);
size--;
return frontElement;
}
/**
* 获取队头元素
*
* @return
*/
public E front() {
return elements[front];
}
/**
* 扩容
*/
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;
}
@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;
// 10%8 = 2 10-8 = 2
// 11%10 = 1 11-10 = 1
return index - (index >= elements.length ? elements.length : 0);
}
}
static void test2() {
CircleQueue<Integer> queue = new CircleQueue<Integer>();
// 0 1 2 3 4 5 6 7 8 9
for (int i = 0; i < 10; i++) {
queue.enQueue(i);
}
// null null null null null 5 6 7 8 9
for (int i = 0; i < 5; i++) {
queue.deQueue();
}
// 15 16 17 18 19 5 6 7 8 9
for (int i = 15; i < 23; i++) {
queue.enQueue(i);
}
System.out.println(queue);
while (!queue.isEmpty()) {
System.out.println(queue.deQueue());
}
}循环双端队列 Circle Dequeue循环双端队列：可以进行两端添加、删除操作的循环队列；
循环队列中用了 front 指针来表示队列的头部，双端循环队列是否需要再使用一个 rear 指针来表示队列的尾部?
不需要，只要有了头指针便可以算出尾部；首先理解一下循环双端队列中索引封装映射：
传入的 index 是相对于 front 的索引，返回的是真实的索引：比如要获得 头部指针 的前一位，则是 index(-1)（用于队头入队）
比如要获得 尾部指针，则是 index(size - 1)
private int index(int index) {
index += front;
if (index < 0) {
return index + elements.length;
} else {
return index % elements.length;
}
}循环双端队列实现package cn.xx.java.circle;%运算符优化
/**
* @author xiexu
* @create 2021-07-25 11:47 上午
*/
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];
}
/**
* 获取队列元素的数量
*
* @return
*/
public int size() {
return size;
}
/**
* 判断队列是否为空
*
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 清空队列
*/
public void clear() {
for (int i = 0; i < elements.length; i++) {
elements[index(i)] = null;
}
size = 0;
front = 0;
}
/**
* 从队尾入队
*
* @param element
*/
public void enQueueRear(E element) {
ensureCapacity(size + 1);
elements[index(size)] = element;
size++;
}
/**
* 从队头出队
*
* @return
*/
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++;
}
/**
* 从队尾出队
*
* @return
*/
public E deQueueRear() {
int rearIndex = index(size - 1); //尾部元素的索引
E rear = elements[rearIndex];
elements[rearIndex] = null;
size--;
return rear;
}
/**
* 获取队头元素
*
* @return
*/
public E front() {
return elements[front];
}
/**
* 获取队尾元素
*
* @return
*/
public E rear() {
return elements[index(size - 1)];
}
private int index(int index) {
index += front;
if (index < 0) {
return index + elements.length;
} else {
return index % elements.length;
}
}
/**
* 扩容
*/
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;
}
@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();
}
}
尽量避免使用 乘*、除/、模%、浮点数运算，效率低下；
原理：已知 n >= 0，m > 0：
n % m 等价于n – (m > n ? 0 : m) ；前提条件：n < 2m
由于我们已经封装了索引映射的方法，%运算符优化只需要修改 index 方法即可：
private int index(int index) {
index += front;
if (index < 0) {
return index + elements.length;
} else {
return index - (index >= elements.length ? elements.length : 0);
}
}完整代码
package cn.xx.java.circle;循环双端队列测试
/**
* @author xiexu
* @create 2021-07-25 11:47 上午
*/
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];
}
/**
* 获取队列元素的数量
*
* @return
*/
public int size() {
return size;
}
/**
* 判断队列是否为空
*
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 清空队列
*/
public void clear() {
for (int i = 0; i < elements.length; i++) {
elements[index(i)] = null;
}
size = 0;
front = 0;
}
/**
* 从队尾入队
*
* @param element
*/
public void enQueueRear(E element) {
ensureCapacity(size + 1);
elements[index(size)] = element;
size++;
}
/**
* 从队头出队
*
* @return
*/
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++;
}
/**
* 从队尾出队
*
* @return
*/
public E deQueueRear() {
int rearIndex = index(size - 1); //尾部元素的索引
E rear = elements[rearIndex];
elements[rearIndex] = null;
size--;
return rear;
}
/**
* 获取队头元素
*
* @return
*/
public E front() {
return elements[front];
}
/**
* 获取队尾元素
*
* @return
*/
public E rear() {
return elements[index(size - 1)];
}
private int index(int index) {
index += front;
if (index < 0) {
return index + elements.length;
} else {
return index - (index >= elements.length ? elements.length : 0);
}
}
/**
* 扩容
*/
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;
}
@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();
}
}
static void test3() {
CircleDeque<Integer> queue = new CircleDeque<>();
// 头5 4 3 2 1 100 101 102 103 104 105 106 8 7 6 尾
// 头 8 7 6 5 4 3 2 1 100 101 102 103 104 105 106 107 108 109 null null 10 9 尾
for (int i = 0; i < 10; i++) {
queue.enQueueFront(i + 1);
queue.enQueueRear(i + 100);
}
// 头 null 7 6 5 4 3 2 1 100 101 102 103 104 105 106 null null null null null null null 尾
for (int i = 0; i < 3; i++) {
queue.deQueueFront();
queue.deQueueRear();
}
// 头 11 7 6 5 4 3 2 1 100 101 102 103 104 105 106 null null null null null null 12 尾
queue.enQueueFront(11);
queue.enQueueFront(12);
System.out.println(queue);
while (!queue.isEmpty()) {
System.out.print(queue.deQueueFront() + "\t");
}
}
版权声明
本文仅代表作者观点，不代表博信信息网立场。
相关文章
作者文章
- 拨号VPS需要手动换IP吗？ 11个月前 (06-25)
- 如何搭建VPS远程拨号服务器？ 11个月前 (06-25)
- 如何为拨号VPS搭建最佳代理？ 11个月前 (06-25)
- 如何利用VPS进行拨号连接？ 11个月前 (06-25)
- 日本VPS拨号动态IP：解锁网络新境界 11个月前 (06-25)