Implement Stack using Queues#

1
MyStack stack = new MyStack();
2

3
stack.push(1);
4
stack.push(2);
5
stack.top();   // returns 2
6
stack.pop();   // returns 2
7
stack.empty(); // returns false

1
# @Author：Kilien
2
# @lc app=leetcode id=225 lang=python3
3
# [225] Implement Stack using Queues
4
# time:O(1)  space:O(n)
5
# 思路：双端队列，左进右出模拟栈
6
class MyStack:
7

8
    def __init__(self):
9
        """
10
        Initialize your data structure here.
11
        """
12
        self.stack = collections.deque([])
13

14

15
    def push(self, x: int) -> None:
16
        """
17
        Push element x onto stack.
18
        """
19
        self.stack.append(x)
20

21

22
    def pop(self) -> int:
23
        """
24
        Removes the element on top of the stack and returns that element.
25
        """
26
        for i in range(len(self.stack) - 1):
27
            self.stack.append(self.stack.popleft())
28
        return self.stack.popleft()
29

30
    def top(self) -> int:
31
        """
32
        Get the top element.
33
        """
34
        return self.stack[-1]
35

36
    def empty(self) -> bool:
37
        """
38
        Returns whether the stack is empty.
39
        """
40
        return len(self.stack) == 0
41

42

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

1
>>> from collections import deque
2
>>> d = deque('ghi')                 # make a new deque with three items
3
>>> for elem in d:                   # iterate over the deque's elements
4
...     print(elem.upper())
5
G
6
H
7
I
8

9
>>> d.append('j')                    # add a new entry to the right side
10
>>> d.appendleft('f')                # add a new entry to the left side
11
>>> d                                # show the representation of the deque
12
deque(['f', 'g', 'h', 'i', 'j'])
13

14
>>> d.pop()                          # return and remove the rightmost item
15
'j'
16
>>> d.popleft()                      # return and remove the leftmost item
17
'f'
18
>>> list(d)                          # list the contents of the deque
19
['g', 'h', 'i']
20
>>> d[0]                             # peek at leftmost item
21
'g'
22
>>> d[-1]                            # peek at rightmost item
23
'i'