Implement Stack Using Queue in DSA Java - Time & Space Complexity

Time Complexity: Implement Stack Using Queue

O(n)

Understanding Time Complexity

We want to understand how long it takes to use a queue to act like a stack.

Specifically, how the time grows when we add or remove items.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import java.util.LinkedList;
import java.util.Queue;

public class StackUsingQueue {
    private Queue<Integer> queue = new LinkedList<>();

    public void push(int x) {
        queue.add(x);
        int size = queue.size();
        while (size > 1) {
            queue.add(queue.remove());
            size--;
        }
    }

    public int pop() {
        return queue.remove();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

This code uses one queue to simulate stack behavior by rotating elements on push.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop inside the push method that moves elements.
• How many times: It runs once for each element already in the queue before the new one.

How Execution Grows With Input

Each push moves all existing elements to the back of the queue to keep the newest on front.

Input Size (n)	Approx. Operations in push
10	About 9 moves
100	About 99 moves
1000	About 999 moves

Pattern observation: The number of moves grows directly with the number of items already in the queue.

Final Time Complexity

Time Complexity: O(n)

This means pushing an item takes longer as the stack grows, roughly proportional to the number of items.

Common Mistake

[X] Wrong: "Push operation is always fast because it just adds one item."

[OK] Correct: Because push moves all existing items to keep stack order, it takes time proportional to the current size.

Interview Connect

Understanding how to use one data structure to mimic another shows your problem-solving skills and grasp of time costs.

Self-Check

"What if we used two queues instead of one? How would that change the time complexity of push and pop?"

Practice

1. What is the main idea behind implementing a stack using a queue?

easy

A. Use one queue and reorder elements to simulate stack behavior

B. Use two stacks to simulate a queue

C. Use a linked list to implement both stack and queue

D. Use an array to simulate queue operations

Solution

1. Step 1: Understand stack and queue behaviors

   A stack follows Last-In-First-Out (LIFO), while a queue follows First-In-First-Out (FIFO).

2. Step 2: Simulate stack using queue

   By reordering elements in a single queue after each push, we can simulate LIFO behavior of a stack.

3. Final Answer:

   Use one queue and reorder elements to simulate stack behavior -> Option A

4. Quick Check:

   Stack via queue = reorder in one queue [OK]

Hint: Remember stack is LIFO; reorder queue to mimic it [OK]

Common Mistakes:

• Confusing stack with queue behavior
• Using two stacks instead of queues
• Ignoring element order after push

2. Which of the following is the correct Java syntax to declare a queue of integers using LinkedList?

easy

A. LinkedList<Integer> queue = new Queue<>();

B. Queue<int> queue = new LinkedList<>();

C. Queue<Integer> queue = new LinkedList<>();

D. Queue<Integer> queue = new Queue<>();

Solution

1. Step 1: Use interface Queue with LinkedList implementation

   In Java, Queue is an interface and LinkedList implements it. Use generics with wrapper class Integer.

2. Step 2: Check syntax correctness

   Queue<Integer> queue = new LinkedList<>(); is correct syntax for declaring a queue of integers.

3. Final Answer:

   Queue<Integer> queue = new LinkedList<>(); -> Option C

4. Quick Check:

   Queue<Integer> with LinkedList = correct syntax [OK]

Hint: Use wrapper classes and interface for queue declaration [OK]

Common Mistakes:

• Using primitive int instead of Integer
• Trying to instantiate interface Queue directly
• Confusing LinkedList and Queue syntax

3. What will be the output of the following code snippet implementing stack push using one queue?

Queue<Integer> q = new LinkedList<>();
// Push 1
q.add(1);
// Push 2
q.add(2);
// Reorder queue to simulate stack push
for (int i = 0; i < q.size() - 1; i++) {
  q.add(q.remove());
}
System.out.println(q.remove());

medium

A. 1

B. 2

C. Queue is empty

D. Runtime error

Solution

1. Step 1: Add elements 1 and 2 to queue

   Queue after adds: front -> 1, 2 -> rear

2. Step 2: Reorder queue to simulate stack push

   Loop runs q.size()-1 = 1 time: remove 1, add 1 back. Queue becomes front -> 2, 1 -> rear

3. Step 3: Remove and print element

   q.remove() removes front element 2, which is printed.

4. Final Answer:

   2 -> Option B

5. Quick Check:

   Reordered queue front = last pushed = 2 [OK]

Hint: After push reorder, front is last pushed element [OK]

Common Mistakes:

• Not reordering queue after push
• Printing wrong element without remove
• Confusing queue front with rear

4. Identify the error in this stack pop implementation using one queue:

public int pop() {
  if (queue.isEmpty()) return -1;
  return queue.remove();
}

medium

A. No error, code works correctly

B. Queue should be cleared after pop

C. Should use queue.peek() instead of remove()

D. Pop removes the oldest element, not the last pushed

Solution

1. Step 1: Understand queue remove() behavior

   queue.remove() removes the front element, which is the oldest inserted, not the last pushed.

2. Step 2: Check stack pop requirement

   Stack pop must remove the last pushed element (LIFO), but this code removes FIFO element.

3. Final Answer:

   Pop removes the oldest element, not the last pushed -> Option D

4. Quick Check:

   Queue remove() = FIFO, stack pop = LIFO [OK]

Hint: Pop must remove last pushed, not queue front [OK]

Common Mistakes:

• Using queue.remove() directly for pop
• Ignoring element order after push
• Not reordering queue to simulate stack

5. You want to implement a stack using two queues. Which sequence of operations correctly simulates the pop() method?

hard

A. Move all but last element from queue1 to queue2, remove last from queue1, swap queues

B. Remove front element from queue1 directly

C. Add element to queue2, then remove from queue1

D. Swap queues without removing any element

Solution

1. Step 1: Understand two-queue stack pop logic

   To pop last pushed element, move all except last from queue1 to queue2, then remove last from queue1.

2. Step 2: Swap queues for next operations

   After removal, swap queue1 and queue2 references to maintain stack state.

3. Final Answer:

   Move all but last element from queue1 to queue2, remove last from queue1, swap queues -> Option A

4. Quick Check:

   Pop with two queues = move all but last, remove last, swap [OK]

Hint: Pop = move all but last, remove last, then swap queues [OK]

Common Mistakes:

• Removing front element directly
• Not swapping queues after pop
• Adding elements to wrong queue during pop