[Swift]LeetCode622. 设计循环队列 | Design Circular Queue
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10472658.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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. It is also called "Ring Buffer".
One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.
Your implementation should support following operations:
MyCircularQueue(k): Constructor, set the size of the queue to be k.Front: Get the front item from the queue. If the queue is empty, return -1.Rear: Get the last item from the queue. If the queue is empty, return -1.enQueue(value): Insert an element into the circular queue. Return true if the operation is successful.deQueue(): Delete an element from the circular queue. Return true if the operation is successful.isEmpty(): Checks whether the circular queue is empty or not.isFull(): Checks whether the circular queue is full or not.
Example:
MyCircularQueue circularQueue = new MyCircularQueue(3); // set the size to be 3 circularQueue.enQueue(1); // return true circularQueue.enQueue(2); // return true circularQueue.enQueue(3); // return true circularQueue.enQueue(4); // return false, the queue is full circularQueue.Rear(); // return 3 circularQueue.isFull(); // return true circularQueue.deQueue(); // return true circularQueue.enQueue(4); // return true circularQueue.Rear(); // return 4
Note:
- All values will be in the range of [0, 1000].
- The number of operations will be in the range of [1, 1000].
- Please do not use the built-in Queue library.
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
示例：
MyCircularQueue circularQueue = new MycircularQueue(3); // 设置长度为 3 circularQueue.enQueue(1); // 返回 true circularQueue.enQueue(2); // 返回 true circularQueue.enQueue(3); // 返回 true circularQueue.enQueue(4); // 返回 false，队列已满 circularQueue.Rear(); // 返回 3 circularQueue.isFull(); // 返回 true circularQueue.deQueue(); // 返回 true circularQueue.enQueue(4); // 返回 true circularQueue.Rear(); // 返回 4
提示：
- 所有的值都在 0 至 1000 的范围内；
- 操作数将在 1 至 1000 的范围内；
- 请不要使用内置的队列库。
Runtime: 124 ms
Memory Usage: 20.2 MB
1 class MyCircularQueue {
2
3 var array: [Int] = []
4
5 var curLength = 0
6 var length = 0
7
8 var startIndex = 0
9 var endIndex = -1
10
11 /** Initialize your data structure here. Set the size of the queue to be k. */
12 init(_ k: Int) {
13 length = k
14
15 for _ in 0..<k {
16 array.append(0)
17 }
18 }
19 /** Insert an element into the circular queue. Return true if the operation is successful. */
20
21 func enQueue(_ value: Int) -> Bool {
22
23 if curLength == length {
24 return false
25 } else {
26 endIndex = (endIndex + 1) % length
27 array[endIndex] = value
28
29 curLength += 1
30
31 return true
32 }
33 }
34 /** Delete an element from the circular queue. Return true if the operation is successful. */
35
36 func deQueue() -> Bool {
37
38 if curLength == 0 {
39 return false
40 } else {
41 startIndex = (startIndex + 1) % length
42 curLength -= 1
43
44 return true
45 }
46 }
47 /** Get the front item from the queue. */
48
49 func Front() -> Int {
50
51 if curLength == 0 {
52 return -1
53 } else {
54 return array[startIndex]
55 }
56 }
57 /** Get the last item from the queue. */
58
59 func Rear() -> Int {
60
61 if curLength == 0 {
62 return -1
63 } else {
64 return array[endIndex]
65 }
66 }
67 /** Checks whether the circular queue is empty or not. */
68
69 func isEmpty() -> Bool {
70 if curLength == 0 {
71 return true
72 } else {
73 return false
74 }
75 }
76 /** Checks whether the circular queue is full or not. */
77
78 func isFull() -> Bool {
79 if curLength == length {
80 return true
81 } else {
82 return false
83 }
84 }
85 }
86
87 /**
88 * Your MyCircularQueue object will be instantiated and called as such:
89 * let obj = MyCircularQueue(k)
90 * let ret_1: Bool = obj.enQueue(value)
91 * let ret_2: Bool = obj.deQueue()
92 * let ret_3: Int = obj.Front()
93 * let ret_4: Int = obj.Rear()
94 * let ret_5: Bool = obj.isEmpty()
95 * let ret_6: Bool = obj.isFull()
96 */144ms
1 class MyCircularQueue {
2
3 private var queue: [Int]
4 private var size: Int
5 private let cap: Int
6 private var front: Int
7 private var rear: Int
8
9 /** Initialize your data structure here. Set the size of the queue to be k. */
10 init(_ k: Int) {
11 queue = Array(repeating: 0, count: k)
12 size = 0
13 cap = k
14 front = 0
15 rear = -1
16 }
17 /** Insert an element into the circular queue. Return true if the operation is successful. */
18
19 func enQueue(_ value: Int) -> Bool {
20 guard !isFull() else { return false }
21 rear = (rear + 1) % cap
22 queue[rear] = value
23 size += 1
24 return true
25 }
26 /** Delete an element from the circular queue. Return true if the operation is successful. */
27
28 func deQueue() -> Bool {
29 guard !isEmpty() else { return false }
30 front = (front + 1) % cap
31 size -= 1
32 return true
33
34 }
35 /** Get the front item from the queue. */
36
37 func Front() -> Int {
38 guard !isEmpty() else { return -1 }
39 return queue[front]
40 }
41 /** Get the last item from the queue. */
42
43 func Rear() -> Int {
44 guard !isEmpty() else { return -1 }
45 return queue[rear]
46 }
47 /** Checks whether the circular queue is empty or not. */
48
49 func isEmpty() -> Bool {
50 return size == 0
51 }
52 /** Checks whether the circular queue is full or not. */
53
54 func isFull() -> Bool {
55 return size == cap
56 }
57 }
58
59 /**
60 * Your MyCircularQueue object will be instantiated and called as such:
61 * let obj = MyCircularQueue(k)
62 * let ret_1: Bool = obj.enQueue(value)
63 * let ret_2: Bool = obj.deQueue()
64 * let ret_3: Int = obj.Front()
65 * let ret_4: Int = obj.Rear()
66 * let ret_5: Bool = obj.isEmpty()
67 * let ret_6: Bool = obj.isFull()
68 */148ms
1 class MyCircularQueue {
2 private var size: Int = 0
3 private var head: Int = -1
4 private var tail: Int = -1
5 private var data = [Int]()
6
7 /** Initialize your data structure here. Set the size of the queue to be k. */
8 init(_ k: Int) {
9 size = k;
10 data = Array(repeating: 0, count: size)
11 }
12
13 /** Insert an element into the circular queue. Return true if the operation is successful. */
14 func enQueue(_ value: Int) -> Bool {
15 var tempHead = head+1
16 if tempHead == size {
17 tempHead = 0
18 }
19 if tempHead == tail {
20 return false
21 }
22
23 head = tempHead
24 if tail == -1 {
25 tail = tempHead
26 }
27 data[head] = value
28 return true
29 }
30 /** Delete an element from the circular queue. Return true if the operation is successful. */
31
32 func deQueue() -> Bool {
33 if tail == -1 {
34 return false
35 }
36
37 if head == tail {
38 head = -1
39 tail = -1
40 return true
41 }
42
43 tail = tail + 1
44 if tail == size {
45 tail = 0
46 }
47 return true
48 }
49 /** Get the front item from the queue. */
50
51 func Front() -> Int {
52 if tail == -1 {
53 return -1
54 }
55 return data[tail]
56
57 }
58 /** Get the last item from the queue. */
59
60 func Rear() -> Int {
61 if head == -1 {
62 return -1
63 }
64 return data[head]
65
66 }
67 /** Checks whether the circular queue is empty or not. */
68
69 func isEmpty() -> Bool {
70 if head == -1 {
71 return true
72 }
73 return false
74
75 }
76 /** Checks whether the circular queue is full or not. */
77
78 func isFull() -> Bool {
79 if (head+1 == tail) {
80 return true
81 }
82 else {
83 if ( (head+1-size) == tail) {
84 return true
85 }
86 return false
87 }
88 }
89 }
90
91 /**
92 * Your MyCircularQueue object will be instantiated and called as such:
93 * let obj = MyCircularQueue(k)
94 * let ret_1: Bool = obj.enQueue(value)
95 * let ret_2: Bool = obj.deQueue()
96 * let ret_3: Int = obj.Front()
97 * let ret_4: Int = obj.Rear()
98 * let ret_5: Bool = obj.isEmpty()
99 * let ret_6: Bool = obj.isFull()
100 */152ms
1 class MyCircularQueue {
2 private var circularArray: [Int]
3 private var readIndex = 0
4 private var writeIndex = 0
5 /** Initialize your data structure here. Set the size of the queue to be k. */
6 init(_ k: Int) {
7 circularArray = Array(repeating: 0, count: k)
8 }
9 /** Insert an element into the circular queue. Return true if the operation is successful. */
10
11 func enQueue(_ value: Int) -> Bool {
12 guard !isFull() else {
13 return false
14 }
15 circularArray[writeIndex % circularArray.count] = value
16 writeIndex += 1
17 return true
18 }
19 /** Delete an element from the circular queue. Return true if the operation is successful. */
20
21 func deQueue() -> Bool {
22 guard !isEmpty() else {
23 return false
24 }
25 readIndex += 1
26 return true
27 }
28 /** Get the front item from the queue. */
29
30 func Front() -> Int {
31 guard !isEmpty() else {
32 return -1
33 }
34 return circularArray[readIndex % circularArray.count]
35 }
36 /** Get the last item from the queue. */
37
38 func Rear() -> Int {
39 guard !isEmpty() else {
40 return -1
41 }
42 return circularArray[ (writeIndex - 1) % circularArray.count ]
43 }
44 /** Checks whether the circular queue is empty or not. */
45
46 func isEmpty() -> Bool {
47 return writeIndex == readIndex
48 }
49 /** Checks whether the circular queue is full or not. */
50
51 func isFull() -> Bool {
52 return writeIndex - readIndex == circularArray.count
53 }
54 }
55
56 /**
57 * Your MyCircularQueue object will be instantiated and called as such:
58 * let obj = MyCircularQueue(k)
59 * let ret_1: Bool = obj.enQueue(value)
60 * let ret_2: Bool = obj.deQueue()
61 * let ret_3: Int = obj.Front()
62 * let ret_4: Int = obj.Rear()
63 * let ret_5: Bool = obj.isEmpty()
64 * let ret_6: Bool = obj.isFull()
65 */164ms
1 class MyCircularQueue {
2
3 private var queueSize: Int = 0
4 private var queue = [Int: Int]()
5
6 private var frontIndex: Int = 0
7 private var endIndex: Int = 0
8
9 /** Initialize your data structure here. Set the size of the queue to be k. */
10 init(_ k: Int) {
11 queueSize = k
12 }
13 /** Insert an element into the circular queue. Return true if the operation is successful. */
14
15 func enQueue(_ value: Int) -> Bool {
16 if !isFull() {
17 if queue[endIndex] != nil {
18 endIndex = updateIndex(from: endIndex)
19 }
20 queue[endIndex] = value
21 return true
22 } else {
23 return false
24 }
25 }
26 /** Delete an element from the circular queue. Return true if the operation is successful. */
27
28 func deQueue() -> Bool {
29
30 if !isEmpty() {
31 queue.removeValue(forKey: frontIndex)
32 frontIndex = updateIndex(from: frontIndex)
33 endIndex = isEmpty() ? frontIndex : endIndex
34 return true
35 } else {
36 return false
37 }
38 }
39 /** Get the front item from the queue. */
40
41 func Front() -> Int {
42 return isEmpty() ? -1 : queue[frontIndex] ?? -1
43 }
44 /** Get the last item from the queue. */
45
46 func Rear() -> Int {
47 return isEmpty() ? -1 : queue[endIndex] ?? -1
48 }
49 /** Checks whether the circular queue is empty or not. */
50
51 func isEmpty() -> Bool {
52 return queue.count == 0
53 }
54 /** Checks whether the circular queue is full or not. */
55
56 func isFull() -> Bool {
57 return queue.count >= queueSize
58 }
59
60 private func updateIndex(from index: Int) -> Int {
61 return index < queueSize - 1 ? index + 1 : 0
62 }
63 }
64
65 /**
66 * Your MyCircularQueue object will be instantiated and called as such:
67 * let obj = MyCircularQueue(k)
68 * let ret_1: Bool = obj.enQueue(value)
69 * let ret_2: Bool = obj.deQueue()
70 * let ret_3: Int = obj.Front()
71 * let ret_4: Int = obj.Rear()
72 * let ret_5: Bool = obj.isEmpty()
73 * let ret_6: Bool = obj.isFull()
74 */192ms
1 class MyCircularQueue {
2
3 private var data: [Int]
4 private var p_start: Int
5 private var p_tail: Int
6 private var count: Int
7 private var len: Int
8
9 /** Initialize your data structure here. Set the size of the queue to be k. */
10 init(_ k: Int) {
11 data = [Int].init(repeating: 0, count: k)
12 p_start = 0
13 p_tail = 0
14 len = k
15 count = 0
16 }
17 /** Insert an element into the circular queue. Return true if the operation is successful. */
18
19 func enQueue(_ value: Int) -> Bool {
20 if isFull() { return false }
21
22 data[p_tail] = value
23 count += 1
24 p_tail = (p_tail + 1) % len
25 return true
26
27 }
28 /** Delete an element from the circular queue. Return true if the operation is successful. */
29
30 func deQueue() -> Bool {
31 if isEmpty() { return false }
32 p_start = (p_start + 1) % len
33 count -= 1
34 return true
35
36 }
37 /** Get the front item from the queue. */
38
39 func Front() -> Int {
40 if isEmpty() {
41 return -1
42 }
43 return data[p_start]
44 }
45 /** Get the last item from the queue. */
46
47 func Rear() -> Int {
48 if isEmpty() {
49 return -1
50 }
51 let temp: Int = p_tail == 0 ? (len - 1) : (p_tail - 1)
52 return data[temp]
53 }
54 /** Checks whether the circular queue is empty or not. */
55
56 func isEmpty() -> Bool {
57 return count == 0
58 }
59 /** Checks whether the circular queue is full or not. */
60
61 func isFull() -> Bool {
62 return count == len
63 }
64 }
65
66 /**
67 * Your MyCircularQueue object will be instantiated and called as such:
68 * let obj = MyCircularQueue(k)
69 * let ret_1: Bool = obj.enQueue(value)
70 * let ret_2: Bool = obj.deQueue()
71 * let ret_3: Int = obj.Front()
72 * let ret_4: Int = obj.Rear()
73 * let ret_5: Bool = obj.isEmpty()
74 * let ret_6: Bool = obj.isFull()
75 */204ms
1 class MyCircularQueue {
2 var maxQueueSize: Int
3 var circleQueue: Array<Int>
4 var head: Int
5 var rear: Int
6 let maxValue = 1000
7
8 /** Initialize your data structure here. Set the size of the queue to be k. */
9 init(_ k: Int) {
10 maxQueueSize = k
11 circleQueue = Array(repeating: -1, count: k)
12 head = -1
13 rear = -1
14 }
15
16 /** Insert an element into the circular queue. Return true if the operation is successful. */
17 func enQueue(_ value: Int) -> Bool {
18 if value < 0 || value > maxValue {
19 return false
20 }
21
22 if isFull() {
23 return false
24 }
25
26 if isEmpty() {
27 head = 0
28 }
29
30 rear = (rear + 1) % maxQueueSize
31 circleQueue[rear] = value
32 return true
33 }
34
35 /** Delete an element from the circular queue. Return true if the operation is successful. */
36 func deQueue() -> Bool {
37 if isEmpty() {
38 return false
39 }
40
41 if head == rear {
42 head = -1
43 rear = -1
44 return true
45 }
46
47 head = (head + 1) % maxQueueSize
48 return true
49 }
50
51 /** Get the front item from the queue. */
52 func Front() -> Int {
53 if isEmpty() {
54 return -1
55 }
56 return circleQueue[head]
57 }
58
59 /** Get the last item from the queue. */
60 func Rear() -> Int {
61 if isEmpty() {
62 return -1
63 }
64 return circleQueue[rear]
65 }
66
67 /** Checks whether the circular queue is empty or not. */
68 func isEmpty() -> Bool {
69 return head == -1
70 }
71
72 /** Checks whether the circular queue is full or not. */
73 func isFull() -> Bool {
74 return head == (rear + 1) % maxQueueSize
75 }
76 }236ms
1 class MyCircularQueue {
2
3 var arr:Array<Int>?
4 var head:Int = -1
5 var tail:Int = -1
6 var size:Int?
7
8 /** Initialize your data structure here. Set the size of the queue to be k. */
9 init(_ k: Int) {
10 arr = Array.init(repeating: 0, count: k)
11 size = k
12 }
13 /** Insert an element into the circular queue. Return true if the operation is successful. */
14
15 func enQueue(_ value: Int) -> Bool {
16 if isFull() == true {
17 return false
18 }
19
20 if isEmpty() == true{
21 head = 0
22 }
23 tail = (tail + 1) % size!
24 arr![tail] = value
25 return true
26 }
27 /** Delete an element from the circular queue. Return true if the operation is successful. */
28
29 func deQueue() -> Bool {
30 if isEmpty() == true{
31 return false
32 }
33
34 if head == tail{
35 head = -1
36 tail = -1
37 return true
38 }
39 head = (head + 1) % size!
40 return true
41 }
42 /** Get the front item from the queue. */
43
44 func Front() -> Int {
45 if isEmpty() == true{
46 return -1
47 }
48 return arr![head]
49 }
50 /** Get the last item from the queue. */
51
52 func Rear() -> Int {
53 if isEmpty() == true {
54 return -1
55 }
56 return arr![tail]
57 }
58 /** Checks whether the circular queue is empty or not. */
59
60 func isEmpty() -> Bool {
61 return head == -1
62 }
63 /** Checks whether the circular queue is full or not. */
64
65 func isFull() -> Bool {
66 return ((tail + 1) % size!) == head
67 }
68 }