0622. 设计循环队列

0622. 设计循环队列 #

  • 标签:队列
  • 难度:中等

题目大意 #

要求:设计实现一个循环队列,支持一下操作:

  • MyCircularQueue(k): 构造器,设置队列长度为 k
  • Front: 从队首获取元素。如果队列为空,返回 -1
  • Rear: 获取队尾元素。如果队列为空,返回 -1
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

解题思路 #

这道题可以使用数组,也可以使用链表来实现循环队列。以数组为例,建立一个容量为 k + 1 的数组 queue。并保存队头指针 front、队尾指针 rear,队列容量 capacityk + 1。这里之所以用了 k + 1 的容量,是为了判断空和满,需要空出一个。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class MyCircularQueue:

    def __init__(self, k: int):
        self.capacity = k + 1
        self.queue = [0 for _ in range(k+1)]
        self.front = 0
        self.rear = 0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = value
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.capacity
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[(self.front + 1)  % self.capacity]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[self.rear]

    def isEmpty(self) -> bool:
        return self.front == self.rear

    def isFull(self) -> bool:
        return (self.rear + 1) % self.capacity == self.front
本站总访问量  次  |  您是本站第  位访问者