[Swift]LeetCode225.用队列实现栈|ImplementStackusingQueues

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

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

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

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

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

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

Implement the following operations of a stack using queues.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
empty() -- Return whether the stack is empty.

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes:

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

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

push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空

注意:

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

8ms

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

8ms

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

12ms

 1 class MyStack {
 2 
 3     private var queue = [Int]()
 4 
 5     /** Initialize your data structure here. */
 6     init() {
 7 
 8     }
 9 
10     /** Push element x onto stack. */
11     func push(_ x: Int) {
12         queue.append(x)
13         for _ in 0..<queue.count - 1 {
14             queue.append(queue.removeFirst())
15         }
16     }
17 
18     /** Removes the element on top of the stack and returns that element. */
19     func pop() -> Int {
20         return queue.removeFirst()
21     }
22 
23     /** Get the top element. */
24     func top() -> Int {
25         return queue.first!
26     }
27 
28     /** Returns whether the stack is empty. */
29     func empty() -> Bool {
30         return queue.isEmpty
31     }
32 }

16ms

  1 //: [Previous](@previous)
  2 
  3 import Foundation
  4 
  5 
  6 class MyQueue {
  7     
  8     var array = Array<Int>()
  9     
 10     /** Initialize your data structure here. */
 11     init() {
 12         array = []
 13     }
 14     
 15     /** Push element x to the back of queue. */
 16     func push(_ x: Int) {
 17         array.append(x)
 18     }
 19     
 20     /** Removes the element from in front of queue and returns that element. */
 21     func pop() -> Int {
 22         let last = array.first!
 23         array.remove(at: 0)
 24         return last
 25     }
 26     
 27     /** Get the front element. */
 28     func peek() -> Int {
 29         return array.first!
 30     }
 31     
 32     /** Returns whether the queue is empty. */
 33     func empty() -> Bool {
 34         return array.count == 0
 35     }
 36     
 37     func size() -> Int {
 38         
 39         return array.count;
 40     }
 41 }
 42 
 43 class MyStack {
 44     
 45     var queue: MyQueue?
 46     var helpQueue: MyQueue?
 47     /** Initialize your data structure here. */
 48     
 49     init() {
 50         queue = MyQueue.init()
 51         helpQueue = MyQueue.init()
 52     }
 53     
 54     /** Push element x onto stack. */
 55     func push(_ x: Int) {
 56         queue?.push(x)
 57     }
 58     
 59     /** Removes the element on top of the stack and returns that element. */
 60     func pop() -> Int {
 61         
 62         shift()
 63         let popObj = queue?.pop()
 64         swap()
 65         return popObj!
 66     }
 67     
 68     /** Get the top element. */
 69     func top() -> Int {
 70         shift()
 71         let popObj = queue!.peek()
 72         helpQueue?.push(queue!.pop())
 73         swap()
 74         return popObj
 75     }
 76     
 77     /** Returns whether the stack is empty. */
 78     func empty() -> Bool {
 79         
 80         return queue!.empty() && helpQueue!.empty();
 81     }
 82     
 83     func swap() {
 84         
 85         (queue, helpQueue) = (helpQueue, queue)
 86     }
 87     
 88     func shift() {
 89         
 90         while queue?.size() != 1 {
 91             
 92             helpQueue?.push(queue!.pop())
 93         }
 94     }
 95     
 96 }
 97 
 98 /**
 99  * Your MyStack object will be instantiated and called as such:
100  * let obj = MyStack()
101  * obj.push(x)
102  * let ret_2: Int = obj.pop()
103  * let ret_3: Int = obj.top()
104  * let ret_4: Bool = obj.empty()
105  */