队列(Queue),循环队列,双端队列(Deque)and LeetCode刷题
1. 队列的概念
什么是队列?打个比方,就是一群人在排队买东西,先排队的人先拿到东西先离开,后排队的人后拿到东西后离开。
因此,队列是一种 只允许在一端进行插入数据操作,在另一端进行删除数据操作 的特殊线性表,即 “先进先出” ,而栈是“先进后出”。其中,进行插入操作的一端称为队尾(Tail/Rear),该操作叫做入队; 进行删除操作的一端称为队头(Head/Front),该操作叫做出队。在使用队列时,可以画出这样的图形
2.队列的使用
Queue是一个 接口 ,底层是 由LinkedList实现 的!
Queue里的方法是比较少的,如图:
其中,红色框框里的是一组,橙色框框里的是一组;两组的方法都差不多,一般情况下用的是红色框框里的方法
- offer(E):boolean 入列
- poll():E 出列
- peek():E获取队头元素
另外,Queue继承于Collection接口里的两个方法也比较常用:
- size():int 获取队列元素个数
- isEmpty():boolean 判断队列是否为空
public class Test {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
queue.offer(5);
System.out.println(queue.poll());//1
System.out.println(queue.size());//4
System.out.println(queue.peek());//2
System.out.println(queue.isEmpty());//false
}
}
注意: Queue是接口,不能进行实例化接口,而是实例化LinkedList对象,因为LinkedList实现了Queue接口!
3. 队列的模拟实现
常见的结构有顺序结构和链式结构,那么我们模拟实现队列时,选用什么结构来实现呢?答案是都是可以的!
3.1 用链式结构实现队列
链式结构包括单链表和双链表,两种都是可以用来实现的
- 假如用单链表来实现,为了使时间复杂度更小,必须要采用头删和尾插,并且需要一个tail引用来标记尾节点,当然也需要head来标记头节点
- 假如用双链表来实现的话,那就灵活多了,既可以用头删和尾插来模拟实现出队和入队,也可以使用尾删和头插!
下面仅用双链表来模拟实现
public class MyQueue {
static class ListNode {
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode first = null;
public ListNode last = null;
public int usedSize = 0;
public void offer(int val) {
ListNode node = new ListNode(val);
if(first == null) {
first = last = node;
}else {
node.prev = last;
last.next = node;
last = node;
}
usedSize++;
}
public int poll() {
if(first == null) {
return -1;
} else {
int ret = first.val;
first = first.next;
if(first != null){
first.prev = null;
}
usedSize--;
return ret;
}
}
public int peek() {
if(first == null) {
return -1;
} else {
return first.val;
}
}
public boolean isEmpty() {
return usedSize == 0;
}
}
3.2 用顺序结构实现队列
如果使用数组去实现队列,当出队列后,要么把所有的元素都往前挪一位,然而这很浪费时间;要么就要浪费空间,当有大量的出队操作时,就会浪费大量的空间,简直是得不偿失!
那有什么办法可以解决这些问题呢?我们假如可以把数组的首尾连起来,构成循环,出队操作可以直接将队头往后挪一个位置,而原来的位置又能被后面的入队元素占据,这样既能节省时间,又不会浪费空间,接下来就来学习一下循环队列
4. 循环队列
环形队列通常使用数组实现
如图,在一个长度为8的循环队列中,存放12、23、34、45、56元素,用front标记队头,用rear标记队尾,注意rear是数组中最后一个有效元素的下一个
内圈表示数组的下标,外圈表示数组存放的元素。构建好基本的框架后,问题来了
问题1: 如何判空和判满
判空:只要front和rear相遇,就是空
判满:
- 方式1:定义一个变量usedSize,表示当前数组中存放有效数据的个数
- 方式2:添加标记,定义一个boolean类型的标记
- 方式3:浪费一个空间,每次添加元素时判断rear的下一个是不是front,若是则已满
如图,利用方式3,则该循环队列已满,因为rear的下一位是front。该方式浪费了一个空间
问题2: rear或front下标如何由7位置到0位置?可以利用如下公式:(rear + 1) % arr.length
废话不多说,直接上链接来用顺序结构来实现队列,题目链接:622. 设计循环队列
采用方式1的代码如下:
class MyCircularQueue {
public int[] elem;
public int front;
public int rear;
public int usedSize;
public MyCircularQueue(int k) {
elem = new int[k];
}
public boolean enQueue(int value) {
if(isFull()) {
return false;
}
elem[rear] = value;
rear = (rear+1) % elem.length;
usedSize++;
return true;
}
public boolean deQueue() {
if(isEmpty()) {
return false;
}
front = (front+1) % elem.length;
usedSize--;
return true;
}
public int Front() {
if(isEmpty()) {
return -1;
}
return elem[front];
}
public int Rear() {
if(isEmpty()) {
return -1;
}
int index = rear == 0? elem.length-1 : rear-1;
return elem[index];
}
public boolean isEmpty() {
if(usedSize == 0) {
return true;
}
return false;
}
public boolean isFull() {
if(usedSize == elem.length) {
return true;
}
return false;
}
}
5. 双端队列(Deque)
双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。这也就说明,无论是栈,还是队列,都可以使用该接口
同样地,Deque是一个接口,使用时必须创建LinkedList的对象。
在实际工程中,使用Deque接口是比较多的,栈和队列均可以使用该接口
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线型实现 Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现
6. LeetCode刷题
6.1 用队列实现栈
题目链接:225. 用队列实现栈
6.2 用栈实现队列
题目链接:232. 用栈实现队列