🚁分析如何设计循环队列
队列的底层用双向链表实现,因为使用双向链表保证了入队列和出队列的时间复杂度都达到O(1),那能否使用一段连续的空间实现呢?当然可以,先分析用普通的数组对其实现进行分析,看看会出现哪些问题?
用front标记对头元素,进行出队列,用rear标记队尾后的空位置,进行入队列
🚧入队列操作:直接在rear标记的位置进行插入,再进行rear++,时间复杂度为O(1)
🏁出队列操作:有两种实现方式
方式1:将front位置的元素出队列后,front位置不变,将front后面的元素都向前搬移一个长度,时间复杂度O(n)
方式2:将front位置元素出队列后,再进行front++,时间复杂度O(1),但是会有一个问题,造成空间的假溢出
为了解决上述空间的假溢出问题,使用循环数组来实现循环队列,所谓循环数组,就是数组尾部标记往后再走的话就走到数组头部了
为了更好的理解循环队列,我们这样画图表示:
但是这样会出现一个问题:发现当rear与front在同一位置时,有两种状态,队列满,队列空,那么如何判断队列满与队列空❓
🤔思考怎么区分队列满与队列空
🚀如何区分循环队列的满与空?
有三种办法来区分循环队列的满与空
🔥方法一:使用count来标记队列中元素的个数,当count为0说明队列为空,当count等于数组的长度时说明队列已经满了
💧方法二:预留一个空位置,也就是当队列还有一个空位置的时候,认为该循环队列已经满了
⚡方法三:使用一个标记flag,初始时设置为false,每入队一个元素将flag设置为true
对比上述三种实现方式,使用count记录队列元素的个数辨识度更高 ,所以后续在实现的时候就使用count标记来判断队列的空与满
🛸实现循环队列
循环队列的成员变量:
private E[] array; private int front; //标记队列头,进行出队列 private int rear; //标记队列尾,进行入队列 private int count; //队列中元素个数,用来区分队列满与空 private int N; //数组的长度
循环队列的构造方法:
public MyCircularQueue(){ array = (E[])new Object[10]; N = array.length; }
入队列操作:
1. 如果队列已经满了,返回false
2. 否则在队尾位置直接插入元素,count++,队尾标记rear往后走一个
3. 如果rear走到N,则将rear置为0,从头开始继续
public boolean enQueue(E val){ if(isFull()){ return false; } array[rear] = val; rear++; if(rear == N){ rear = 0; } count++; return true; } 出队列操作: 1. 如果队列已经为空,则返回false 2. 否则直接将count--,front++ 3. 如果front走到N的位置,将front置为0,从头开始,与上述类似 public boolean deQueue(){ if(isEmpty()){ return false; } count--; front++; if(front == N){ front = 0; } return true; }
获取队尾元素:
如果队列为空抛出异常,否则直接返回rear前一个位置的元素,因为rear标记的是队尾的空位置,对rear的处理有两种情况,所以要对两种情况统一处理,获取(rear-1+N)%N位置元素
public E rear(){ if(isEmpty()){ throw new RuntimeException("队列为空"); } return array[(rear-1+N)%N]; }
获取对头元素:
如果队列为空,则抛出异常,否则直接返回front位置元素,因为front标记的是队头元素
public E front(){ if(isEmpty()){ throw new RuntimeException("队列为空"); } return array[front]; }
判断队列是否为空:
比较count==0
public boolean isEmpty(){ return count==0; }
判断是否队列已经满了:
比较count==N
public boolean isFull(){ return count==N; }
🪂了解双端队列Deque
Deque是一个接口,底层也是用LinkedList实现的,双端队列指队列的两端都可以进行入队列和出队列操作
🛰️循环双端队列的实现
循环双端队列,与循环队列的实现大同小异,只不过是在队列头多了入队列操作,在队列尾多了出队列操作
🚨注意:
在循环队列中,front标记对头元素,rear标记队尾空位置
在循环双端队列中,front标记队头空位置,rear标记队尾元素
循环双端队列的成员变量:
int[] array; int rear; //队尾 int front; //队头 int count; //队列中元素个数 int N; //数组长度
循环双端队列的构造方法:
public MyCircularDeque() { array = new int[10]; N = array.length; }
队列头部插入:
1. 如果队列已经满了,直接返回false
2. 否则在front位置直接插入元素,然后front--,count++
3. 如果front当前为0,front--直接就为-1,所以要进行(front+N)%N计算更新front
public boolean insertFront(int value) { if(isFull()){ return false; } array[front] = value; count++; front--; front = (front+N)%N; return true; }
队列尾部插入:
1. 如果队列为空,则直接返回false
2. 否则在rear+1位置插入元素,如果rear+1等于数组长度时,需要置0,所以进行rear%N操作
3. 插入后count++
public boolean insertLast(int value) { if(isFull()){ return false; } rear++; rear %= N; array[rear] = value; count++; return true; }
队列头部删除:
1. 如果队列为空,直接返回false
2. 否则将front往后走一个位置,如果走到N的位置,则需要将front重新置0,所以(front+1)%N
3. 删除完,count--
public boolean deleteFront() { if(isEmpty()){ return false; } front = (front+1)%N; count--; return true; }
队列尾部删除:
1. 如果队列为空,则直接返回false
2. 否则rear往前走一个位置,如果走到-1,则要将rear置为末尾,所以(rear-1+N)%N
3. 删除后,count--
public boolean deleteLast() { if(isEmpty()){ return false; } rear = (rear-1+N)%N; count--; return true; }
获取队头元素:
1. 如果队列为空,则返回-1
2. 否则返回front下一个位置的元素,如果front下一个位置为N,则将front置为0,所以(front+1)%N
3. 返回array[(front+1)%N]
public int getFront() { if(isEmpty()){ return -1; } return array[(front+1)%N]; }
获取队尾元素:
1. 如果队列为空,则直接返回-1
2. 直接返回rear位置的元素
public int getRear() { if(isEmpty()){ return -1; } return array[rear]; }
判断队列是否为空:
直接判断count==0
public boolean isEmpty() { return count==0; }
判断队列是否已经满了:
直接判断count==N
public boolean isFull() { return count==N; }