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

Print Job Simulator

Problem Statement

Write a Java program that simulates a printer queue using a queue implementation. The program should allow users to enqueue print jobs (represented as strings) and dequeue them in order, printing each job as it is processed in a first-in, first-out (FIFO) manner. Test the implementation with various sequences of enqueue and dequeue operations, including edge cases like empty queues and null print jobs. You can visualize this as a printer handling a queue of documents, where each document is printed in the order it was submitted, and the printer processes one job at a time.

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

  • Enqueue: Add a print job (string) to the queue (e.g., "Document1").
  • Dequeue: Remove and process the next print job, printing its details. Output: For each operation, print the action performed (enqueue or dequeue) and, for dequeue, the processed job or a message if the queue is empty. Constraints:
  • Queue size is between 0 and 10^5.
  • Print jobs are non-empty strings containing printable ASCII characters, or null (handled gracefully).
  • The queue may be empty when dequeue is called. Example:
  • Input: Operations = [enqueue("Doc1"), enqueue("Doc2"), dequeue, enqueue("Doc3"), dequeue]
  • Output: 
    Enqueued Doc1
Enqueued Doc2
Dequeued and processed: Doc1
Enqueued Doc3
Dequeued and processed: Doc2
  • Explanation: Jobs are enqueued in order and dequeued in FIFO order, printing each job as processed.
  • 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(job)
        IF size equals array length THEN
            RETURN false (queue full)
        ENDIF
        INCREMENT rear
        SET array[rear] to job
        INCREMENT size
        RETURN true
    ENDFUNCTION
    
    FUNCTION dequeue()
        IF size equals 0 THEN
            RETURN null (queue empty)
        ENDIF
        SET job to array[front]
        INCREMENT front
        DECREMENT size
        RETURN job
    ENDFUNCTION
    
    FUNCTION isEmpty()
        RETURN size equals 0
    ENDFUNCTION
ENDCLASS

FUNCTION simulatePrinter(operations)
    CREATE queue as new StringQueue
    FOR each operation in operations
        IF operation.type equals "enqueue" THEN
            CALL queue.enqueue(operation.job)
            PRINT enqueued job
        ELSE IF operation.type equals "dequeue" THEN
            SET job to queue.dequeue()
            IF job is null THEN
                PRINT queue empty message
            ELSE
                PRINT dequeued and processed job
            ENDIF
        ENDIF
    ENDFOR
ENDFUNCTION

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

Algorithm Steps

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

Java Implementation

import java.util.*;

public class PrintJobSimulator {
    // 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 job) {
            if (size == array.length) {
                return false; // Queue full
            }
            array[++rear] = job;
            size++;
            return true;
        }

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

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

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

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

    // Simulates printer queue functionality
    public void simulatePrinter(List<Operation> operations) {
        StringQueue queue = new StringQueue();
        for (Operation op : operations) {
            if (op.type.equals("enqueue")) {
                boolean success = queue.enqueue(op.job);
                if (success) {
                    System.out.println("Enqueued " + (op.job != null ? op.job : "null"));
                } else {
                    System.out.println("Enqueue " + (op.job != null ? op.job : "null") + " failed: Queue full");
                }
            } else if (op.type.equals("dequeue")) {
                String job = queue.dequeue();
                if (job == null) {
                    System.out.println("Queue empty, cannot dequeue");
                } else {
                    System.out.println("Dequeued and processed: " + job);
                }
            }
        }
    }

    // Main method to test printer queue simulation
    public static void main(String[] args) {
        PrintJobSimulator simulator = new PrintJobSimulator();

        // Test cases
        List<List<Operation>> testCases = new ArrayList<>();
        
        // Test case 1: Normal sequence
        List<Operation> case1 = Arrays.asList(
            new Operation("enqueue", "Document1"),
            new Operation("enqueue", "Document2"),
            new Operation("dequeue", null),
            new Operation("enqueue", "Document3"),
            new Operation("dequeue", null)
        );
        testCases.add(case1);
        
        // Test case 2: Empty queue
        List<Operation> case2 = Arrays.asList(
            new Operation("dequeue", null)
        );
        testCases.add(case2);
        
        // Test case 3: Single job
        List<Operation> case3 = Arrays.asList(
            new Operation("enqueue", "SingleDoc"),
            new Operation("dequeue", null)
        );
        testCases.add(case3);
        
        // Test case 4: Multiple enqueues
        List<Operation> case4 = Arrays.asList(
            new Operation("enqueue", "Job1"),
            new Operation("enqueue", "Job2"),
            new Operation("enqueue", "Job3"),
            new Operation("dequeue", null),
            new Operation("dequeue", null)
        );
        testCases.add(case4);
        
        // Test case 5: Null job
        List<Operation> case5 = Arrays.asList(
            new Operation("enqueue", 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.simulatePrinter(testCases.get(i));
            System.out.println();
        }
    }
}

Output

Running the main method produces:

Test case 1:
Enqueued Document1
Enqueued Document2
Dequeued and processed: Document1
Enqueued Document3
Dequeued and processed: Document2

Test case 2:
Queue empty, cannot dequeue

Test case 3:
Enqueued SingleDoc
Dequeued and processed: SingleDoc

Test case 4:
Enqueued Job1
Enqueued Job2
Enqueued Job3
Dequeued and processed: Job1
Dequeued and processed: Job2

Test case 5:
Enqueued null
Dequeued and processed: null

Explanation:

  • Test case 1: Enqueues "Document1", "Document2", dequeues "Document1", enqueues "Document3", dequeues "Document2".
  • Test case 2: Dequeue on empty queue returns "Queue empty".
  • Test case 3: Enqueues single job, dequeues it.
  • Test case 4: Enqueues three jobs, dequeues two in FIFO order.
  • Test case 5: Enqueues null job, dequeues it.

How It Works

  • StringQueue:
    • Uses an array with front and rear indices to track the queue’s state, and size to track the number of jobs.
    • enqueue: Adds a job to the rear if the queue isn’t full.
    • dequeue: Removes and returns the front job if not empty.
    • isEmpty: Checks if the queue is empty.
  • simulatePrinter:
    • Enqueues jobs, printing each action.
    • Dequeues jobs, printing the processed job or "Queue empty".
  • Example Trace (Test case 1):
    • Enqueue "Document1": queue = ["Document1"], front=0, rear=0.
    • Enqueue "Document2": queue = ["Document1", "Document2"], front=0, rear=1.
    • Dequeue: Returns "Document1", queue = ["Document2"], front=1, rear=1.
    • Enqueue "Document3": queue = ["Document2", "Document3"], front=1, rear=2.
    • Dequeue: Returns "Document2", queue = ["Document3"], front=2, rear=2.
  • Main Method: Tests normal sequences, empty queue, single job, multiple enqueues, and null job.

Complexity Analysis Table

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

Note:

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

✅ Tip: Use a queue to simulate a printer’s job processing, as its FIFO nature ensures jobs are processed in submission order. Test with sequences that mix enqueue and dequeue operations to verify correctness.

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