CodingGyan

Queue Using Two Stacks

medium Data Structures and Algorithms

Problem

Build a queue (first in, first out) using only stack operations. Commands: enqueue X, dequeue and front. enqueue prints ok. dequeue prints the removed value and front prints the oldest value. If the queue is empty, dequeue and front print empty.

Constraints

  • 1 <= commands <= 10^5

Examples

Input

enqueue 1
enqueue 2
front
dequeue

Output

ok
ok
1
1

Solutions

Best approachTime O(1) amortizedSpace O(n)

Moving values from the input stack to the output stack reverses them, so the oldest value comes out first. Each value moves at most once, so the average cost is O(1) per command.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process commands line by line.
 * Input   : Several lines of commands.
 * Output  : One result line per command.
 * Approach: Two stacks.
 * Time    : O(1) amortized
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: A queue is first in, first out. We build it from two stacks. Stack "in" receives new values.
        static class TwoStackQueue {
            private final java.util.ArrayDeque<Long> in = new java.util.ArrayDeque<>();
            private final java.util.ArrayDeque<Long> out = new java.util.ArrayDeque<>();

            void enqueue(long value) {
                in.push(value);
            }

            // Step 2: Only when "out" is empty, move all values from "in". This reverses their order, so the oldest value is on top.
            private void shift() {
                if (out.isEmpty()) {
                    while (!in.isEmpty()) {
                        out.push(in.pop());
                    }
                }
            }

            long dequeue() {
                shift();
                return out.pop();
            }

            long front() {
                shift();
                return out.peek();
            }

            boolean isEmpty() {
                return in.isEmpty() && out.isEmpty();
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        TwoStackQueue queue = new TwoStackQueue();
        String[] output = new String[lines.length];
        for (int i = 0; i < lines.length; i++) {
            String[] parts = lines[i].split(" ");

            // Step 3: Run the command. Enqueue always works. The other commands need a non-empty queue.
            if (parts[0].equals("enqueue")) {
                queue.enqueue(Long.parseLong(parts[1]));
                output[i] = "ok";
            } else if (queue.isEmpty()) {
                output[i] = "empty";
            } else if (parts[0].equals("dequeue")) {
                output[i] = String.valueOf(queue.dequeue());
            } else {
                output[i] = String.valueOf(queue.front());
            }
        }
        return output;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(String.join("\n", solve(lines)));
    }
}
Hints (1)
  1. When should you move values to the output stack?

Try these next