232.用栈实现队列

链接 代码随想录 思路：重点是模拟出队列行为，需要两个栈，statck_in负责push, stack_out负责pop

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class MyQueue:

    def __init__(self):
        """in负责push，out负责pop"""
        self.stack_in = []
        self.stack_out = []

    def push(self, x: int) -> None:
        self.stack_in.append(x)

    def pop(self) -> int:
        if not self.stack_out:
            while self.stack_in:
                item = self.stack_in.pop()
                self.stack_out.append(item)
             
        return self.stack_out.pop()

    def peek(self) -> int:
        res = self.pop()
        self.stack_out.append(res)
        return res

    def empty(self) -> bool:
        return not self.stack_in and not self.stack_out

时间复杂度：O(n)

225. 用队列实现栈

leetcode

代码随想录

思路：使用一个队列来模拟栈。主要是pop操作，要想获取队列最后一个元素，需要把它前面的元素都pop出去，pop size-1次。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class MyStack:

    def __init__(self):
        self.queue = []

    def push(self, x: int) -> None:
        self.queue.append(x)

    def pop(self) -> int:
        size = len(self.queue)
        while size -1 > 0:
            # pop size-1次
            item = self.queue.pop(0)
            self.push(item)
            size -= 1
        return self.queue.pop(0) 

    def top(self) -> int:
        item = self.pop()
        self.push(item)
        return item

    def empty(self) -> bool:
        return not self.queue

时间复杂度：O(n)