225. 用队列实现栈 [easy]

https://leetcode-cn.com/problems/implement-stack-using-queues/

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

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

注意:

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

通过次数57,775 | 提交次数89,106

Second Try

2020-06-24

看题解才知道的单队列版本，思路很不错，写起来也简洁，虽然在提交得分上并没有什么优势。

python pop

另外原来python的pop可以选择任意index位置，我竟然不知道，一直以为只能踢出最后一位。

In [113]: a = [1, 2]

In [114]: a.pop(0)
Out[114]: 1

In [115]: a.pop?
Docstring:
L.pop([index]) -> item -- remove and return item at index (default last).
Raises IndexError if list is empty or index is out of range.
Type:      builtin_function_or_method

题解

class Queue(object):
    def __init__(self):
        self.q = []

    def push(self, x):
        self.q.insert(0, x)

    def pop(self):
        assert not self.empty(), "queue empty, pop not allowed"
        return self.q.pop()

    def peek(self):
        assert not self.empty(), "queue empty, peek not allowed"
        return self.q[-1]
    
    def empty(self):
        return len(self.q) == 0
    
    def size(self):
        return len(self.q)


class MyStack(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.q = Queue()


    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: None
        """
        self.q.push(x)
        i = 1
        while i < self.q.size():
            self.q.push(self.q.pop())
            i += 1
        
    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        不用考虑异常操作; 每次都倒腾一遍操作？
        """
        return self.q.pop()
          
    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        return self.q.peek()

    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        return self.q.empty()

执行用时：20 ms, 在所有 Python 提交中击败了67.45%的用户
内存消耗：12.8 MB, 在所有 Python 提交中击败了100.00%的用户

First Try

2020-06-24

双队列操作，比较繁琐，但毕竟通过了，而且空间消耗竟然也能排名100%。

class MyStack(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """

        class Queue(object):
            def __init__(self):
                self.q = []

            def push(self, x):
                self.q.insert(0, x)

            def pop(self):
                assert not self.empty(), "queue empty, pop not allowed"
                return self.q.pop()

            def peek(self, x):
                return self.q[-1]
            
            def empty(self):
                return len(self.q) == 0
            
            def size(self):
                return len(self.q)

        self.qone = Queue()
        self.qtwo = Queue()
        self.qs = [self.qone, self.qtwo]
        self.idx = 1

    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: None
        """
        self.qs[self.idx].push(x)


    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        不用考虑异常操作; 每次都倒腾一遍操作？
        """
        while self.qs[self.idx].size() > 1:
            self.qs[1 - self.idx].push(self.qs[self.idx].pop())
        rv = self.qs[self.idx].pop()
        self.idx = 1 - self.idx
        return rv
                
    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        rv = self.pop()
        self.push(rv)
        return rv


    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        return self.qs[self.idx].empty()



# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

执行用时：16 ms, 在所有 Python 提交中击败了87.91%的用户
内存消耗：13 MB, 在所有 Python 提交中击败了100.00%

225. 用队列实现栈 [easy]​

Second Try​

First Try​

225. 用队列实现栈 [easy]

Second Try

First Try