[剑指Offer]用两个栈实现队列
程序员文章站
2022-07-10 10:26:21
...
本文首发于我的个人博客Suixin’s Blog
原文: https://suixinblog.cn/2019/03/target-offer-queue-from-two-stacks.html 作者: Suixin
题目描述
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
解题思路
可以使用两个栈来存储队列,一个stack1用来正序存储该队列(这个栈的栈底为队首),方便从队尾入队操作,另一个stack2用来逆序存储该队列(这个栈的栈底为队尾),方便从队首出队操作。入队时,将stack2的元素逐渐转移到stack1,并入栈该元素;出队时,将stack1的元素逐渐转移到stack2,并出栈一个元素。
代码
Python(2.7.3)
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack1=[]
self.stack2=[]
def push(self, node):
# write code here
while self.stack2:
tmp = self.stack2.pop()
self.stack1.append(tmp)
self.stack1.append(node)
def pop(self):
# return xx
while self.stack1:
tmp = self.stack1.pop()
self.stack2.append(tmp)
return self.stack2.pop()
运行时间:28ms
占用内存:5856k
实际上,上面的方法浪费了一部分计算资源,可以把队列分成两段来存储,见https://www.nowcoder.com/profile/4991846/codeBookDetail?submissionId=9811452