Implement Stack Using Queue in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of push and pop operations in stack implemented using one queue

What is the printed output after performing the following operations on a stack implemented using a single queue?

Operations:
push(10), push(20), push(30), pop(), push(40), pop()

DSA Java

class StackUsingQueue {
    private java.util.Queue<Integer> queue = new java.util.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 String printStack() {
        return queue.toString();
    }
}

public class Main {
    public static void main(String[] args) {
        StackUsingQueue stack = new StackUsingQueue();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.print(stack.pop() + ", ");
        stack.push(40);
        System.out.print(stack.pop());
    }
}

A 10, 20

B 30, 40

C 20, 30

D 40, 30

💡 Hint

Remember that push operation rotates the queue to keep the last pushed element at the front.

The push method rotates the queue so the newest element is always at the front. So pop removes the last pushed element. After pushing 10, 20, 30, the queue front is 30. pop() removes 30. Then push(40) makes 40 front. pop() removes 40. So output is '30, 40'.

❓ Predict Output

intermediate

Final queue state after multiple push and pop operations

Given a stack implemented using a single queue with the push method rotating the queue, what is the final state of the queue after these operations?

push(1), push(2), pop(), push(3), push(4), pop(), push(5)

DSA Java

class StackUsingQueue {
    private java.util.Queue<Integer> queue = new java.util.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 String printQueue() {
        return queue.toString();
    }
}

public class Main {
    public static void main(String[] args) {
        StackUsingQueue stack = new StackUsingQueue();
        stack.push(1);
        stack.push(2);
        stack.pop();
        stack.push(3);
        stack.push(4);
        stack.pop();
        stack.push(5);
        System.out.print(stack.printQueue());
    }
}

A [3, 1, 5]

B [1, 3, 5]

C [5, 3, 1]

D [5, 4, 3]

💡 Hint

Track the queue after each push and pop carefully, remembering push rotates the queue.

After push(1) queue=[1]. push(2) rotates queue to [2,1]. pop() removes 2, queue=[1]. push(3) rotates queue to [3,1]. push(4) rotates queue to [4,3,1]. pop() removes 4, queue=[3,1]. push(5) rotates queue to [5,3,1].

🔧 Debug

advanced

Identify the error in stack pop method using two queues

Consider this stack implementation using two queues. What error will occur when calling pop() if the queues are empty?

DSA Java

class StackUsingTwoQueues {
    private java.util.Queue<Integer> q1 = new java.util.LinkedList<>();
    private java.util.Queue<Integer> q2 = new java.util.LinkedList<>();

    public void push(int x) {
        q2.add(x);
        while (!q1.isEmpty()) {
            q2.add(q1.remove());
        }
        java.util.Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }

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

A NoSuchElementException

B NullPointerException

C IllegalStateException

D ClassCastException

💡 Hint

What happens if you call remove() on an empty queue in Java?

Calling remove() on an empty Java queue throws NoSuchElementException because there is no element to remove.

🧠 Conceptual

advanced

Time complexity of push and pop in stack using one queue

What are the time complexities of push and pop operations in a stack implemented using a single queue where push rotates the queue to keep the last pushed element at front?

A push: O(n), pop: O(1)

B push: O(1), pop: O(n)

C push: O(n), pop: O(n)

D push: O(1), pop: O(1)

💡 Hint

Consider how many elements are moved during push and pop.

Push adds element then rotates all other elements to the back, taking O(n). Pop just removes front element, O(1).

🚀 Application

expert

Implement stack with two queues: which operation is costly?

In a stack implemented using two queues, if push operation adds element to the empty queue and then moves all elements from the other queue, which operation is costly and why?

A Neither push nor pop is costly; both are O(1).

B Pop is costly because it removes elements one by one.

C Both push and pop are equally costly due to queue operations.

D Push is costly because it moves all elements to maintain stack order.

💡 Hint

Think about which operation involves moving many elements between queues.

Push moves all elements from one queue to another to keep newest element at front, making push costly O(n). Pop just removes front element O(1).

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