WA3. Stacks and Queues¶

Statement¶

For this assignment, assume that you are developing a system for a manufacturing assembly line that builds automobiles. There are three stations in the manufacturing line where an inspector will visually inspect the vehicle. Your program must keep track of these inspections as they occur. You decided to develop your program using a stack data structure. As your vehicle begins the line you will push the number 0, which indicates that an inspection has not yet occurred, onto the stack three subsequent times.

At each station in the line, you will pop one of the items off of the stack. Each time your algorithm pops an item from the stack you must print it out to the console using the System.out.println function. Your algorithm should perform the functions of the stack as illustrated in the diagram.

Stack Diagram

Introduction¶

This text will discuss the problem above, unfortunately, the problem statement is not very clear so the text will start by including some perspective on the problem and continue by discussing the solution accordingly.

The scenario that text tries to solve is as the following:

An assembly line does exist and includes three stations for inspection.
The Assembly line has a queue of Cars that are waiting to be processed.
Each Car has a Stack of three inspections objects (or indicators) that are waiting to be inspected.
When the Assembly line runs, it starts processing the first Car in the queue, and pass it through the three stations.
As soon as the first Car is finished its journey through the three stations, the next Car in the queue is processed, and so on until the queue is empty.
Upon passing an inspection station the Car is inspected and a print statements indicates the car number, the station number, and the inspection number is printed to the standard output.

Conclusion¶

Upon running the attached code, the steps listed in the introduction are followed, and the following output is produced:

Output

Here is a screenshot of the code running in VSCode IDE:

Output

Although it seems the code is a bit complicated, but the text is explaining the code in details in the coming sections and the code is well commented.
The text is going down the road of heavy abstraction, and the code is not very readable, but it is very flexible and can be easily modified to fit any other scenario (e.g. a different number of stations, or a different number of inspections per car, etc.)

Important Notes¶

version

The code is written for Java SE Development Kit 17.0.2 as shown in the screenshot above.
Unfortunately, the JeLiot plugin is not compatible with Java 17, so the code is not visualized using JeLiot.
Please run this code using Java 17 or higher; although it might work with older versions, but it is not tested and not guaranteed to work.
The problem statement asks about pushing inspection points of value 0 and then popping them, but the code is pushing 2,1,0 instead of 0,0,0 to make the output more readable.
The this keyword is omitted most of the time for readability purposes, but it is used when it is necessary; however, this might cause some confusion and work on all environments. The code is tested in the environment mentioned above (VsCode + JDK 17) and it works fine.
The @SuppressWarnings("unchecked") annotation is used to suppress the warnings that are produced by the compiler when casting objects to generic types.
The text is now going through the classes one by one and explaining them in details (from top to bottom).

Runtime Analysis¶

Please read the Code Walkthrough section before reading this section.
The analysis is done using the Big-O notation.
The analysis is done for the run() method of the AssemblyLine class assuming that we have n Cars in the queue and m stations in the Assembly line and each Car has k inspections.
The number of inspections k may not always be equal to the number of stations m as the problem statement does not mention that, but the code is written to handle this case as there may be stations that do not perform any inspections.
For simplicity, the analysis is done assuming that k = m and the number of inspections is equal to the number of stations.
Thus we have n Cars, each Car has m inspections, and we have m stations.

    public void run() {
        int totalCars = cars.length(); // 1
        System.out.println("Assembly line is running, total cars: " + totalCars + " to be inspected ... \n\n");
        while (!cars.isEmpty()) { // 2
            Car car = processCar(); // 3
            car.initializeInspections(); // 4
            for (int i = 0; i < stations.length; i++) { // 5
                stations[i].inspect(car); // 6
            }
        }
        System.out.println(
                "Assembly line has finished running, total cars: " + totalCars + "have been inspected.");
    }

Let’s analyze the AssemblyLine.run() method line by line (line numbers are shown in the code snippet above):
1. int totalCars = cars.length(); takes O(1) time as it is a simple method call on the MQueue class.
2. while (!cars.isEmpty()) { takes O(1) time as it is a simple method call on the MQueue class, but it is executed n times. Thus, it takes O(n) time.
3. Car car = processCar(); takes O(1) time as it is a simple method call on the MQueue class.
4. car.initializeInspections(); takes O(m) as it does m insertions to the MStack class.
5. for (int i = 0; i < stations.length; i++) { takes O(1) time as it is a simple loop that is executed m times.
6. stations[i].inspect(car); takes O(1) time as it is a simple method call on the Station class and then on pop() of the MStack class.
Thus, the total time complexity of the AssemblyLine.run() is as the following:

O(run) = O (1) + O(n) * ( O(1) + O(m) + O(m) * ( O(m) + O(1) ))     // assuming k = m
       = O (1) + O(n) * ( O(1) + O(m) + O(m) + O(1) )        // unwrapping the inner loop
       = O (1) + O(n) * ( 2*O(1) + 2*O(m) )  // ignoring the lower order terms in the inner loop
       = O (1) + O(n) * 2*O(m)               // ignoring the lower order terms in the outer loop
       = O (n) * 2*O(m)
       = O(2 * n * m)

Thus, the total time complexity of the AssemblyLine.run() is O(2nm) where n is the number of Cars and m is the number of stations.

Code Walkthrough¶

Main Class¶

Main is the entry point of the program nad it is responsible for:
1. initializing the Assembly line.
2. initializing Cars and adding them to the Assembly line.
3. running the Assembly line.

class Main {
    public static void main(String[] args) {
        int expectedCars = 3; // n
        int numberOfStations = 3; // m
        int expectedInspections = 3; // k

        AssemblyLine assemblyLine = new AssemblyLine(expectedCars, numberOfStations);

        for (int i = 0; i < expectedCars; i++) {
            assemblyLine.addCar(new Car(i + 1, expectedInspections));
        }

        assemblyLine.run();

    }
}

AssemblyLine Class¶

AssemblyLine abstracts the assembly line mentioned in the problem statement.
It has the following responsibilities:
1. manages a queue of Cars that wait to be processed.
2. manages an array stations that are responsible for inspecting the Cars.
3. defining the run method that starts the processing of the Cars.
Constructor(): takes the expected number of Cars and number of stations as an arguments and initializes the queue and the stations array accordingly.
addCar(): takes a Car object as an argument and adds it to the queue.
processCar(): dequeues a Car from the queue and returns it to the caller.
run():
- It is the most important method.
- IT starts at the front of the Cars queue and processes each Car in the queue.
- For each Car, it passes it through the three stations by calling the Station.inspect() method which in turn calls the Car.inspect() method.

class AssemblyLine {
    private MQueue<Car> cars;
    private InspectionStation[] stations;

    public AssemblyLine(int expectedCars, int numberOfStations) {
        cars = new MQueue<Car>(expectedCars);
        stations = new InspectionStation[numberOfStations];
        for (int i = 0; i < numberOfStations; i++) {
            stations[i] = new InspectionStation(i + 1);
        }
    }

    public void addCar(Car car) {
        cars.enqueue(car);
    }

    public Car processCar() {
        return cars.dequeue();
    }

    public void run() {
        int totalCars = cars.length();
        System.out.println("Assembly line is running, total cars: " + totalCars + " to be inspected ... \n\n");
        while (!cars.isEmpty()) {
            Car car = processCar();
            car.initializeInspections();
            for (int i = 0; i < stations.length; i++) {
                stations[i].inspect(car);
            }
        }
        System.out.println(
                "Assembly line has finished running, total cars: " + totalCars + "have been inspected.");
    }
}

InspectionStation Class¶

InspectionStation abstracts the inspection stations mentioned in the problem statement.
It has an id and inspect method
inspect:
- It takes a Car object as an argument and calls the Car.inspect() method.
- It also checks if inspection stack on the Car is empty, then it logs a message to the standard output indicating that the Car has passed all the inspection station.

class InspectionStation {
    private int id;

    public InspectionStation(int id) {
        this.id = id;
    }

    public int getId() {
        return id;
    }

    public void inspect(Car car) {
        car.inspect(id);
        if (car.getInspections().isEmpty()) {
            System.out.println("Car " + car.getId() + " has passed all inspections");
            System.out.println("-----------------------------------");
            System.out.println("\n\n");
        }
    }

}

Car Class¶

Car abstracts the cars mentioned in the problem statement.
The Car has and id, Stack of inspections, initializeInspections, getInspections, and inspect methods.
Constructor(): takes the id of the Car as an argument along the numberOfInspections and initializes an empty stack of inspections with the given number of inspections.
initializeInspections(): pushes the number of inspections to the stack. The code is pushing 2,1,0 instead of 0,0,0 to make the output more readable.
getInspections(): returns the stack of inspections to the caller.
inspect(): pops the top inspection from the stack and logs a message to the standard output indicating that the Car is being inspected at a specific station and inspection point.

class Car {
    private int id;
    private MStack<Integer> inspections;
    private int noOfInspections;

    public Car(int id, int noOfInspections) {
        this.id = id;
        inspections = new MStack<Integer>(noOfInspections);
        this.noOfInspections = noOfInspections;
    }

    public void initializeInspections() {
        for (int i = noOfInspections - 1; i >= 0; i--) {
            inspections.push(i);
        }
    }

    public int getId() {
        return id;
    }

    public MStack<Integer> getInspections() {
        return inspections;
    }

    public void inspect(int stationId) {
        int inspectionPoint = inspections.pop();
        System.out.println("Car " + id + " is being inspected at station " + stationId + " for inspection point "
                + inspectionPoint);
    }
}

MStack Class¶

MStack is a generic class that implements the stack data structure.
The stack is implemented using an array.
The stack has the following methods:
1. push(): takes an item as an argument and pushes it to the top of the stack.
2. pop(): pops the top item from the stack and returns it to the caller.
3. peek(): returns the top item from the stack to the caller.
4. isEmpty(): returns true if the stack is empty, false otherwise.
5. isFull(): returns true if the stack is full, false otherwise.
6. length(): returns the number of items in the stack.

class MStack<T> {
    private T[] stack;
    private int top;
    private int size;

    @SuppressWarnings("unchecked")
    public MStack(int size) {
        this.size = size;
        this.stack = (T[]) new Object[size];
        top = -1;
    }

    public void push(T item) {
        if (top == size - 1) {
            System.out.println("MStack is full");
        } else {
            top++;
            stack[top] = item;
        }
    }

    public T pop() {
        if (top == -1) {
            System.out.println("MStack is empty");
            return null;
        } else {
            T item = stack[top];
            top--;
            return item;
        }
    }

    public T peek() {
        if (top == -1) {
            System.out.println("MStack is empty");
            return null;
        } else {
            return stack[top];
        }
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == size - 1;
    }

    public int length() {
        return top + 1;
    }
}

MQueue Class¶

MQueue is a generic class that implements the queue data structure.
The queue is implemented using an array.
The MQueue has the following methods:
1. enqueue(): takes an item as an argument and adds it to the rear of the queue.
2. dequeue(): removes the item from the front of the queue and returns it to the caller.
3. isEmpty(): returns true if the queue is empty, false otherwise.
4. isFull(): returns true if the queue is full, false otherwise.
5. length(): returns the number of items in the queue.

class MQueue<T> {
    private T[] queue;
    private int front;
    private int rear;
    private int size;

    @SuppressWarnings("unchecked")
    public MQueue(int size) {
        this.size = size;
        queue = (T[]) new Object[size];
        front = -1;
        rear = -1;
    }

    public void enqueue(T item) {
        if (rear == size - 1) {
            System.out.println("MQueue is full");
        } else {
            if (front == -1) {
                front = 0;
            }
            rear++;
            queue[rear] = item;
        }
    }

    public T dequeue() {
        if (front == -1) {
            System.out.println("MQueue is empty");
            return null;
        } else {
            T item = queue[front];
            if (front == rear) {
                front = -1;
                rear = -1;
            } else {
                front++;
            }
            return item;
        }
    }

    public boolean isEmpty() {
        return front == -1;
    }

    public boolean isFull() {
        return rear == size - 1;
    }

    public int length() {
        return rear - front + 1;
    }
}

References¶

Shaffer, C. (2011). A Practical Introduction to Data Structures and Algorithm Analysis. Blacksburg: Virginia. Tech. https://people.cs.vt.edu/shaffer/Book/JAVA3e20130328.pdf. Chapter 4.
Barnett, G. & Del Tongo, L. (2008). Data Structures and Algorithms: An Annotated Reference with Examples. Chapter 6: Queues.