Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Queue Reversal

Problem Statement

Write a Java program that reverses the elements of a queue using a stack. The program should enqueue a set of numbers into a queue, reverse the order of the elements using a stack, and print the reversed queue. The reversal should maintain the queue’s FIFO (first-in, first-out) property in the final output. Test the implementation with various sets of numbers, including empty queues and single-element queues. You can visualize this as unloading a queue of items onto a stack, which flips their order, and then reloading them into a new queue to get the reversed sequence.

Input: A set of integers to enqueue (e.g., [1, 2, 3]). Output: The reversed queue as a string (e.g., "[3, 2, 1]"). Constraints:

  • Queue size is between 0 and 10^5.
  • Elements are integers in the range [-10^9, 10^9].
  • The queue may be empty. Example:
  • Input: Enqueue [1, 2, 3]
  • Output: [3, 2, 1]
  • Explanation: Enqueue 1, 2, 3; dequeue to stack (3, 2, 1 top); pop to new queue → [3, 2, 1].
  • Input: Enqueue []
  • Output: []
  • Explanation: Empty queue remains empty after reversal.

Pseudocode

CLASS IntQueue
    SET array to new integer array of size 1000
    SET front to 0
    SET rear to -1
    SET size to 0
    
    FUNCTION enqueue(number)
        IF size equals array length THEN
            RETURN false (queue full)
        ENDIF
        INCREMENT rear
        SET array[rear] to number
        INCREMENT size
        RETURN true
    ENDFUNCTION
    
    FUNCTION dequeue()
        IF size equals 0 THEN
            RETURN null (queue empty)
        ENDIF
        SET number to array[front]
        INCREMENT front
        DECREMENT size
        RETURN number
    ENDFUNCTION
    
    FUNCTION isEmpty()
        RETURN size equals 0
    ENDFUNCTION
    
    FUNCTION toString()
        CREATE result as empty string
        APPEND "["
        FOR i from front to rear
            APPEND array[i] and ", " to result
        ENDFOR
        IF result ends with ", " THEN
            REMOVE last ", "
        ENDIF
        APPEND "]" to result
        RETURN result
    ENDFUNCTION
ENDCLASS

CLASS IntStack
    SET array to new integer array of size 1000
    SET top to -1
    
    FUNCTION push(number)
        IF top equals array length - 1 THEN
            RETURN false (stack full)
        ENDIF
        INCREMENT top
        SET array[top] to number
        RETURN true
    ENDFUNCTION
    
    FUNCTION pop()
        IF top equals -1 THEN
            RETURN null (stack empty)
        ENDIF
        SET number to array[top]
        DECREMENT top
        RETURN number
    ENDFUNCTION
ENDCLASS

FUNCTION reverseQueue(queue)
    CREATE stack as new IntStack
    CREATE newQueue as new IntQueue
    WHILE queue is not empty
        SET number to queue.dequeue()
        PUSH number to stack
    ENDWHILE
    WHILE stack is not empty
        SET number to stack.pop()
        ENQUEUE number to newQueue
    ENDWHILE
    RETURN newQueue
ENDFUNCTION

FUNCTION main()
    SET testCases to array of integer arrays
    FOR each numbers in testCases
        CREATE queue as new IntQueue
        FOR each number in numbers
            ENQUEUE number to queue
        ENDFOR
        PRINT original queue
        SET reversed to reverseQueue(queue)
        PRINT reversed queue
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define an IntQueue class with: a. An array to store integers, with front, rear, and size to track queue state. b. Methods: enqueue (add to rear), dequeue (remove from front), isEmpty, toString.
  2. Define an IntStack class with: a. An array to store integers, with top index. b. Methods: push (add to top), pop (remove from top).
  3. In the reverseQueue method: a. Create a stack and a new queue. b. Dequeue all elements from the input queue and push them onto the stack. c. Pop all elements from the stack and enqueue them into the new queue. d. Return the new queue.
  4. In the main method, test with different sets of numbers, including empty and single-element queues, printing the original and reversed queues.

Java Implementation

import java.util.*;

public class QueueReversal {
    // Custom queue implementation for integers
    static class IntQueue {
        private int[] array;
        private int front;
        private int rear;
        private int size;
        private static final int DEFAULT_SIZE = 1000;

        public IntQueue() {
            array = new int[DEFAULT_SIZE];
            front = 0;
            rear = -1;
            size = 0;
        }

        public boolean enqueue(int number) {
            if (size == array.length) {
                return false; // Queue full
            }
            array[++rear] = number;
            size++;
            return true;
        }

        public Integer dequeue() {
            if (size == 0) {
                return null; // Queue empty
            }
            int number = array[front++];
            size--;
            return number;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public String toString() {
            StringBuilder result = new StringBuilder("[");
            for (int i = front; i <= rear; i++) {
                result.append(array[i]);
                if (i < rear) {
                    result.append(", ");
                }
            }
            result.append("]");
            return result.toString();
        }
    }

    // Custom stack implementation for integers
    static class IntStack {
        private int[] array;
        private int top;
        private static final int DEFAULT_SIZE = 1000;

        public IntStack() {
            array = new int[DEFAULT_SIZE];
            top = -1;
        }

        public boolean push(int number) {
            if (top == array.length - 1) {
                return false; // Stack full
            }
            array[++top] = number;
            return true;
        }

        public Integer pop() {
            if (top == -1) {
                return null; // Stack empty
            }
            return array[top--];
        }
    }

    // Reverses a queue using a stack
    public IntQueue reverseQueue(IntQueue queue) {
        IntStack stack = new IntStack();
        IntQueue newQueue = new IntQueue();

        // Dequeue all elements and push to stack
        while (!queue.isEmpty()) {
            Integer number = queue.dequeue();
            if (number != null) {
                stack.push(number);
            }
        }

        // Pop from stack and enqueue to new queue
        while (true) {
            Integer number = stack.pop();
            if (number == null) {
                break;
            }
            newQueue.enqueue(number);
        }

        return newQueue;
    }

    // Main method to test queue reversal
    public static void main(String[] args) {
        QueueReversal reverser = new QueueReversal();

        // Test cases
        int[][] testCases = {
            {1, 2, 3},           // Normal queue
            {},                   // Empty queue
            {42},                // Single element
            {10, 20, 30, 40, 50} // Larger queue
        };

        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            IntQueue queue = new IntQueue();
            for (int num : testCases[i]) {
                queue.enqueue(num);
            }
            System.out.println("Original queue: " + queue);
            IntQueue reversed = reverser.reverseQueue(queue);
            System.out.println("Reversed queue: " + reversed + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Original queue: [1, 2, 3]
Reversed queue: [3, 2, 1]

Test case 2:
Original queue: []
Reversed queue: []

Test case 3:
Original queue: [42]
Reversed queue: [42]

Test case 4:
Original queue: [10, 20, 30, 40, 50]
Reversed queue: [50, 40, 30, 20, 10]

Explanation:

  • Test case 1: Enqueue [1, 2, 3] → stack [3, 2, 1 (top)] → new queue [3, 2, 1].
  • Test case 2: Empty queue → empty stack → empty queue.
  • Test case 3: Enqueue [42] → stack [42] → new queue [42].
  • Test case 4: Enqueue [10, 20, 30, 40, 50] → stack [50, 40, 30, 20, 10 (top)] → new queue [50, 40, 30, 20, 10].

How It Works

  • IntQueue:
    • Uses an array with front, rear, and size to manage integers in FIFO order.
    • enqueue: Adds to rear if not full.
    • dequeue: Removes from front if not empty.
    • toString: Formats queue as a string for output.
  • IntStack:
    • Uses an array with top to manage integers in LIFO order.
    • push: Adds to top if not full.
    • pop: Removes from top if not empty.
  • reverseQueue:
    • Dequeues all elements from the input queue to a stack (reversing order due to LIFO).
    • Pops all elements from the stack to a new queue (restoring FIFO order, now reversed).
  • Example Trace (Test case 1):
    • Enqueue 1, 2, 3: queue = [1, 2, 3], front=0, rear=2.
    • Dequeue to stack: stack = [1, 2, 3 (top)].
    • Pop to new queue: newQueue = [3, 2, 1].
  • Main Method: Tests normal, empty, single-element, and larger queues.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
Enqueue/DequeueO(1)O(1)
Push/PopO(1)O(1)
Full AlgorithmO(n)O(n)

Note:

  • n is the number of elements in the queue.
  • Time complexity: O(n) for n dequeues to stack and n pops to new queue.
  • Space complexity: O(n) for the stack and new queue.
  • Worst case: O(n) time and O(n) space for large queues.

✅ Tip: Use a stack to reverse a queue, as its LIFO nature naturally flips the order of elements. Test with various queue sizes to ensure the reversal works correctly.

⚠ Warning: Ensure the stack and queue sizes are sufficient to handle the input. Handle empty queues to avoid null pointer issues during reversal.