当前位置：首页 > article >正文

【代码随想录】刷题记录(29)-用栈实现队列

article 2024/11/15 11:31:41

题目描述：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

我的作答：

这道题看得我好懵，特别是对没有接触过栈和队列概念的人来说。。。

class MyQueue(object):

    def __init__(self):
        self.stack_in = [] #进栈的列表
        self.stack_out = [] #用于出栈的列表

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.stack_in.append(x) #push进in列表，用于储存本来的顺序

    def pop(self):
        """
        :rtype: int
        """
        if self.empty():
            return None
        if self.stack_out: #如果out列表有元素，就把它弹出去就行了（就是队列顺序）
            return self.stack_out.pop()
        else:
            for i in range(len(self.stack_in)):#如果out没有元素，则先把in里的元素搬过去
                self.stack_out.append(self.stack_in.pop())
            return self.stack_out.pop()

    def peek(self):
        """
        :rtype: int
        """
        temp = self.pop() 
        self.stack_out.append(temp)#因为self.pop()移除了栈顶，所以再添加回来
        return temp

    def empty(self):
        """
        :rtype: bool
        """
        return not(self.stack_in or self.stack_out)


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

思路其实很简单，有点像那种小学益智游戏，比如那种给两个箱子，花几步把最下面的砖块搬出来的游戏。这道题其实就是类似这种动作，因为栈是遵循“先入后出”的原则，所以如果要拿出最先入栈stack_in的元素（也就是栈底元素），就先要另一个箱子放置储存它上面的砖块，而这个箱子就是stack_out，随着它上面的砖块一个一个又被堆到out箱子里，in最下面的砖块入out箱子时已经在最上面，这个时候，我们用pop（）弹出out箱子，pop()默认弹出最上面的砖块，就实现了in里最先入栈元素的弹出；