LearnFrenzy
Sign in Take a free test

Data Structures in Java · Data Structures in Java Programs · Question 2

Queue implemented with two stacks in Java Solution, output & explanation

  • Program
  • Medium
  • 0 comments
  • Answer explained
  • Moderated community
Question 2 Back to Exercise

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).

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!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links