Implement stacks with queues
LeetCode225 implements stack operations in the form of queues, FIFO FIFO mode, and FILO FIFO mode.
Simple ideas
PUSH: Use a tag to mark the top of the stack. Enqueue the top of the stack each time.
POP: The POP operation removes the top element, and the dequeue can only remove the bottom element. The loop removes the element from the head of the queue and rejoins it to the end of the queue, keeping the penultimate element at the top of the stack and removing the first element from the queue.
PEEK: Returns the tag element directly
Post code
class MyStack {
Queue<Integer> q;
int top_ele;
/** Initialize your data structure here. */
public MyStack(a) {
q = new LinkedList<>();
top_ele = 0;
}
/** Push element x onto stack. */
public void push(int x) {
q.offer(x);
top_ele = x;
}
/** Removes the element on top of the stack and returns that element. */
public int pop(a) {
int size = q.size();
while (size > 2) {
q.offer(q.poll());
size --;
}
top_ele = q.poll();
q.offer(top_ele);
return q.poll();
}
/** Get the top element. */
public int top(a) {
return top_ele;
}
/** Returns whether the stack is empty. */
public boolean empty(a) {
returnq.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(); * /
Copy the code