Implement Stack using Queues

 关注
发布于: 2020 年 05 月 24 日
对于队列，他有这几种操作：
﻿
enqueue()
dequeue()
isEmpty()
head()
size()
﻿
Queue 定义
class Queue {
    var array: [Int]
    init() {
        self.array = Array()
    }
    
    func enqueue(x: Int) {
        self.array.append(x)
    }
    
    func dequeue() -> Int {
        let first = self.head()
        if first != Int.min {
            self.array.removeFirst()
        }
        return first
    }
    
    func head() -> Int {
        if let first = self.array.first {
            return first
        }
        return Int.min
    }
    
    func size() -> Int {
        return self.array.count
    }
    
    func isEmpty() -> Bool {
        return self.array.isEmpty
    }
}
﻿
解决方案两个队列，push O(1)，pop O(n)﻿
Push 的操作栈和队列是一样的，pop 的操作，需要用一个临时队列将当前队列中的元素重新进入一次队列，然后取到最后一个进入队列的元素，将其作为结果返回，然后再将两个队列的引用调换；
﻿
class MyStack {
    var queueOne: Queue
    var queueTwo: Queue
    /** Initialize your data structure here. */
    init() {
        self.queueOne = Queue()
        self.queueTwo = Queue()
    }
    
    /** Push element x onto stack. */
    func push(_ x: Int) {
        self.queueOne.enqueue(x: x)
    }
    
    /** Removes the element on top of the stack and returns that element. */
    func pop() -> Int {
        if self.queueOne.isEmpty() {
            return Int.min
        }
        while self.queueOne.size() > 1 {
            let head = self.queueOne.dequeue()
            self.queueTwo.enqueue(x: head)
        }
        let stackTop = self.queueOne.dequeue()
        switchQueue()
        return stackTop
    }
    
    /** Get the top element. */
    func top() -> Int {
        var stackTop = Int.min
        while self.queueOne.size() > 0 {
            stackTop = self.queueOne.dequeue()
            self.queueTwo.enqueue(x: stackTop)
        }
        switchQueue()
        return stackTop
    }
    
    func switchQueue() {
        let tempQueue = self.queueOne
        self.queueOne = self.queueTwo
        self.queueTwo = tempQueue
    }
    
    /** Returns whether the stack is empty. */
    func empty() -> Bool {
        return self.queueOne.isEmpty()
    }
}
﻿
两个队列，push O(n)，pop O(1)﻿
和之前的思路是反过来的，每次 push 的时候都把队列翻转过来，只维护着一个和栈保持同样结构的队列
﻿
class MyStackTwo {
    var queueOne: Queue
    var queueTwo: Queue
    /** Initialize your data structure here. */
    init() {
        self.queueOne = Queue()
        self.queueTwo = Queue()
    }
    
    /** Push element x onto stack. */
    func push(_ x: Int) {
        self.queueTwo.enqueue(x: x)
        while !self.queueOne.isEmpty() {
            let head = self.queueOne.dequeue()
            self.queueTwo.enqueue(x: head)
        }
        switchQueue()
    }
    
    /** Removes the element on top of the stack and returns that element. */
    func pop() -> Int {
        if self.queueOne.isEmpty() {
            return Int.min
        }
        return self.queueOne.dequeue()
    }
    
    /** Get the top element. */
    func top() -> Int {
        var stackTop = Int.min
        if !self.queueOne.isEmpty() {
            stackTop = self.queueOne.head()
        }
        return stackTop
    }
    
    func switchQueue() {
        let tempQueue = self.queueOne
        self.queueOne = self.queueTwo
        self.queueTwo = tempQueue
    }
    
    /** Returns whether the stack is empty. */
    func empty() -> Bool {
        return self.queueOne.isEmpty()
    }
}
﻿
用一个队列来实现﻿
Push O(n) 的做法是在 push 的时候就直接按照倒序的方式去存储队列；
Pop O(n) 的做法是在 Pop 的时候遍历一下队列，
把以上操作重新用这个方法重新实现一遍就可以了：
﻿
class MyStackThree {
    var queue: Queue
    /** Initialize your data structure here. */
    init() {
        self.queue = Queue()
    }
    
    /** Push element x onto stack. */
    func push(_ x: Int) {
        var size = self.queue.size()
        self.queue.enqueue(x: x)
        while size > 0 {
            self.queue.enqueue(x: self.queue.dequeue())
            size -= 1
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    func pop() -> Int {
        if self.queue.isEmpty() {
            return Int.min
        }
        return self.queue.dequeue()
    }
    
    /** Get the top element. */
    func top() -> Int {
        var stackTop = Int.min
        if !self.queue.isEmpty() {
            stackTop = self.queue.head()
        }
        return stackTop
    }
    
    /** Returns whether the stack is empty. */
    func empty() -> Bool {
        return self.queue.isEmpty()
    }
}
class MyStackFour {
    var queue: Queue
    /** Initialize your data structure here. */
    init() {
        self.queue = Queue()
    }
    
    /** Push element x onto stack. */
    func push(_ x: Int) {
        self.queue.enqueue(x: x)
    }
    
    /** Removes the element on top of the stack and returns that element. */
    func pop() -> Int {
        if self.queue.isEmpty() {
            return Int.min
        }
        var size = self.queue.size()
        while size > 1 {
            self.queue.enqueue(x: self.queue.dequeue())
            size -= 1
        }
        return self.queue.dequeue()
    }
    
    /** Get the top element. */
    func top() -> Int {
        var size = self.queue.size()
        var stackTop = Int.min
        while size > 0 {
            let head = self.queue.dequeue()
            self.queue.enqueue(x: head)
            if size == 1 {
                stackTop = head
            }
            size -= 1
        }
        return stackTop
    }
    
    /** Returns whether the stack is empty. */
    func empty() -> Bool {
        return self.queue.isEmpty()
    }
}
﻿
发布于: 2020 年 05 月 24 日阅读数: 28
Forelax

 关注
不想当个音乐家的程序员不是好猫奴 2016.03.26 加入
个人博客：https://forelax.space/ ，欢迎各种交流
发布
暂无评论