Implement Queue using Stacks（用两个栈实现队列）
2024-09-05 21:25:36
来源：https://leetcode.com/problems/implement-queue-using-stacks
Implement the following operations of a queue using stacks.
- push(x) -- Push element x to the back of queue.
- pop() -- Removes the element from in front of queue.
- peek() -- Get the front element.
- empty() -- Return whether the queue is empty.
Notes:
- You must use only standard operations of a stack -- which means only
push to top,peek/pop from top,size, andis emptyoperations are valid. - Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
- You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
栈A负责push，栈B负责pop和peek，当pop或peek时，如果栈B没有元素，就将栈A中的内容按栈的pop顺序push到栈B中
Java
class MyQueue {
Stack<Integer> input;
Stack<Integer> output;
/** Initialize your data structure here. */
public MyQueue() {
input = new Stack<Integer>();
output = new Stack<Integer>();
}
/** Push element x to the back of queue. */
public void push(int x) {
input.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
peek();
return output.pop();
}
/** Get the front element. */
public int peek() {
if(output.empty()) {
int len = input.size();
for(int i=0; i<len; i++) {
output.push(input.pop());
}
}
return output.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return input.empty() && output.empty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
Python
class MyQueue(object):
i_stack = []
o_stack = []
def __init__(self):
"""
Initialize your data structure here.
"""
self.i_stack = []
self.o_stack = [] def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: void
"""
self.i_stack.append(x) def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
self.peek()
return self.o_stack.pop() def peek(self):
"""
Get the front element.
:rtype: int
"""
if len(self.o_stack) == 0:
i_len = len(self.i_stack)
for i in range(i_len):
self.o_stack.append(self.i_stack.pop())
return self.o_stack[-1] def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
return len(self.i_stack) == 0 and len(self.o_stack) == 0 # 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()
最新文章
- iOS的nil，Null，NSNull的使用
- ionic实现手机检测app是否安装，未安装则下载安装包，已安装则打开app（未实现iOS平台）
- zookeeper节点数与watch的性能测试
- MVC3远程验证
- hadoop2.5.2学习及实践笔记（二）—— 编译源代码及导入源码至eclipse
- Java基础知识强化之网络编程笔记15：Android网络通信之 Android异步任务处理（AsyncTask使用）
- php 随机显示据今天30天内的任意一天
- 字符串查找--B中是否有元素不在A中
- lcc之内存分配
- hdu_5036_Explosion(bitset优化传递闭包)
- 剖析Asp.Net Web API中HttpController的激活
- Linux性能及调优指南（翻译）之Linux进程管理
- 网易im即时通讯 移动端嵌入web
- 离线安装Eclipse插件-Vrapper
- #2 安装Python
- Gulp实现静态网页模块化的方法详解
- 6-14 Abbott的复仇 uva816
- Ubuntu终端多窗口分屏Terminator
- XML与HTML区别
- android之滑屏的实现