Implement Stack Using Queue in DSA Java - Build from Scratch

Implement Stack Using Queue

📖 Scenario: Imagine you are building a simple text editor that needs to keep track of the last few actions a user performed. You want to use a stack to store these actions so you can undo them in reverse order. However, you only have a queue data structure available. Let's learn how to build a stack using a queue.

🎯 Goal: Build a stack using a single queue in Java. You will create the queue, add a helper variable, implement the push method to add elements like a stack, and finally print the stack's content after some operations.

📋 What You'll Learn

Create a queue of integers called queue using LinkedList

Create an integer variable called size to track the number of elements

Implement the push method to add elements to the stack using the queue

Print the queue content after pushing elements to show the stack order

💡 Why This Matters

🌍 Real World

Stacks are used in undo features, expression evaluation, and backtracking algorithms. Sometimes you only have queues available, so knowing how to build a stack from a queue is useful.

💼 Career

Understanding how to implement one data structure using another shows problem-solving skills and deep understanding of data structures, which is valuable in coding interviews and software development.

1

Create the queue

Create a queue of integers called queue using LinkedList<Integer>().

DSA Java

// Your code here

Hint

Use Queue<Integer> queue = new LinkedList<>(); to create the queue.

2

Add size variable

Add an integer variable called size and set it to 0 to track the number of elements in the stack.

DSA Java

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

public class StackUsingQueue {
    public static void main(String[] args) {
        Queue queue = new LinkedList();
        // Your code here
    }
}

Hint

Declare int size = 0; inside the main method.

3

Implement push method

Implement a push method inside the main method that takes an integer x, adds it to queue, then rotates the queue to keep the newest element at the front. Also, increase size by 1. Use a for loop with variable i to rotate the queue.

DSA Java

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

public class StackUsingQueue {
    public static void main(String[] args) {
        Queue queue = new LinkedList();
        int size = 0;
        // Implement push method below
    }
}

Hint

Use queue.add(x); then rotate the queue with a for loop and queue.add(queue.remove());. Finally, increment size.

4

Print stack content after pushes

Use the push method to add 10, 20, and 30 to the stack. Then print the queue to show the stack order.

DSA Java

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

public class StackUsingQueue {
    public static void main(String[] args) {
        Queue queue = new LinkedList();
        int size = 0;

        // push method implementation
        java.util.function.Consumer push = x -> {
            queue.add(x);
            for (int i = 0; i < size; i++) {
                queue.add(queue.remove());
            }
            size++;
        };

        // Use push to add 10, 20, 30 and print queue
        // Your code here
    }
}

Hint

Call push.accept(10);, push.accept(20);, and push.accept(30); then print queue.

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