[Leetcode]225. Implement Stack using Queues

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

225. Implement Stack using Queues

Implement the following operations of a stack using queues.

push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
empty() – Return whether the stack is empty.
Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);
stack.top(); // returns 2
stack.pop(); // returns 2
stack.empty(); // returns false
Notes:

You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

• 本题难度: Easy
• Topic: Data Structure

Description

我的代码

import collectionsclass MyStack:def __init__(self):"""Initialize your data structure here."""self.queue1 = collections.deque([])self.queue2 = collections.deque([])def push(self, x: 'int') -> 'None':"""Push element x onto stack."""while(not self.empty(self.queue1)):self.queue2.append(self.queue1.popleft())self.queue1.append(x)while(not self.empty(self.queue2)):self.queue1.append(self.queue2.popleft())returndef pop(self) -> 'int':"""Removes the element on top of the stack and returns that element."""return self.queue1.popleft()def top(self) -> 'int':"""Get the top element."""return self.queue1[0]def empty(self) -> 'bool':"""Returns whether the stack is empty."""return self.queue1 == []# Your MyStack object will be instantiated and called as such:# obj = MyStack()# obj.push(x)# param_2 = obj.pop()# param_3 = obj.top()

思路

push 1
q1 [1]
q2 []push 2
q1 [2]   -> q1 [2, 1]
q2 [1]   -> q2 []push 3
q1 [3]   -> q1 [3, 2, 1]
q2 [2,1]   -> q2 []

• 时间复杂度 push O(n) others O(1)

这篇关于[Leetcode]225. Implement Stack using Queues的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---