資料結構實作題 環狀佇列 Design Circular Queue Leetcode #622

這題的題目在這裡

題目敘述

這題是一個經典的資料結構實作題，要求我們實作指定長度為k的環狀佇列。

請記得，佇列最重要的特質就是先進先出 First In First Out 又簡稱為 FIFO

測試範例

Example 1:

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

Explanation
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(1); // return True
myCircularQueue.enQueue(2); // return True
myCircularQueue.enQueue(3); // return True
myCircularQueue.enQueue(4); // return False
myCircularQueue.Rear();     // return 3
myCircularQueue.isFull();   // return True
myCircularQueue.deQueue();  // return True
myCircularQueue.enQueue(4); // return True
myCircularQueue.Rear();     // return 4

約束條件

• 1 <= k <= 1000
• 0 <= value <= 1000
• At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

演算法

核心思想和傳統的線性陣列的Queue類似，都是Front取出元素，Rear推入新元素。

唯一的差別在於，環狀佇列，在全部放滿的情況下，頭尾有可能相鄰。
因此每次在Rear推入新元素時，要特別留意，環狀佇列是否還有剩餘的空間可以使用，如果沒有，應該直接返回False。

程式碼

class MyCircularQueue:

　def __init__(self, k: int):
　　"""
　　Initialize your data structure here. Set the size of the queue to be k.
　　"""

　　self.circular_q = [ 0 ] * k 
　　self.front = 0
　　self.rear = 0
　　self.size = 0
　　self.capacity = k

　def enQueue(self, value: int) -> bool:
　　"""
　　Insert an element into the circular queue. Return true if the operation is successful.
　　"""
　　if (self.size+1) <= self.capacity:
　　　
　　　self.circular_q[self.rear] = value
　　　self.rear = ( self.rear +  1 ) % self.capacity
　　　self.size += 1 
　　　
　　　return True
　　else:
　　　return False
　　

　def deQueue(self) -> bool:
　　"""
　　Delete an element from the circular queue. Return true if the operation is successful.
　　"""
　　if self.size != 0:
　　
　　　self.front = ( self.front + 1) % self.capacity
　　　self.size -= 1
　　　
　　　return True
　　else:
　　　return False
　　

　def Front(self) -> int:
　　"""
　　Get the front item from the queue.
　　"""
　　if self.size != 0:
　　　return self.circular_q[ self.front ]
　　else:
　　　return -1
　　

　def Rear(self) -> int:
　　"""
　　Get the last item from the queue.
　　"""
　　if self.size != 0:
　　　return self.circular_q[ (self.rear-1) % self.capacity ]
　　else:
　　　return -1
　　

　def isEmpty(self) -> bool:
　　"""
　　Checks whether the circular queue is empty or not.
　　"""
　　return self.size == 0

　def isFull(self) -> bool:
　　"""
　　Checks whether the circular queue is full or not.
　　"""
　　return self.size == self.capacity　　

複雜度分析

時間複雜度: 初始化O( k )，其餘操作皆為O(1)
只有初始化的時候需要先建立一個長度為k的空陣列。

其餘的推入元素，取出元素，檢查是否為空，檢查是否全滿，皆為常數時間O(1)

空間複雜度: 初始化O( k )，其餘操作皆為O(1)
只有初始化的時候需要先建立一個長度為k的空陣列。

其餘的推入元素，取出元素，檢查是否為空，檢查是否全滿，皆為常數空間O(1)

關鍵知識點

在於理解環狀柱列同樣保有First In First Out 先進先出FIFO的特質，差別在於環狀柱列頭部、尾部指針移動的處理。

Reference:

[1] Python sol. based on native list. run-time 90%+ - Design Circular Queue - LeetCode