Build a FIFO queue from two stacks: push into an "in" stack and, only when the "out" stack is empty, move everything across. Count how many element moves happen.
Solution
Main.java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Main {
static class TwoStackQueue<T> {
private final Deque<T> in = new ArrayDeque<>();
private final Deque<T> out = new ArrayDeque<>();
private int moves;
void enqueue(T x) { in.push(x); }
T dequeue() { shift(); return out.pop(); }
T peek() { shift(); return out.peek(); }
int size() { return in.size() + out.size(); }
private void shift() { // reverse "in" into "out" only when "out" is empty
if (out.isEmpty())
while (!in.isEmpty()) { out.push(in.pop()); moves++; }
}
}
public static void main(String[] args) {
TwoStackQueue<Integer> q = new TwoStackQueue<>();
for (int i = 1; i <= 3; i++) q.enqueue(i);
System.out.println("first out: " + q.dequeue());
q.enqueue(4);
q.enqueue(5);
System.out.println("front now: " + q.peek());
List<Integer> rest = new ArrayList<>();
while (q.size() > 0) rest.add(q.dequeue());
System.out.println("rest: " + rest + ", element moves: " + q.moves);
}
}
Output Verified by compiling and running
first out: 1
front now: 2
rest: [2, 3, 4, 5], element moves: 5
1, 2, 3 move across once; 4 and 5 move only after 2 and 3 have left. Every element moves exactly once, so each operation is amortized O(1).
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!
We use Google Analytics cookies to see how LearnFrenzy is used and make it better, and Google AdSense to keep it free.
No analytics or ad cookies are set until you accept. Privacy Policy
·
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!