622. 设计循环队列难度等
题目描述:
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:
MyCircularQueue(k)
: 构造器,设置队列长度为 k 。Front
: 从队首获取元素。如果队列为空,返回 -1 。Rear
: 获取队尾元素。如果队列为空,返回 -1 。enQueue(value)
: 向循环队列插入一个元素。如果成功插入则返回真。deQueue()
: 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty()
: 检查循环队列是否为空。isFull()
: 检查循环队列是否已满。
示例:
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false,队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4
提示:
- 所有的值都在 0 至 1000 的范围内;
- 操作数将在 1 至 1000 的范围内;
- 请不要使用内置的队列库。
解法:(双指针 队列)
采用双指针,front
指向队头,rear
指向队尾(下一个插入位置),capacity
表示队列总体空间。
为了区分队列是空还是满的,我们可以牺牲一个空间不用来存放东西。
几种情况:
(1)判断队列为空,只需要判断 front = rear
,即队头和队尾指向同一个元素。
(2)判断队列是否满,只需要判断 (rear 1) % capacity) == front
,即队尾的下一个元素是不是队首。
(3)获取队首元素,先判断队列不为空,然后返回front
指向的元素
(4)获取队尾元素,由于rear
指向队尾(下一个插入位置),所以真正的队尾是 rear - 1指向的位置,但是下标可能是上一次循环的下标,所以采用取余的方式计算,即(rear - 1 capacity) % capacity
指向的元素。
(5)插入元素,先判断队列是否已满,若未满,将元素插入至rear
位置,再将rear
移动到下一个位置(rear 1) % capacity
。
(6)删除元素,先判断队列是否为空,若不为空,将队首元素向后移动一位即可,即将front移动至(front 1) % capacity
位置。
代码:
class MyCircularQueue {
private int front;
private int rear;
private int capacity;
private int[] elements;
public MyCircularQueue(int k) {
capacity = k 1;
elements = new int[capacity];
rear = front = 0;
}
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
elements[rear] = value;
rear = (rear 1) % capacity;
return true;
}
public boolean deQueue() {
if (isEmpty()) {
return false;
}
front = (front 1) % capacity;
return true;
}
public int Front() {
if (isEmpty()) {
return -1;
}
return elements[front];
}
public int Rear() {
if (isEmpty()) {
return -1;
}
return elements[(rear - 1 capacity) % capacity];
}
public boolean isEmpty() {
return rear == front;
}
public boolean isFull() {
return ((rear 1) % capacity) == front;
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgkckah
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13