Implement Stack using Queues - Leetcode Java | Welkin Lan

Implement Stack using Queues – Leetcode Java | Welkin Lan

Q: push(x) — Push element x onto stack. pop() — Removes the element on top of the stack. top() — Get the top element. empty() — Return whether the stack is empty. A: Use 2 queues and an extra queue to mark which one to pop class MyStack { LinkedList q1 = new LinkedList(); LinkedList q2 = new LinkedList(); LinkedList toPop = null; // Push element x onto stack. public void push(int x) { if (toPop == q1) { q2.offer(q1.poll()); q1.offer(x); } else if (toPop == q2) { q1.offer(q2.poll()); q2.offer(x); } else { q1.offer(x); toPop = q1; } } // Removes the element on top of the stack. public void pop() { if (empty()) { return; } if (toPop == q1) { q1.poll(); transit(q2, q1); toPop = q2; } else { q2.poll();

Read full article from Implement Stack using Queues – Leetcode Java | Welkin Lan