LeetCode232. 用栈实现队列🌟🌟🌟🌟🌟简单
课后作业
问题描述
原文链接：232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
说明：
- 你只能使用标准的栈操作 —— 也就是只有
push to top,peek/pop from top,size, 和is empty操作是合法的。 - 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示：
1 <= x <= 9- 最多调用
100次push、pop、peek和empty - 假设所有操作都是有效的 （例如，一个空的队列不会调用
pop或者peek操作）
代码实现
Java
class MyQueue {
Stack<Integer> stack1;
Stack<Integer> stack2;
public MyQueue() {
stack1 = new Stack();
stack2 = new Stack();
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if(!stack2.isEmpty()){
return stack2.pop();
}
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.pop();
}
public int peek() {
if(!stack2.isEmpty()){
return stack2.peek();
}
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}
/**
* 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):
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.stack1.append(x)
def pop(self):
"""
:rtype: int
"""
if self.stack2:
return self.stack2.pop()
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
def peek(self):
"""
:rtype: int
"""
if self.stack2:
return self.stack2[-1]
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2[-1]
def empty(self):
"""
:rtype: bool
"""
return not self.stack1 and not self.stack2
# 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()
C++
class MyQueue {
private:
stack<int> stack1;
stack<int> stack2;
public:
MyQueue() {
}
void push(int x) {
stack1.push(x);
}
int pop() {
if (!stack2.empty()) {
int val = stack2.top();
stack2.pop();
return val;
}
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
int val = stack2.top();
stack2.pop();
return val;
}
int peek() {
if (!stack2.empty()) {
return stack2.top();
}
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
return stack2.top();
}
bool empty() {
return stack1.empty() && stack2.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();
// bool param_4 = obj->empty();
Go
type MyQueue struct {
stack1 []int
stack2 []int
}
func Constructor() MyQueue {
return MyQueue{}
}
func (this *MyQueue) Push(x int) {
this.stack1 = append(this.stack1, x)
}
func (this *MyQueue) Pop() int {
if len(this.stack2) > 0 {
val := this.stack2[len(this.stack2)-1]
this.stack2 = this.stack2[:len(this.stack2)-1]
return val
}
for len(this.stack1) > 0 {
val := this.stack1[len(this.stack1)-1]
this.stack1 = this.stack1[:len(this.stack1)-1]
this.stack2 = append(this.stack2, val)
}
val := this.stack2[len(this.stack2)-1]
this.stack2 = this.stack2[:len(this.stack2)-1]
return val
}
func (this *MyQueue) Peek() int {
if len(this.stack2) > 0 {
return this.stack2[len(this.stack2)-1]
}
for len(this.stack1) > 0 {
val := this.stack1[len(this.stack1)-1]
this.stack1 = this.stack1[:len(this.stack1)-1]
this.stack2 = append(this.stack2, val)
}
return this.stack2[len(this.stack2)-1]
}
func (this *MyQueue) Empty() bool {
return len(this.stack1) == 0 && len(this.stack2) == 0
}
// Your MyQueue object will be instantiated and called as such:
// obj := Constructor();
// obj.Push(x);
// param_2 := obj.Pop();
// param_3 := obj.Peek();
// param_4 := obj.Empty();