1.题目基本信息
1.1.题目描述
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:
- MyCircularQueue(k): 构造器,设置队列长度为 k 。
- Front: 从队首获取元素。如果队列为空,返回 -1 。
- Rear: 获取队尾元素。如果队列为空,返回 -1 。
- enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
- deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
- isEmpty(): 检查循环队列是否为空。
- isFull(): 检查循环队列是否已满。
1.2.题目地址
https://leetcode.cn/problems/design-circular-queue/description/
2.解题方法
2.1.解题思路
数组法 / 单链表法
2.2.解题步骤
数组法
- 第一步,初始化存储数组和头尾指针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指针想要获取尾节点的值必须遍历整个链表。
3.解题代码
Python代码 – 数组法
# 数组法
# 第一步,初始化存储数组和头尾指针head和rear,尾指针作为标志位始终在数组中占用一个空位置。第二步,构建判断队列为空和队列已满的判断函数,使用rear指针和head指针的值进行比较进行判断。第三步,构建入队函数,首先判断队列是否已满,如果已满,直接返回False;如果未满,在rear指针处添加值,并将rear指针加1并取数组长度数值的模,返回True。第四步,构建出队函数,首先判断队列是否为空,为空则直接返回False,如果不为空,则初始化head处数组的值,并将head指针加1并取数组长度数值的模,返回True。第五步,根据head和rear指针很容易构建获取队首和队尾的值,但注意先判断队列是否已满或者已空。
# 注意:这里的rear指向空节点方便进行是否已满或者已空的判断。
class MyCircularQueue:
def __init__(self, k: int):
self.data=[-1]*(k+1) # k+1是为了让rear节点始终维持为空的状态
self.head=self.rear=0
def enQueue(self, value: int) -> bool:
if self.isFull():
return False
self.data[self.rear]=value
self.rear=(self.rear+1)%len(self.data)
return True
def deQueue(self) -> bool:
if self.isEmpty():
return False
self.data[self.head]=-1
self.head=(self.head+1)%len(self.data)
return True
def Front(self) -> int:
return -1 if self.isEmpty() else self.data[self.head]
def Rear(self) -> int:
return -1 if self.isEmpty() else self.data[self.rear-1]
def isEmpty(self) -> bool:
return True if self.head==self.rear else False
def isFull(self) -> bool:
return True if (self.rear+1)%len(self.data)==self.head else False
Python代码 – 单链表法
class LinkedNode():
def __init__(self,val,next=None):
self.val=val
self.next=next
# 单链表法
# 第一步,初始化头结点指针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指针想要获取尾节点的值必须遍历整个链表。
class MyCircularQueue:
def __init__(self, k: int):
self.head=self.tail=None
self.capacity=k
self.size=0
def enQueue(self, value: int) -> bool:
if self.isFull():
return False
newNode=LinkedNode(value)
if self.isEmpty():
self.head=self.tail=newNode
else:
self.tail.next=newNode
self.tail=newNode
self.size+=1
return True
def deQueue(self) -> bool:
if self.isEmpty():
return False
self.head=self.head.next
self.size-=1
return True
def Front(self) -> int:
return self.head.val if not self.isEmpty() else -1
def Rear(self) -> int:
return self.tail.val if not self.isEmpty() else -1
def isEmpty(self) -> bool:
return self.size==0
def isFull(self) -> bool:
return self.size==self.capacity
C++代码 – 单链表法
struct LinkedNode{
int val;
struct LinkedNode *next;
LinkedNode(int x): val(x), next(NULL){}; // 初始化
};
class MyCircularQueue {
LinkedNode *head;
LinkedNode *tail;
int capacity;
int size;
public:
MyCircularQueue(int k) {
this->capacity=k;
this->size=0;
this->head = this->tail = nullptr;
}
bool enQueue(int value) {
if(isFull()){
return false;
}
LinkedNode* newNode=new LinkedNode(value);
if(isEmpty()){
head=newNode;
tail=newNode;
}else{
tail->next = newNode;
tail=newNode;
}
size++;
return true;
}
bool deQueue() {
if(isEmpty()){
return false;
}
LinkedNode *node=head;
head=head->next;
size--;
node->next = NULL;
delete node;
return true;
}
int Front() {
return isEmpty() ? -1 : head->val;
}
int Rear() {
return isEmpty() ? -1 : tail->val;
}
bool isEmpty() {
return size==0;
}
bool isFull() {
return size==capacity;
}
};