[Lintcode] 40. Implement Queue by Two Stacks/[Leetcode]225. Implement Stack using Queues

本文主要是介绍[Lintcode] 40. Implement Queue by Two Stacks/[Leetcode]225. Implement Stack using Queues，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

40. Implement Queue by Two Stacks / 225. Implement Stack using Queues

本题难度: Medium/Easy
Topic: Data Structure - stack/queue

Description

As the title described, you should only use two stacks to implement a queue’s actions.

The queue should support push(element), pop() and top() where pop is pop the first(a.k.a front) element in the queue.

Both pop and top methods should return the value of first element.

Example
Example 1:

Input:
push(1)
pop()
push(2)
push(3)
top()
pop()
Output:
1
2
2

Example 2:

Input:
push(1)
push(2)
push(2)
push(3)
push(4)
push(5)
push(6)
push(7)
push(1)
Output:
[]

Challenge
implement it by two stacks, do not use any other data structure and push, pop and top should be O(1) by AVERAGE.

我的代码

class MyQueue:def __init__(self):"""Initialize your data structure here."""self.stack1 = []self.stack2 = []def push(self, x: 'int') -> 'None':"""Push element x to the back of queue."""while(len(self.stack1)>0):self.stack2.append(self.stack1.pop())self.stack1.append(x)while(len(self.stack2)>0):self.stack1.append(self.stack2.pop())return def pop(self) -> 'int':"""Removes the element from in front of queue and returns that element."""return self.stack1.pop()def peek(self) -> 'int':"""Get the front element."""return self.stack1[-1]def empty(self) -> 'bool':"""Returns whether the queue is empty."""return self.stack1 == []# 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()

思路
example:

push 2list1 [2]
list2 []push 3
list1[2]       ->   list1 [3]   ->      list1 [3,2]
list2[]        ->   list2 [2]   ->      list2 []push 4
list1 [3,2]    -> list1[4]      ->      list1[4,3,2]
list2 []       -> lst2[2,3]     ->      list2[]