225. 用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
push to back、peek/pop from front、size 和 is empty 这些操作。
示例：
输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false] 解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False
提示：
1 <= x <= 9100 次 push、pop、top 和 emptypop 和 top 都保证栈不为空
进阶：你能否仅用一个队列来实现栈。
相似题目
原站题解
javascript 解法, 执行用时: 44 ms, 内存消耗: 49 MB, 提交时间: 2024-03-03 11:55:44
var MyStack = function() {
this.queue = [];
this._queue = [];
};
/**
* @param {number} x
* @return {void}
*/
MyStack.prototype.push = function(x) {
this.queue.push(x);
};
/**
* @return {number}
*/
MyStack.prototype.pop = function() {
while(this.queue.length > 1){
this._queue.push(this.queue.shift());
}
let ans = this.queue.shift();
while(this._queue.length){
this.queue.push(this._queue.shift());
}
return ans;
};
/**
* @return {number}
*/
MyStack.prototype.top = function() {
return this.queue.slice(-1)[0];
};
/**
* @return {boolean}
*/
MyStack.prototype.empty = function() {
return !this.queue.length;
};
/**
* Your MyStack object will be instantiated and called as such:
* var obj = new MyStack()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.empty()
*/
rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-09-15 15:03:28
struct MyStack {
q1: VecDeque<i32>,
q2: VecDeque<i32>,
out1: bool,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
use std::collections::VecDeque;
impl MyStack {
fn new() -> Self {
Self {
q1: VecDeque::new(),
q2: VecDeque::new(),
out1: false,
}
}
fn push(&mut self, x: i32) {
let (q1, q2) = if !self.out1 {
(&mut self.q1, &mut self.q2)
} else {
(&mut self.q2, &mut self.q1)
};
q1.push_back(x);
while let Some(val) = q2.pop_front() {
q1.push_back(val);
}
self.out1 = !self.out1;
}
fn pop(&mut self) -> i32 {
if self.out1 {
self.q1.pop_front().unwrap()
} else {
self.q2.pop_front().unwrap()
}
}
fn top(&mut self) -> i32 {
if self.out1 {
*self.q1.front().unwrap()
} else {
*self.q2.front().unwrap()
}
}
fn empty(&self) -> bool {
self.q1.is_empty() && self.q2.is_empty()
}
}
/**
* Your MyStack object will be instantiated and called as such:
* let obj = MyStack::new();
* obj.push(x);
* let ret_2: i32 = obj.pop();
* let ret_3: i32 = obj.top();
* let ret_4: bool = obj.empty();
*/
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-15 15:01:26
type MyStack struct {
queue []int
}
/** Initialize your data structure here. */
func Constructor() (s MyStack) {
return
}
/** Push element x onto stack. */
func (s *MyStack) Push(x int) {
n := len(s.queue)
s.queue = append(s.queue, x)
for ; n > 0; n-- {
s.queue = append(s.queue, s.queue[0])
s.queue = s.queue[1:]
}
}
/** Removes the element on top of the stack and returns that element. */
func (s *MyStack) Pop() int {
v := s.queue[0]
s.queue = s.queue[1:]
return v
}
/** Get the top element. */
func (s *MyStack) Top() int {
return s.queue[0]
}
/** Returns whether the stack is empty. */
func (s *MyStack) Empty() bool {
return len(s.queue) == 0
}
/**
* Your MyStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(x);
* param_2 := obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.Empty();
*/
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-15 15:01:08
type MyStack struct {
queue1, queue2 []int
}
/** Initialize your data structure here. */
func Constructor() (s MyStack) {
return
}
/** Push element x onto stack. */
func (s *MyStack) Push(x int) {
s.queue2 = append(s.queue2, x)
for len(s.queue1) > 0 {
s.queue2 = append(s.queue2, s.queue1[0])
s.queue1 = s.queue1[1:]
}
s.queue1, s.queue2 = s.queue2, s.queue1
}
/** Removes the element on top of the stack and returns that element. */
func (s *MyStack) Pop() int {
v := s.queue1[0]
s.queue1 = s.queue1[1:]
return v
}
/** Get the top element. */
func (s *MyStack) Top() int {
return s.queue1[0]
}
/** Returns whether the stack is empty. */
func (s *MyStack) Empty() bool {
return len(s.queue1) == 0
}
/**
* Your MyStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(x);
* param_2 := obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.Empty();
*/
python3 解法, 执行用时: 40 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-15 15:00:37
class 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.
"""
self.queue2.append(x)
while self.queue1:
self.queue2.append(self.queue1.popleft())
self.queue1, self.queue2 = self.queue2, self.queue1
def 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 not 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()
# param_4 = obj.empty()
python3 解法, 执行用时: 40 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-15 15:00:18
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.queue = collections.deque()
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
n = len(self.queue)
self.queue.append(x)
for _ in range(n):
self.queue.append(self.queue.popleft())
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
return self.queue.popleft()
def top(self) -> int:
"""
Get the top element.
"""
return self.queue[0]
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return not self.queue
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
java 解法, 执行用时: 0 ms, 内存消耗: 39.1 MB, 提交时间: 2023-09-15 14:59:54
class MyStack {
Queue<Integer> queue;
/** Initialize your data structure here. */
public MyStack() {
queue = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
int n = queue.size();
queue.offer(x);
for (int i = 0; i < n; i++) {
queue.offer(queue.poll());
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.poll();
}
/** Get the top element. */
public int top() {
return queue.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
java 解法, 执行用时: 0 ms, 内存消耗: 39.4 MB, 提交时间: 2023-09-15 14:59:32
// 两个队列
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
/** Initialize your data structure here. */
public MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
queue2.offer(x);
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue1.poll();
}
/** Get the top element. */
public int top() {
return queue1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
php 解法, 执行用时: 4 ms, 内存消耗: 15.2 MB, 提交时间: 2021-05-25 11:44:15
class MyStack {
/**
* Initialize your data structure here.
*/
function __construct() {
$this->stack = [];
}
/**
* Push element x onto stack.
* @param Integer $x
* @return NULL
*/
function push($x) {
array_unshift($this->stack, $x);
}
/**
* Removes the element on top of the stack and returns that element.
* @return Integer
*/
function pop() {
return array_shift($this->stack);
}
/**
* Get the top element.
* @return Integer
*/
function top() {
return current($this->stack);
}
/**
* Returns whether the stack is empty.
* @return Boolean
*/
function empty() {
return empty($this->stack);
}
}
/**
* Your MyStack object will be instantiated and called as such:
* $obj = MyStack();
* $obj->push($x);
* $ret_2 = $obj->pop();
* $ret_3 = $obj->top();
* $ret_4 = $obj->empty();
*/