双栈实现队列练习题

发表于 | 分类于 |

任务描述：编写一个类，只能用两个栈结构实现队列，支持队列的基本操作（push,pop)。给定一个操作序列ope以及它的长度n,其中元素为正数代表push操作，为0代表pop操作，保证操作序列合法且一定含pop操作，请返回pop的结果序列。

输入：[1,2,3,0,4,0],6
返回：[1,2]

思路：push时正常的将元素push到第一个栈之中，当需要pop的时候，将第一个栈中的元素通通倒入第二个栈之中，此时第二个栈就与开始时第一个栈中元素顺序相反，然后对第二个栈进行pop操作，便实现了队列。

Python实现

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 TwoStack:
    def __init__(self):
        self.push_stack = []
        self.pop_stack = []

    def push(self, item):
        self.push_stack.append(item)

    def pop(self):
        for i in self.push_stack[::-1]:
            self.pop_stack.append(i)
        output = self.pop_stack.pop()
        self.push_stack = self.pop_stack[::-1]
        self.pop_stack = []
        return output

    def twoStack(self, ope, n):
        # write code here
        res = []
        for i in ope:
            if i > 0:
                self.push(i)
            elif i == 0:
                res.append(self.pop())
        return res