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

Ticket Counter Simulation

Problem Statement

Write a Java program that simulates a ticket counter system where customers, represented by names (strings), join a queue and are served in first-in, first-out (FIFO) order. The program should allow users to enqueue customers, dequeue them to simulate serving, and display the current queue size after each operation. Test the implementation with various sequences of enqueue and dequeue operations, including edge cases like empty queues and null customer names. You can visualize this as a ticket counter at a movie theater, where customers line up, are served one by one, and the staff tracks how many people are still waiting.

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

  • Enqueue: Add a customer name (string) to the queue (e.g., "Alice").
  • Dequeue: Remove and serve the next customer from the queue.
  • Size: Display the current number of customers in the queue. Output: For each operation, print the action performed (enqueue, dequeue, or size) and the result, such as the served customer, queue size, or error messages for empty queues. Constraints:
  • Queue size is between 0 and 10^5.
  • Customer names are non-empty strings containing printable ASCII characters, or null (handled gracefully).
  • The queue may be empty when dequeue or size is called. Example:
  • Input: Operations = [enqueue("Alice"), enqueue("Bob"), size, dequeue, size, enqueue("Charlie"), dequeue]
  • Output: 
    Enqueued Alice
Enqueued Bob
Queue size: 2
Served customer: Alice
Queue size: 1
Enqueued Charlie
Served customer: Bob
  • Explanation: Customers join and are served in order, with queue size reported as requested.
  • Input: Operations = [dequeue on empty queue]
  • Output: Queue empty, cannot dequeue

Pseudocode

CLASS StringQueue
    SET array to new string array of size 1000
    SET front to 0
    SET rear to -1
    SET size to 0
    
    FUNCTION enqueue(name)
        IF size equals array length THEN
            RETURN false (queue full)
        ENDIF
        INCREMENT rear
        SET array[rear] to name
        INCREMENT size
        RETURN true
    ENDFUNCTION
    
    FUNCTION dequeue()
        IF size equals 0 THEN
            RETURN null (queue empty)
        ENDIF
        SET name to array[front]
        INCREMENT front
        DECREMENT size
        RETURN name
    ENDFUNCTION
    
    FUNCTION size()
        RETURN size
    ENDFUNCTION
    
    FUNCTION isEmpty()
        RETURN size equals 0
    ENDFUNCTION
ENDCLASS

FUNCTION simulateTicketCounter(operations)
    CREATE queue as new StringQueue
    FOR each operation in operations
        IF operation.type equals "enqueue" THEN
            CALL queue.enqueue(operation.name)
            PRINT enqueued name
        ELSE IF operation.type equals "dequeue" THEN
            SET name to queue.dequeue()
            IF name is null THEN
                PRINT queue empty message
            ELSE
                PRINT served customer name
            ENDIF
        ELSE IF operation.type equals "size" THEN
            PRINT queue size
        ENDIF
    ENDFOR
ENDFUNCTION

FUNCTION main()
    SET testCases to array of operation sequences
    FOR each testCase in testCases
        PRINT test case details
        CALL simulateTicketCounter(testCase)
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define a StringQueue class with: a. An array to store customer names, with front, rear, and size to track queue state. b. Methods: enqueue (add to rear), dequeue (remove from front), size (return current size), isEmpty (check if empty).
  2. In the simulateTicketCounter method: a. Create a new StringQueue. b. For each operation:
    • If "enqueue", add the customer name and print the action.
    • If "dequeue", remove the next customer, print the served customer or "Queue empty".
    • If "size", print the current queue size.
  3. In the main method, test with sequences of enqueue, dequeue, and size operations, including empty queues, single customers, and null names.

Java Implementation

import java.util.*;

public class TicketCounterSimulation {
    // Custom queue implementation for strings
    static class StringQueue {
        private String[] array;
        private int front;
        private int rear;
        private int size;
        private static final int DEFAULT_SIZE = 1000;

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

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

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

        public int size() {
            return size;
        }

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

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

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

    // Simulates ticket counter system
    public void simulateTicketCounter(List<Operation> operations) {
        StringQueue queue = new StringQueue();
        for (Operation op : operations) {
            if (op.type.equals("enqueue")) {
                boolean success = queue.enqueue(op.name);
                if (success) {
                    System.out.println("Enqueued " + (op.name != null ? op.name : "null"));
                } else {
                    System.out.println("Enqueue " + (op.name != null ? op.name : "null") + " failed: Queue full");
                }
            } else if (op.type.equals("dequeue")) {
                String name = queue.dequeue();
                if (name == null) {
                    System.out.println("Queue empty, cannot dequeue");
                } else {
                    System.out.println("Served customer: " + name);
                }
            } else if (op.type.equals("size")) {
                System.out.println("Queue size: " + queue.size());
            }
        }
    }

    // Main method to test ticket counter simulation
    public static void main(String[] args) {
        TicketCounterSimulation simulator = new TicketCounterSimulation();

        // Test cases
        List<List<Operation>> testCases = new ArrayList<>();
        
        // Test case 1: Normal sequence
        List<Operation> case1 = Arrays.asList(
            new Operation("enqueue", "Alice"),
            new Operation("enqueue", "Bob"),
            new Operation("size", null),
            new Operation("dequeue", null),
            new Operation("size", null),
            new Operation("enqueue", "Charlie"),
            new Operation("dequeue", null)
        );
        testCases.add(case1);
        
        // Test case 2: Empty queue
        List<Operation> case2 = Arrays.asList(
            new Operation("dequeue", null),
            new Operation("size", null)
        );
        testCases.add(case2);
        
        // Test case 3: Single customer
        List<Operation> case3 = Arrays.asList(
            new Operation("enqueue", "David"),
            new Operation("size", null),
            new Operation("dequeue", null)
        );
        testCases.add(case3);
        
        // Test case 4: Multiple enqueues and dequeues
        List<Operation> case4 = Arrays.asList(
            new Operation("enqueue", "Eve"),
            new Operation("enqueue", "Frank"),
            new Operation("enqueue", "Grace"),
            new Operation("size", null),
            new Operation("dequeue", null),
            new Operation("dequeue", null),
            new Operation("size", null)
        );
        testCases.add(case4);
        
        // Test case 5: Null customer name
        List<Operation> case5 = Arrays.asList(
            new Operation("enqueue", null),
            new Operation("size", null),
            new Operation("dequeue", null)
        );
        testCases.add(case5);

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

Output

Running the main method produces:

Test case 1:
Enqueued Alice
Enqueued Bob
Queue size: 2
Served customer: Alice
Queue size: 1
Enqueued Charlie
Served customer: Bob

Test case 2:
Queue empty, cannot dequeue
Queue size: 0

Test case 3:
Enqueued David
Queue size: 1
Served customer: David

Test case 4:
Enqueued Eve
Enqueued Frank
Enqueued Grace
Queue size: 3
Served customer: Eve
Served customer: Frank
Queue size: 1

Test case 5:
Enqueued null
Queue size: 1
Served customer: null

Explanation:

  • Test case 1: Enqueues Alice, Bob; reports size 2; dequeues Alice; reports size 1; enqueues Charlie; dequeues Bob.
  • Test case 2: Dequeue and size on empty queue return error and 0.
  • Test case 3: Enqueues David, reports size 1, dequeues David.
  • Test case 4: Enqueues three customers, reports size 3, dequeues two, reports size 1.
  • Test case 5: Enqueues null name, reports size 1, dequeues null.

How It Works

  • StringQueue:
    • Uses an array with front, rear, and size to manage customer names in FIFO order.
    • enqueue: Adds to rear if not full.
    • dequeue: Removes from front if not empty.
    • size: Returns current number of customers.
  • simulateTicketCounter:
    • Enqueues customers, printing the action.
    • Dequeues customers, printing the served customer or "Queue empty".
    • Reports queue size when requested.
  • Example Trace (Test case 1):
    • Enqueue "Alice": array=["Alice"], front=0, rear=0, size=1.
    • Enqueue "Bob": array=["Alice","Bob"], front=0, rear=1, size=2.
    • Size: Returns 2.
    • Dequeue: Returns "Alice", array=["-","Bob"], front=1, rear=1, size=1.
    • Size: Returns 1.
    • Enqueue "Charlie": array=["-","Bob","Charlie"], front=1, rear=2, size=2.
    • Dequeue: Returns "Bob", array=["-","-","Charlie"], front=2, rear=2, size=1.
  • Main Method: Tests normal sequences, empty queue, single customer, multiple operations, and null name.

Complexity Analysis Table

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

Note:

  • n is the number of operations.
  • Time complexity: O(1) for each enqueue, dequeue, or size; O(n) for n operations.
  • Space complexity: O(n) for the queue storing up to n customers.
  • Worst case: O(n) time and O(n) space for many enqueue operations.

✅ Tip: Use a queue for a ticket counter simulation, as its FIFO nature ensures customers are served in arrival order. Test with size queries to verify queue state after operations.

⚠ Warning: Handle null names and empty queue cases to avoid unexpected behavior. Ensure the queue size is sufficient to accommodate the input sequence.