Circular Queue Test

Problem Statement

Write a Java program that implements a circular queue to handle edge cases, such as enqueueing and dequeuing in a loop, and tests it with a sequence of operations to verify circular behavior. The circular queue should reuse array space by wrapping around when the rear pointer reaches the end, and handle full and empty queue conditions. Test the implementation with various sequences of enqueue and dequeue operations, including wrap-around scenarios, full queues, and empty queues. You can visualize this as a circular conveyor belt where items are added and removed, and when the belt’s end is reached, it loops back to the start to continue adding items.

Input: A sequence of operations, where each operation is either:

• Enqueue: Add an integer to the queue (e.g., enqueue 5).
• Dequeue: Remove and return the next integer from the queue. Output: For each operation, print the action performed (enqueue or dequeue) and the result, including queue state or error messages for full/empty conditions. Constraints:
• Queue capacity is fixed (e.g., 5 elements for testing).
• Elements are integers in the range [-10^9, 10^9].
• The queue may be empty or full during operations. Example:
• Input: Operations = [enqueue(1), enqueue(2), enqueue(3), dequeue, enqueue(4), dequeue, enqueue(5)]
• Output:

  Enqueued 1, Queue: [1]
  Enqueued 2, Queue: [1, 2]
  Enqueued 3, Queue: [1, 2, 3]
  Dequeued 1, Queue: [2, 3]
  Enqueued 4, Queue: [2, 3, 4]
  Dequeued 2, Queue: [3, 4]
  Enqueued 5, Queue: [3, 4, 5]
  

• Explanation: The queue operates in FIFO order, reusing space as elements are dequeued.
• Input: Operations = [enqueue(1), enqueue(2), enqueue(3), enqueue(4), enqueue(5), enqueue(6) on capacity 5]
• Output: Enqueue 6 failed: Queue full

Pseudocode

CLASS CircularQueue
    SET array to new integer array of size capacity
    SET front to 0
    SET rear to -1
    SET size to 0
    SET capacity to input capacity
    
    FUNCTION enqueue(number)
        IF size equals capacity THEN
            RETURN false (queue full)
        ENDIF
        SET rear to (rear + 1) mod capacity
        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]
        SET front to (front + 1) mod capacity
        DECREMENT size
        RETURN number
    ENDFUNCTION
    
    FUNCTION isEmpty()
        RETURN size equals 0
    ENDFUNCTION
    
    FUNCTION isFull()
        RETURN size equals capacity
    ENDFUNCTION
    
    FUNCTION toString()
        CREATE result as empty string
        APPEND "["
        FOR i from 0 to size - 1
            SET index to (front + i) mod capacity
            APPEND array[index] and ", " to result
        ENDFOR
        IF result ends with ", " THEN
            REMOVE last ", "
        ENDIF
        APPEND "]" to result
        RETURN result
    ENDFUNCTION
ENDCLASS

FUNCTION testCircularQueue(operations, capacity)
    CREATE queue as new CircularQueue with capacity
    FOR each operation in operations
        IF operation.type equals "enqueue" THEN
            IF queue.enqueue(operation.number) THEN
                PRINT enqueued number and queue state
            ELSE
                PRINT enqueue failed: queue full
            ENDIF
        ELSE IF operation.type equals "dequeue" THEN
            SET number to queue.dequeue()
            IF number is null THEN
                PRINT queue empty message
            ELSE
                PRINT dequeued number and queue state
            ENDIF
        ENDIF
    ENFOR
ENDFUNCTION

FUNCTION main()
    SET testCases to array of operation sequences with fixed capacity
    FOR each testCase in testCases
        PRINT test case details
        CALL testCircularQueue(testCase, capacity)
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define a CircularQueue class with: a. An array of fixed capacity, with front, rear, and size to track state. b. Methods: enqueue (add to rear with wrap-around), dequeue (remove from front with wrap-around), isEmpty, isFull, toString.
2. In enqueue: a. If queue is full, return false. b. Increment rear modulo capacity, add number, increment size.
3. In dequeue: a. If queue is empty, return null. b. Remove number at front, increment front modulo capacity, decrement size.
4. In testCircularQueue: a. Create a CircularQueue with given capacity. b. For each operation:
   • Enqueue: Add number, print queue state or "Queue full".
   • Dequeue: Remove number, print result and queue state or "Queue empty".
5. In the main method, test with sequences demonstrating normal operations, wrap-around, full queue, and empty queue cases.

Java Implementation

import java.util.*;

public class CircularQueueTest {
    // Custom circular queue implementation for integers
    static class CircularQueue {
        private int[] array;
        private int front;
        private int rear;
        private int size;
        private int capacity;

        public CircularQueue(int capacity) {
            this.array = new int[capacity];
            this.front = 0;
            this.rear = -1;
            this.size = 0;
            this.capacity = capacity;
        }

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

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

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

        public boolean isFull() {
            return size == capacity;
        }

        public String toString() {
            StringBuilder result = new StringBuilder("[");
            for (int i = 0; i < size; i++) {
                int index = (front + i) % capacity;
                result.append(array[index]);
                if (i < size - 1) {
                    result.append(", ");
                }
            }
            result.append("]");
            return result.toString();
        }
    }

    // Helper class for operations
    static class Operation {
        String type;
        Integer number; // For enqueue operations

        Operation(String type, Integer number) {
            this.type = type;
            this.number = number;
        }
    }

    // Tests circular queue with operations
    public void testCircularQueue(List<Operation> operations, int capacity) {
        CircularQueue queue = new CircularQueue(capacity);
        for (Operation op : operations) {
            if (op.type.equals("enqueue")) {
                if (queue.enqueue(op.number)) {
                    System.out.println("Enqueued " + op.number + ", Queue: " + queue);
                } else {
                    System.out.println("Enqueue " + op.number + " failed: Queue full");
                }
            } else if (op.type.equals("dequeue")) {
                Integer number = queue.dequeue();
                if (number == null) {
                    System.out.println("Queue empty, cannot dequeue");
                } else {
                    System.out.println("Dequeued " + number + ", Queue: " + queue);
                }
            }
        }
    }

    // Main method to test circular queue
    public static void main(String[] args) {
        CircularQueueTest tester = new CircularQueueTest();
        int capacity = 5; // Fixed capacity for all test cases

        // Test cases
        List<List<Operation>> testCases = new ArrayList<>();
        
        // Test case 1: Normal sequence
        List<Operation> case1 = Arrays.asList(
            new Operation("enqueue", 1),
            new Operation("enqueue", 2),
            new Operation("enqueue", 3),
            new Operation("dequeue", null),
            new Operation("enqueue", 4),
            new Operation("dequeue", null),
            new Operation("enqueue", 5)
        );
        testCases.add(case1);
        
        // Test case 2: Wrap-around behavior
        List<Operation> case2 = Arrays.asList(
            new Operation("enqueue", 1),
            new Operation("enqueue", 2),
            new Operation("enqueue", 3),
            new Operation("dequeue", null),
            new Operation("dequeue", null),
            new Operation("enqueue", 4),
            new Operation("enqueue", 5),
            new Operation("enqueue", 6)
        );
        testCases.add(case2);
        
        // Test case 3: Full queue
        List<Operation> case3 = Arrays.asList(
            new Operation("enqueue", 1),
            new Operation("enqueue", 2),
            new Operation("enqueue", 3),
            new Operation("enqueue", 4),
            new Operation("enqueue", 5),
            new Operation("enqueue", 6)
        );
        testCases.add(case3);
        
        // Test case 4: Empty queue
        List<Operation> case4 = Arrays.asList(
            new Operation("dequeue", null)
        );
        testCases.add(case4);

        // Run test cases
        for (int i = 0; i < testCases.size(); i++) {
            System.out.println("Test case " + (i + 1) + " (capacity=" + capacity + "):");
            tester.testCircularQueue(testCases.get(i), capacity);
            System.out.println();
        }
    }
}

Output

Running the main method produces:

Test case 1 (capacity=5):
Enqueued 1, Queue: [1]
Enqueued 2, Queue: [1, 2]
Enqueued 3, Queue: [1, 2, 3]
Dequeued 1, Queue: [2, 3]
Enqueued 4, Queue: [2, 3, 4]
Dequeued 2, Queue: [3, 4]
Enqueued 5, Queue: [3, 4, 5]

Test case 2 (capacity=5):
Enqueued 1, Queue: [1]
Enqueued 2, Queue: [1, 2]
Enqueued 3, Queue: [1, 2, 3]
Dequeued 1, Queue: [2, 3]
Dequeued 2, Queue: [3]
Enqueued 4, Queue: [3, 4]
Enqueued 5, Queue: [3, 4, 5]
Enqueued 6, Queue: [3, 4, 5, 6]

Test case 3 (capacity=5):
Enqueued 1, Queue: [1]
Enqueued 2, Queue: [1, 2]
Enqueued 3, Queue: [1, 2, 3]
Enqueued 4, Queue: [1, 2, 3, 4]
Enqueued 5, Queue: [1, 2, 3, 4, 5]
Enqueue 6 failed: Queue full

Test case 4 (capacity=5):
Queue empty, cannot dequeue

Explanation:

• Test case 1: Normal enqueue/dequeue operations within capacity.
• Test case 2: Demonstrates wrap-around (after dequeuing, rear wraps to start for 4, 5, 6).
• Test case 3: Fills queue to capacity, fails to enqueue 6.
• Test case 4: Dequeue on empty queue returns error.

How It Works

• CircularQueue:
  • Uses an array with front, rear, and size to manage integers in FIFO order.
  • enqueue: Adds to rear (modulo capacity) if not full.
  • dequeue: Removes from front (modulo capacity) if not empty.
  • toString: Formats queue contents from front to rear.
  • Wrap-around: rear = (rear + 1) % capacity and front = (front + 1) % capacity enable circular behavior.
• testCircularQueue:
  • Enqueues numbers, prints queue state or "Queue full".
  • Dequeues numbers, prints result and queue state or "Queue empty".
• Example Trace (Test case 2):
  • Enqueue 1: array=[1], front=0, rear=0, size=1.
  • Enqueue 2: array=[1,2], front=0, rear=1, size=2.
  • Enqueue 3: array=[1,2,3], front=0, rear=2, size=3.
  • Dequeue 1: array=[-,2,3], front=1, rear=2, size=2.
  • Dequeue 2: array=[-,-,3], front=2, rear=2, size=1.
  • Enqueue 4: array=[4,-,3], front=2, rear=0, size=2 (wrap-around).
  • Enqueue 5: array=[4,5,3], front=2, rear=1, size=3.
  • Enqueue 6: array=[4,5,3,6], front=2, rear=2, size=4.
• Main Method: Tests normal operations, wrap-around, full queue, and empty queue.

Complexity Analysis Table

Note:

• n is the number of operations, c is the fixed capacity.
• Time complexity: O(1) for each enqueue/dequeue; O(n) for n operations.
• Space complexity: O(c) for the fixed-size array.
• Worst case: O(n) time for n operations, O(c) space for the queue.

✅ Tip: Use a circular queue to efficiently reuse array space, especially for applications with frequent enqueue and dequeue operations. Test wrap-around behavior by dequeuing some elements and then enqueuing more to verify the circular property.

⚠ Warning: Carefully manage front and rear indices with modulo operations to ensure correct wrap-around. Handle full and empty queue cases to avoid incorrect behavior.