首先来看看队列这种数据结构:
在 FIFO 数据结构中,将首先处理添加到队列中的第一个元素
。
如上图所示,队列是典型的 FIFO 数据结构。插入(insert)操作也称作入队(enqueue),新元素始终被添加在队列的末尾
。 删除(delete)操作也被称为出队(dequeue)。 你只能移除第一个元素
。
队列 - 实现
为了实现队列,我们可以使用动态数组和指向队列头部的索引。
如上所述,队列应支持两种操作:入队和出队。入队会向队列追加一个新元素,而出队会删除第一个元素。 所以我们需要一个索引来指出起点。
循环队列
此前,我们提供了一种简单但低效的队列实现。
更有效的方法是使用循环队列。 具体来说,我们可以使用固定大小的数组
和两个指针
来指示起始位置和结束位置。 目的是重用
我们之前提到的被浪费的存储
。
让我们通过一个示例来查看循环队列的工作原理。 你应该注意我们入队
或出队
元素时使用的策略。
[外链图片转存失败(img-ScULOtla-1564547660610)(queue.gif)]
仔细检查动画,找出我们用来检查队列是空
还是满
的策略。
以上内容来自力扣中国,内容有改变
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 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
提示:
一般高级程序设计语言都会内置队列库,稍微参考一下即可。在循环队列中,我们使用一个数组
和两个指针(head
和 tail
)。 head
表示队列的起始位置,tail
表示队列的结束位置。
class MyCircularQueue {private int[] data;private int head;private int tail;private int size;/** 初始化数据结构,并规定队列大小k */public MyCircularQueue(int k) {data = new int[k];head = -1;tail = -1;size = k;}/** 在队列插入一项,并返回插入是否成功 */public boolean enQueue(int value) {if (isFull() == true) {return false;}if (isEmpty() == true) {head = 0;}tail = (tail + 1) % size;data[tail] = value;return true;}/** 从队列删除一项,并返回删除是否成功 */public boolean deQueue() {if (isEmpty() == true) {return false;}if (head == tail) {head = -1;tail = -1;return true;}head = (head + 1) % size;return true;}/** 获取队列第一项 */public int Front() {if (isEmpty() == true) {return -1;}return data[head];}/** 获取队列最后一项 */public int Rear() {if (isEmpty() == true) {return -1;}return data[tail];}/** 检查队列是否为空 */public boolean isEmpty() {return head == -1;}/** 检查队列是否已满 */public boolean isFull() {return ((tail + 1) % size) == head;}
}
class MyCircularQueue():def __init__(self, k: int):"""初始化数据结构,并规定队列大小k"""self.size = kself.queue = ['']*kself.head = -1self.tail = -1def enQueue(self, value: int) -> bool:"""在队列插入一项,并返回插入是否成功"""if not self.isFull():if self.head == -1:self.head = 0self.tail = (self.tail+1)%self.sizeself.queue[self.tail] = valuereturn Trueelse:return Falsedef deQueue(self) -> bool:"""从队列删除一项,并返回删除是否成功"""if not self.isEmpty():if self.head ==self.tail:self.head,self.tail = -1,-1else:self.head = (self.head+1)%self.sizereturn Trueelse:return Falsedef Front(self) -> int:"""获取队列第一项"""if self.isEmpty():return -1else:return self.queue[self.head]def Rear(self) -> int:"""获取队列最后一项"""if self.isEmpty():return -1else:return self.queue[self.tail]def isEmpty(self) -> bool:"""检查队列是否为空"""return self.head == -1 and self.tail == -1def isFull(self) -> bool:"""检查队列是否已满"""return (self.tail+1)%self.size ==self.head
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态