[Swift]LeetCode641. 设计循环双端队列 | Design Circular Deque
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10479758.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
Design your implementation of the circular double-ended queue (deque).
Your implementation should support following operations:
MyCircularDeque(k): Constructor, set the size of the deque to be k.insertFront(): Adds an item at the front of Deque. Return true if the operation is successful.insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful.deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful.getFront(): Gets the front item from the Deque. If the deque is empty, return -1.getRear(): Gets the last item from Deque. If the deque is empty, return -1.isEmpty(): Checks whether Deque is empty or not.isFull(): Checks whether Deque is full or not.
Example:
MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3 circularDeque.insertLast(1); // return true circularDeque.insertLast(2); // return true circularDeque.insertFront(3); // return true circularDeque.insertFront(4); // return false, the queue is full circularDeque.getRear(); // return 2 circularDeque.isFull(); // return true circularDeque.deleteLast(); // return true circularDeque.insertFront(4); // return true circularDeque.getFront(); // 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 Deque library.
设计实现双端队列。
你的实现需要支持以下操作：
- MyCircularDeque(k)：构造函数,双端队列的大小为k。
- insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
- insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
- deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
- deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
- getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
- getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
- isEmpty()：检查双端队列是否为空。
- isFull()：检查双端队列是否满了。
示例：
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3 circularDeque.insertLast(1); // 返回 true circularDeque.insertLast(2); // 返回 true circularDeque.insertFront(3); // 返回 true circularDeque.insertFront(4); // 已经满了，返回 false circularDeque.getRear(); // 返回 2 circularDeque.isFull(); // 返回 true circularDeque.deleteLast(); // 返回 true circularDeque.insertFront(4); // 返回 true circularDeque.getFront(); // 返回 4
提示：
- 所有值的范围为 [1, 1000]
- 操作次数的范围为 [1, 1000]
- 请不要使用内置的双端队列库。
Runtime: 136 ms
Memory Usage: 20.5 MB
1 class MyCircularDeque {
2 var data:[Int]
3 var size:Int
4
5 /** Initialize your data structure here. Set the size of the deque to be k. */
6 init(_ k: Int) {
7 data = [Int]()
8 size = k
9 }
10
11 /** Adds an item at the front of Deque. Return true if the operation is successful. */
12 func insertFront(_ value: Int) -> Bool {
13 if isFull() {return false}
14 data.insert(value,at:0)
15 return true
16 }
17
18 /** Adds an item at the rear of Deque. Return true if the operation is successful. */
19 func insertLast(_ value: Int) -> Bool {
20 if isFull() {return false}
21 data.append(value)
22 return true
23 }
24
25 /** Deletes an item from the front of Deque. Return true if the operation is successful. */
26 func deleteFront() -> Bool {
27 if isEmpty() {return false}
28 data.removeFirst()
29 return true
30 }
31
32 /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
33 func deleteLast() -> Bool {
34 if isEmpty() {return false}
35 data.popLast()
36 return true
37 }
38
39 /** Get the front item from the deque. */
40 func getFront() -> Int {
41 if isEmpty() {return -1}
42 return data.first!
43
44 }
45
46 /** Get the last item from the deque. */
47 func getRear() -> Int {
48 if isEmpty() {return -1}
49 return data.last!
50 }
51
52 /** Checks whether the circular deque is empty or not. */
53 func isEmpty() -> Bool {
54 return data.isEmpty
55 }
56
57 /** Checks whether the circular deque is full or not. */
58 func isFull() -> Bool {
59 return data.count >= size
60 }
61 }
62
63 /**
64 * Your MyCircularDeque object will be instantiated and called as such:
65 * let obj = MyCircularDeque(k)
66 * let ret_1: Bool = obj.insertFront(value)
67 * let ret_2: Bool = obj.insertLast(value)
68 * let ret_3: Bool = obj.deleteFront()
69 * let ret_4: Bool = obj.deleteLast()
70 * let ret_5: Int = obj.getFront()
71 * let ret_6: Int = obj.getRear()
72 * let ret_7: Bool = obj.isEmpty()
73 * let ret_8: Bool = obj.isFull()
74 */ 156ms
1 class MyCircularDeque: CustomStringConvertible {
2
3 var capacity: Int {
4 return deque.count
5 }
6
7 var description: String {
8 return deque.description
9 }
10
11 private var deque: [Int]
12
13 private var frontIndex: Int?
14 private var rearIndex: Int?
15
16 /** Initialize your data structure here. Set the size of the deque to be k. */
17 init(_ k: Int) {
18 self.deque = [Int].init(repeating: 0, count: k)
19 }
20
21 /** Adds an item at the front of Deque. Return true if the operation is successful. */
22 func insertFront(_ value: Int) -> Bool {
23 guard isFull() == false else {
24 return false
25 }
26
27 if var front = self.frontIndex {
28 front = shiftBackwards(front)
29 self.frontIndex = front
30 deque[front] = value
31
32 } else {
33 self.frontIndex = 0
34 self.rearIndex = 0
35 deque[0] = value
36 }
37
38 return true
39 }
40
41 /** Adds an item at the rear of Deque. Return true if the operation is successful. */
42 func insertLast(_ value: Int) -> Bool {
43 guard isFull() == false else {
44 return false
45 }
46
47 if var rear = self.rearIndex {
48 rear = shiftForwards(rear)
49 self.rearIndex = rear
50 deque[rear] = value
51
52 } else {
53 self.frontIndex = 0
54 self.rearIndex = 0
55 deque[0] = value
56 }
57
58 return true
59 }
60
61 /** Deletes an item from the front of Deque. Return true if the operation is successful. */
62 func deleteFront() -> Bool {
63 guard isEmpty() == false else {
64 return false
65 }
66
67 guard let front = self.frontIndex else {
68 fatalError("front must be valid in a non empty deque")
69 }
70
71 if front == self.rearIndex {
72 self.frontIndex = nil
73 self.rearIndex = nil
74 } else {
75 self.frontIndex = shiftForwards(front)
76 }
77
78 return true
79 }
80
81 /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
82 func deleteLast() -> Bool {
83 guard isEmpty() == false else {
84 return false
85 }
86
87 guard let rear = self.rearIndex else {
88 fatalError("rear must be valid in a non empty deque")
89 }
90
91 if rear == self.frontIndex {
92 self.frontIndex = nil
93 self.rearIndex = nil
94 } else {
95 self.rearIndex = shiftBackwards(rear)
96 }
97
98 return true
99 }
100
101 /** Get the front item from the deque. */
102 func getFront() -> Int {
103 guard let front = self.frontIndex else {
104 return -1
105 }
106
107 return self.deque[front]
108 }
109
110 /** Get the last item from the deque. */
111 func getRear() -> Int {
112 guard let rear = self.rearIndex else {
113 return -1
114 }
115
116 return self.deque[rear]
117 }
118
119 /** Checks whether the circular deque is empty or not. */
120 func isEmpty() -> Bool {
121 return self.frontIndex == nil && self.rearIndex == nil
122 }
123
124 /** Checks whether the circular deque is full or not. */
125 func isFull() -> Bool {
126 if let front = self.frontIndex, let rear = self.rearIndex {
127
128 if rear < front, front == shiftForwards(rear) {
129 return true
130 }
131
132 if rear > front, front == 0, rear == self.capacity - 1 {
133 return true
134 }
135 }
136
137 return false
138 }
139
140 private func shiftForwards(_ i: Int) -> Int {
141 var index = i + 1
142 if index == capacity {
143 index = 0
144 }
145
146 return index
147 }
148
149 private func shiftBackwards(_ i: Int) -> Int {
150 var index = i - 1
151 if index == -1 {
152 index = capacity - 1
153 }
154
155 return index
156 }
157 }160ms
1 class MyCircularDeque {
2 private class Node {
3 public var prev: Node?
4 public var next: Node?
5 public var val: Int
6
7 init(_ val: Int) {
8 self.val = val
9 }
10 }
11
12 private var head: Node?
13 private var tail: Node?
14 private var maxSize: Int
15 private var size: Int
16
17 /** Initialize your data structure here. Set the size of the deque to be k. */
18 init(_ k: Int) {
19 self.maxSize = k
20 self.size = 0
21 }
22
23 /** Adds an item at the front of Deque. Return true if the operation is successful. */
24 func insertFront(_ value: Int) -> Bool {
25 guard self.size < self.maxSize else {
26 return false
27 }
28
29 let node = Node(value)
30 node.prev = self.head
31 self.head?.next = node
32 self.head = node
33 if size == 0 {
34 self.tail = node
35 }
36 self.size += 1
37
38 return true
39 }
40
41 /** Adds an item at the rear of Deque. Return true if the operation is successful. */
42 func insertLast(_ value: Int) -> Bool {
43 guard self.size < self.maxSize else {
44 return false
45 }
46
47 let node = Node(value)
48 node.next = self.tail
49 self.tail?.prev = node
50 self.tail = node
51 if size == 0 {
52 self.head = node
53 }
54 self.size += 1
55
56 return true
57 }
58
59 /** Deletes an item from the front of Deque. Return true if the operation is successful. */
60 func deleteFront() -> Bool {
61 guard self.size > 0 else {
62 return false
63 }
64
65 self.head = self.head?.prev
66 self.head?.next = nil
67 self.size -= 1
68 if self.size == 0 {
69 self.head = nil
70 self.tail = nil
71 }
72
73 return true
74 }
75
76 /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
77 func deleteLast() -> Bool {
78 guard self.size > 0 else {
79 return false
80 }
81
82 self.tail = self.tail?.next
83 self.tail?.prev = nil
84 self.size -= 1
85 if self.size == 0 {
86 self.head = nil
87 self.tail = nil
88 }
89
90 return true
91
92 }
93
94 /** Get the front item from the deque. */
95 func getFront() -> Int {
96 return self.head?.val ?? -1
97 }
98
99 /** Get the last item from the deque. */
100 func getRear() -> Int {
101 return self.tail?.val ?? -1
102 }
103
104 /** Checks whether the circular deque is empty or not. */
105 func isEmpty() -> Bool {
106 return self.size == 0
107 }
108
109 /** Checks whether the circular deque is full or not. */
110 func isFull() -> Bool {
111 return self.size == self.maxSize
112 }
113
114 func getList() -> [Int] {
115 var l: [Int] = []
116
117 var node = self.head
118 while node != nil {
119 l.append(node!.val)
120 node = node!.prev
121 }
122
123 return l
124 }
125 }196ms
1 class MyCircularDeque {
2
3 private var array = [Int]()
4 private var maxSize = 0
5 /** Initialize your data structure here. Set the size of the deque to be k. */
6 init(_ k: Int) {
7 maxSize = k
8 }
9
10 /** Adds an item at the front of Deque. Return true if the operation is successful. */
11 func insertFront(_ value: Int) -> Bool {
12 guard array.count < maxSize else {
13 return false
14 }
15
16 array.insert(value, at: 0)
17 return true
18 }
19
20 /** Adds an item at the rear of Deque. Return true if the operation is successful. */
21 func insertLast(_ value: Int) -> Bool {
22 guard array.count < maxSize else {
23 return false
24 }
25 array.append(value)
26 return true
27 }
28
29 /** Deletes an item from the front of Deque. Return true if the operation is successful. */
30 func deleteFront() -> Bool {
31 guard array.count >= 1 else {
32 return false
33 }
34
35 array.remove(at: 0)
36 return true
37 }
38
39 /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
40 func deleteLast() -> Bool {
41 guard array.count >= 1 else {
42 return false
43 }
44
45 array.removeLast()
46 return true
47 }
48
49 /** Get the front item from the deque. */
50 func getFront() -> Int {
51 guard let first = array.first else {
52 return -1
53 }
54
55 return first
56 }
57
58 /** Get the last item from the deque. */
59 func getRear() -> Int {
60 guard let last = array.last else {
61 return -1
62 }
63
64 return last
65 }
66
67 /** Checks whether the circular deque is empty or not. */
68 func isEmpty() -> Bool {
69 return array.count == 0
70 }
71
72 /** Checks whether the circular deque is full or not. */
73 func isFull() -> Bool {
74 return array.count == maxSize
75 }
76 }264ms
1 class MyCircularDeque {
2
3 var length = 0
4 var array:[Int] = []
5
6 /** Initialize your data structure here. Set the size of the deque to be k. */
7 init(_ k: Int) {
8 length = k
9 }
10
11 /** Adds an item at the front of Deque. Return true if the operation is successful. */
12 func insertFront(_ value: Int) -> Bool {
13 if array.count < length {
14 array.insert(value, at: 0)
15 return true
16 }else{
17 return false
18 }
19 }
20
21 /** Adds an item at the rear of Deque. Return true if the operation is successful. */
22 func insertLast(_ value: Int) -> Bool {
23 if array.count < length {
24 array.append(value)
25 return true
26 }else{
27 return false
28 }
29 }
30
31 /** Deletes an item from the front of Deque. Return true if the operation is successful. */
32 func deleteFront() -> Bool {
33 if array.count > 0 {
34 array.removeFirst()
35 return true
36 }else{
37 return false
38 }
39 }
40
41 /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
42 func deleteLast() -> Bool {
43 if array.count > 0 {
44 array.removeLast()
45 return true
46 }else{
47 return false
48 }
49 }
50
51 /** Get the front item from the deque. */
52 func getFront() -> Int {
53 if array.count == 0 {
54 return -1
55 }else{
56 return array.first!
57 }
58 }
59
60 /** Get the last item from the deque. */
61 func getRear() -> Int {
62 if array.count == 0 {
63 return -1
64 }else{
65 return array.last!
66 }
67 }
68
69 /** Checks whether the circular deque is empty or not. */
70 func isEmpty() -> Bool {
71 return array.count == 0
72 }
73
74 /** Checks whether the circular deque is full or not. */
75 func isFull() -> Bool {
76 return array.count == length
77 }
78 }