使用栈来实现队列(leetcode)

最新推荐文章于 2025-03-25 09:17:27 发布

go_flush

最新推荐文章于 2025-03-25 09:17:27 发布

阅读量172

点赞数

分类专栏：算法 python

本文链接：https://blog.csdn.net/weixin_44224529/article/details/117657108

版权

python 同时被 2 个专栏收录

185 篇文章

订阅专栏

算法

97 篇文章

订阅专栏

这篇博客探讨了一种使用两个栈来模拟队列数据结构的方法。通过栈的先进后出特性，实现了队列的先进先出功能。在push操作时，元素入栈1；在pop和peek操作时，若栈2为空，则将栈1的所有元素依次入栈2，然后返回栈2的顶部元素，从而保证了队列的正确操作。这个实现有效地利用了栈的特性，简化了队列的管理。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

使用两个栈来实现队列。

栈

先进后出

队列

先进先出

思路

利用两个栈逆序两次，就可以达到队列的效果,取值时，保证第一个栈为空，第二个栈顶的元素就是最先入队列的值

代码如下

class Stack(object):

	def __init__(self):
		self.items = []
		
	def push(self,val):
		self.items.append(val)
		
	def pop(self):
		return self.items.pop()
		
	def peek(self):
		return self.items[len(self.items)-1]
		
	def isEmpty(self):
		return self.items == []
	
class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack1 = Stack()
        self.stack2 = Stack()

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.stack1.push(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if not self.stack2.isEmpty():
        	return self.stack2.pop()
        while not self.stack1.isEmpty():
        	self.stack2.push(self.stack1.pop())
        return self.stack2.pop() # 拿到最前面的值

    def peek(self) -> int:
        """
        Get the front element.
        """
        if not self.stack2.isEmpty():
        	return self.stack2.peek()
        while not self.stack1.isEmpty():
        	self.stack2.push(self.stack1.pop())
        return self.stack2.peek()
        
    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        rerurm self.stack1.isEmpty() and self.stack2.isEmpty()