Design Circular Queue — LeetCode 622 Python Solution
MediumDesignQueueArrayLinked List
- Problem
- #622
- Pattern
- Linked List
- Reading time
- 8 min
- Source
- leetcode.com
The problem
Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle, and the last position is connected back to the first position to make a circle.
Example
- Input
- ["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
- Output
- [null, true, true, true, false, 3, true, true, true, 4]
- Explanation
- MyCircularQueue myCircularQueue = new MyCircularQueue(3);
Python solution
Python
class MyCircularQueue:
def __init__(self, k: int):
self.q = [0] * k
self.size = 0
self.capacity = k
self.front = 0
def enQueue(self, value: int) -> bool:
if self.isFull():
return False
self.q[(self.front + self.size) % self.capacity] = value
self.size += 1
return True
def deQueue(self) -> bool:
if self.isEmpty():
return False
self.front = (self.front + 1) % self.capacity
self.size -= 1
return True
def Front(self) -> int:
return -1 if self.isEmpty() else self.q[self.front]
def Rear(self) -> int:
if self.isEmpty():
return -1
return self.q[(self.front + self.size - 1) % self.capacity]
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == self.capacity
# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()Complexity
| Measure | Complexity |
|---|---|
| Time | O(V+E) |
| Space | O(k) auxiliary |
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 622. Design Circular Queue is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 622. Design Circular Queue?
- LeetCode 622. Design Circular Queue is rated Medium on LeetCode.
- What is the time complexity of LeetCode 622. Design Circular Queue?
- The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 622. Design Circular Queue?
- The Python solution on this page uses O(k) auxiliary space.
- What topics does LeetCode 622. Design Circular Queue cover?
- LeetCode 622. Design Circular Queue is tagged Design, Queue, Array and Linked List on LeetCode.