和上一篇的栈相反,队列(queue)是一种先进先出(First In First Out, FIFO)的线性表。
它只允许在表的一端进行插入,而在另一端删除元素。这和日常生活中的排队是一致的,最早进入队列的元素最早离开。
在队列中,允许插入的一端称为队尾(rear), 允许 删除的一端则称为队头(front)。出队列和入队列示意图如下:
队列的基本运算和堆栈类似,包含判空、获取长度、入队、出队、出队、取队头(不删除队头)等。
我们这里定义一个队列的接口。
/**
* @Author 三分恶
* @Date 2020/8/27
* @Description 队列
*/
public interface Queue {
public boolean isEmpty(); //判空
public int size(); //获取队列容量
public void enQueue(Object element); //入队
public Object deQueue(); //出队
public Object getHead(); //取队首元素
}
队列是一种受限的线性表,同样有顺序和链式两种实现。
这里顺序队列通过可扩容数组来实现。
在类里标记了队头和对尾的下标。
入队时,队尾往后移动,队头保持不变,出队是队头往后移动,队尾保持不变。
为什么不保持队头指向0?因为如果队首指向0,那么出队的时候需要将数组前移,时间复杂度为O(n)。使用了队头和队尾标记之后,出队时队头往后移动一位,这样避免了元素的移动。
/**
* @Author 三分恶
* @Date 2020/8/27
* @Description 顺序队列
*/
public class ArrayQueue implements Queue{
private static int defaultSize=15; //默认容量
private int size; //实际容量:实际存储元素个数
private Object[] data; //存放元素的数组
private int front=0; //队头(下标)
private int rear=0; //队尾(下标)
/**
* 无参构造方法:按默认容量构造元素数组
*/
public ArrayQueue(){
data=new Object[defaultSize];
}
/**
* 有参构造方法:指定元素数组容量
* @param capacity
*/
public ArrayQueue(int capacity){
data=new Object[capacity];
}
/**
* 判空
* @return
*/
public boolean isEmpty() {
return size==0;
}
/**
* 获取队列元素个数
* @return
*/
public int size() {
return size;
}
/**
* 入队
* @param element
*/
public void enQueue(Object element) {
//如果队满
if (size==data.length&&front==0){
//真队满,扩容
if (front==0){
//扩容两倍的新数组
Object [] newData=new Object[size<<1];
//拷贝数组
System.arraycopy(data,0,newData,0,size);
data=newData;
}else{
//假队满:前移元素
//所有数据前移front位
for (int i=front;i<size;i++){
data[i-front] = data[i];
}
//队尾前移front位
rear-=front;
//队头指向0
front=0;
}
}
//队尾插入元素
data[rear]=element;
rear++;
size++;
}
/**
* 出队
* @return
*/
public Object deQueue() {
if (isEmpty()){
throw new RuntimeException("队空");
}
//取队头元素
Object f=data[front];
//队头数组元素指向null,帮助gc
data[front]=null;
//队首指向下一元素
front++;
//元素个数减1
size--;
//返回队首元素
return f;
}
/**
* 取队首元素(不删除队首元素)
* @return
*/
public Object getHead() {
if (isEmpty()){
throw new RuntimeException("队空");
}
return data[front];
}
}
时间复杂度分析:
这里使用单向链表来实现链式队列。
入队是将队尾指向插入的新元素,出队是将队头指向队头的下一个元素。
/**
* @Author 三分恶
* @Date 2020/8/27
* @Description
*/
public class LinkedQueue implements Queue{
/**
* 节点类
* @param <T>
*/
class Node<T>{
private Object data; //数据
private Node next; //下一节点
Node(Object it, Node nextVal){
this.data=it;
this.next=nextVal;
}
}
private Node front; //队头
private Node rear; //队尾
private int size; //队列元素个数
/**
* 判空
* @return
*/
public boolean isEmpty() {
return size==0;
}
public int size() {
return size;
}
/**
* 入栈
* @param element
*/
public void enQueue(Object element) {
Node node=new Node(element,null);
//如果队列为空
if (rear==null){
rear=node;
front=node;
}else{
rear.next=node;
}
size++;
}
/**
* 出队
* @return
*/
public Object deQueue() {
//队列为空
if (front==null){
throw new RuntimeException("队列为空");
}
//队头
Node node=front;
front=front.next;
size--;
return node.data;
}
/**
* 取队头元素
*/
public Object getHead() {
//队列为空
if (front==null){
throw new RuntimeException("队列为空");
}
return front.data;
}
}
时间复杂度分析:
除此之外,顺序队列有变种循环队列,当rear到达数组的最大下标时,重新指回数组下标为0的位置; 链式队列有双端队列,队头、队尾都可以进行入队、出队操作的队列,可以通过双向链表实现;
java中有一个队列接口java.util.Queue,定义了队列的一些方法。
它有一个子接口,java.util.Deque,定义了双端队列的方法。
LinkedList实现了java.util.Deque接口,所以LinkedList能作为队列也能作为双端队列使用。详见LinkedList源码阅读笔记。
源码地址:https://gitee.com/LaughterYoung/data-structure-learn.git
参考:
【1】:邓俊辉 编著. 《数据结构与算法》 【2】:王世民 等编著 . 《数据结构与算法分析》 【3】: Michael T. Goodrich 等编著.《Data-Structures-and-Algorithms-in-Java-6th-Edition》 【4】:严蔚敏、吴伟民 编著 . 《数据结构》 【5】:程杰 编著 . 《大话数据结构》 【6】:看完这篇你还不知道这些队列,我这些图白作了