设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:
MyCircularQueue(k): 构造器,设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空,返回 -1 。
Rear: 获取队尾元素。如果队列为空,返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
https://leetcode.cn/problems/design-circular-queue/description/
数组法 / 单链表法
数组法
第一步,初始化存储数组和头尾指针head和rear,尾指针作为标志位始终在数组中占用一个空位置。
第二步,构建判断队列为空和队列已满的判断函数,使用rear指针和head指针的值进行比较进行判断。
第三步,构建入队函数,首先判断队列是否已满,如果已满,直接返回False;如果未满,在rear指针处添加值,并将rear指针加1并取数组长度数值的模,返回True。
第四步,构建出队函数,首先判断队列是否为空,为空则直接返回False,如果不为空,则初始化head处数组的值,并将head指针加1并取数组长度数值的模,返回True。
第五步,根据head和rear指针很容易构建获取队首和队尾的值,但注意先判断队列是否已满或者已空。
注意:这里的rear指向空节点方便进行是否已满或者已空的判断。
单链表法
第一步,初始化头结点指针head和尾节点指针tail为None,同时初始化循环队列的容量capacity和当前的大小size。
第二步,构建isEmpty和isFull函数,根据size和capacity判断当前队列是否已满或为空。
第三步,构建入队函数,如果队列已满,直接返回False;如果未满但是队列为空,设置head和tail指针指向新建的节点;如果未满但队列不为空,则设置将新节点添加到tail尾部,同时tail指向新的尾节点(即新构建的节点),同时将size加1。
第四步,构建出队函数,如果队列为空,直接返回False;如果队列不为空,则head指针指向head的下一个节点,并将size减1。
第五步,根据head和tail指针很容易构建Front和Rear获取头结点和尾节点的值。
注意:这里的尾节点必须指向有值节点,否则tail指针想要获取尾节点的值必须遍历整个链表。
Python代码 – 数组法
Python代码 – 数组法
C++代码 – 单链表法