[Swift]LeetCode232.用栈实现队列|ImplementQueueusingStacks

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10204818.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）。

8ms

 1 class MyQueue {
 2     
 3     var input = [Int]()
 4     var output = [Int]()
 5     
 6     func push(_ x: Int) {
 7         input.append(x)
 8     }
 9     
10     func pop() -> Int {
11         if output.isEmpty {
12             inputToOutput()
13         }
14         return output.removeLast()
15     }
16     
17     func inputToOutput() {
18         while !input.isEmpty {
19             output.append(input.removeLast())
20         }
21     }
22     
23     func peek() -> Int {
24         if output.isEmpty {
25             inputToOutput()
26         }
27         return output.last!
28     }
29     
30     func empty() -> Bool {
31         return input.isEmpty && output.isEmpty
32     }
33 }
34 
35 /**
36  * Your MyQueue object will be instantiated and called as such:
37  * let obj = MyQueue()
38  * obj.push(x)
39  * let ret_2: Int = obj.pop()
40  * let ret_3: Int = obj.peek()
41  * let ret_4: Bool = obj.empty()
42  */
43

12ms

 1 class MyQueue {
 2 
 3     private var oldStack: [Int]
 4     private var newStack: [Int]
 5     /** Initialize your data structure here. */
 6     init() {
 7         oldStack = [Int]()
 8         newStack = [Int]()
 9     }
10     
11     /** Push element x to the back of queue. */
12     func push(_ x: Int) {
13       newStack.append(x)
14     }
15     
16     /** Removes the element from in front of queue and returns that element. */
17     func pop() -> Int {
18                 shiftStack()
19 
20       return oldStack.removeLast()
21     }
22     
23     /** Get the front element. */
24     func peek() -> Int {
25         shiftStack()
26       return oldStack.last!
27     }
28     
29     /** Returns whether the queue is empty. */
30     func empty() -> Bool {
31       return oldStack.isEmpty && newStack.isEmpty
32     }
33     private func shiftStack() {
34         if oldStack.isEmpty {
35             while !newStack.isEmpty {
36              oldStack.append(newStack.removeLast())
37             }
38         }
39     }
40 }
41 
42 /**
43  * Your MyQueue object will be instantiated and called as such:
44  * let obj = MyQueue()
45  * obj.push(x)
46  * let ret_2: Int = obj.pop()
47  * let ret_3: Int = obj.peek()
48  * let ret_4: Bool = obj.empty()
49  */
50

12ms

 1 class Stack {
 2     
 3     private var nums: [Int] = []
 4     
 5     var isEmpty: Bool {
 6         return nums.isEmpty
 7     }
 8     
 9     func push(_ x: Int) {
10         nums.append(x)
11     }
12     
13     func pop() -> Int? {
14         return nums.popLast()
15     }
16     
17     func peek() -> Int? {
18         return nums.last
19     }
20     
21 }
22 
23 class MyQueue {
24     
25     private let stack = Stack()
26     private let stack2 = Stack()
27 
28     /** Initialize your data structure here. */
29     init() {
30         
31     }
32     
33     /** Push element x to the back of queue. */
34     func push(_ x: Int) {
35         stack.push(x)
36     }
37     
38     /** Removes the element from in front of queue and returns that element. */
39     func pop() -> Int {
40         if stack2.isEmpty {
41             while let num = stack.pop() {
42                 stack2.push(num)
43             }
44         }
45         
46         return stack2.pop() ?? 0
47     }
48     
49     /** Get the front element. */
50     func peek() -> Int {
51         if stack2.isEmpty {
52             while let num = stack.pop() {
53                 stack2.push(num)
54             }
55         }
56         
57         return stack2.peek() ?? 0
58     }
59     
60     /** Returns whether the queue is empty. */
61     func empty() -> Bool {
62       return stack.isEmpty && stack2.isEmpty
63     }
64 }
65 
66 /**
67  * Your MyQueue object will be instantiated and called as such:
68  * let obj = MyQueue()
69  * obj.push(x)
70  * let ret_2: Int = obj.pop()
71  * let ret_3: Int = obj.peek()
72  * let ret_4: Bool = obj.empty()
73  */
74

16ms

 1 class MyQueue {
 2 
 3     fileprivate var stack = [Int?]()
 4     fileprivate var reserveStack = [Int?]()
 5     
 6     
 7     /** Initialize your data structure here. */
 8     init() {
 9         stack = [Int]()
10         reserveStack = [Int]()
11     }
12     
13     /** Push element x to the back of queue. */
14     func push(_ x: Int) {
15         if reserveStack.isEmpty{
16             stack.append(x)
17         }else{
18             // 翻转reserveStack
19             while !reserveStack.isEmpty {
20                 stack.append(reserveStack.popLast()!)
21             }
22             stack.append(x)
23         }
24         
25     }
26     
27     /** Removes the element from in front of queue and returns that element. */
28     func pop() -> Int {
29         
30         // 原栈为空，说明数据翻转到reserve栈中
31         if stack.isEmpty{
32             return reserveStack.removeLast()!
33         }
34         
35         // 翻转stack
36         while !stack.isEmpty {
37             reserveStack.append(stack.removeLast())
38         }
39         
40         return reserveStack.removeLast()!
41     }
42     
43     /** Get the front element. */
44     func peek() -> Int {
45        
46         // 原栈为空，说明数据翻转到reserve栈中
47         if stack.isEmpty{
48             return reserveStack.last!!
49         }
50         
51         // 翻转stack
52         while !stack.isEmpty {
53             reserveStack.append(stack.removeLast()!)
54         }
55         
56         return reserveStack.last!!
57     }
58     
59     /** Returns whether the queue is empty. */
60     func empty() -> Bool {
61         
62         if stack.isEmpty && reserveStack.isEmpty {
63             return true
64         }
65         
66         return false
67     }
68 }
69 
70 /**
71  * Your MyQueue object will be instantiated and called as such:
72  * let obj = MyQueue()
73  * obj.push(x)
74  * let ret_2: Int = obj.pop()
75  * let ret_3: Int = obj.peek()
76  * let ret_4: Bool = obj.empty()
77  */
78

20ms

 1 class MyQueue {
 2 
 3    var queue : [Int]
 4     /** Initialize your data structure here. */
 5     init() {
 6         self.queue = [Int]()
 7     }
 8     
 9     /** Push element x to the back of queue. */
10     func push(_ x: Int) {
11         self.queue.insert(x, at: 0)
12     }
13     
14     /** Removes the element from in front of queue and returns that element. */
15     func pop() -> Int {
16         return self.queue.removeLast()
17     }
18     
19     /** Get the front element. */
20     func peek() -> Int {
21         return self.queue.last!
22     }
23     
24     /** Returns whether the queue is empty. */
25     func empty() -> Bool {
26         return self.queue.isEmpty
27     }
28 }
29 
30 /**
31  * Your MyQueue object will be instantiated and called as such:
32  * let obj = MyQueue()
33  * obj.push(x)
34  * let ret_2: Int = obj.pop()
35  * let ret_3: Int = obj.peek()
36  * let ret_4: Bool = obj.empty()
37  */
38