- Implement Stack using Queues
简单
https://leetcode-cn.com/problems/implement-stack-using-queues/
Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).
Implement the MyStack class:
void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top of the stack and returns it.
int top() Returns the element on the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise.
Notes:
You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.
Example 1:
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False
Constraints:
1 <= x <= 9
At most 100 calls will be made to push, pop, top, and empty.
All the calls to pop and top are valid.
Follow-up:
Can you implement the stack using only one queue?
相关企业
- 字节跳动|3
相关标签
- Stack
- Design
- Queue
相似题目
- Implement Queue using Stacks 简单
- 1 Class Stack
- 2 Class ArrayList
- 3 Interface Deque (Class ArrayDeque)
- 4 Implement Stack Using Queue (use 1 queue)
- 5 python - use class queue.LifoQueue()
- 6 python - use module collections class deque
- 7 python - Implement Stack Using Queue (use class queue.Queue())
class MyStack {
private Stack<Integer> elements;
public MyStack() {
this.elements = new Stack<Integer>();
}
public void push(int x) {
this.elements.push(x);
}
public int pop() {
return this.elements.pop();
}
public int top() {
return this.elements.peek();
}
public boolean empty() {
return this.elements.empty();
}
}
/**
* 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();
*/class MyStack {
private List<Integer> elements;
public MyStack() {
this.elements = new ArrayList<Integer>();
}
public void push(int x) {
this.elements.add(x);
}
public int pop() {
int lastIndex = this.elements.size() - 1;
int lastEle = this.elements.get(lastIndex);
this.elements.remove(lastIndex);
return lastEle;
}
public int top() {
int lastIndex = this.elements.size() - 1;
return this.elements.get(lastIndex);
}
public boolean empty() {
return this.elements.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();
*/class MyStack {
Deque<Integer> elements;
public MyStack() {
this.elements = new ArrayDeque<Integer>();
}
public void push(int x) {
this.elements.push(x);
}
public int pop() {
return this.elements.pop();
}
public int top() {
return this.elements.peek();
}
public boolean empty() {
return this.elements.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();
*/class MyStack {
Queue<Integer> queue; // use as a queue
public MyStack() {
this.queue = new ArrayDeque<Integer>();
}
public void push(int x) {
int oldLeng = this.queue.size();
this.queue.offer(x);
for (int i = 0; i < oldLeng; i++){
this.queue.offer(this.queue.poll()); // make x to be the top
}
}
public int pop() {
return this.queue.poll();
}
public int top() {
return this.queue.peek();
}
public boolean empty() {
return this.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();
*/import queue
class MyStack:
def __init__(self):
self.mystack = queue.LifoQueue()
def push(self, x: int) -> None:
self.mystack.put(x)
def pop(self) -> int:
return self.mystack.get()
def top(self) -> int:
topelem = self.mystack.get()
self.mystack.put(topelem)
for _ in range(self.mystack.qsize() - 1):
self.mystack.put(self.mystack.get())
return topelem
def empty(self) -> bool:
return self.mystack.empty()
# 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()from collections import deque
class MyStack:
def __init__(self):
self.mystack = deque() # left as top
def push(self, x: int) -> None:
self.mystack.appendleft(x)
def pop(self) -> int:
return self.mystack.popleft()
def top(self) -> int:
return list(self.mystack)[0]
# both work
def top(self) -> int:
if self.mystack:
return self.mystack[0]
return -1
def empty(self) -> bool:
return len(self.mystack) == 0
# 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()import queue
class MyStack:
def __init__(self):
self.myqueue = queue.Queue()
def push(self, x: int) -> None:
self.myqueue.put(x)
for _ in range(self.myqueue.qsize() - 1):
self.myqueue.put(self.myqueue.get())
def pop(self) -> int:
return self.myqueue.get()
def top(self) -> int:
topelem = self.myqueue.get()
self.myqueue.put(topelem)
for _ in range(self.myqueue.qsize() - 1):
self.myqueue.put(self.myqueue.get())
return topelem
def empty(self) -> bool:
return self.myqueue.empty()
# 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()
```py