Implenting Stack in Jeliot tool

The full source code that you can run on Jeliot tool for the Stack algorithm is below.

Source Code:

import jeliot.io.*;

public class Stack {

    //top of the stack initially -1 signifying an empty stack

    public static int tos = -1;

    //array to implement the stack of size 3

    public static int stack[] = new int[3]; 

   

    public static void main() {

        // Pushing three items into the stack

        push(2);

        push(1);

        push(0); //vehicle begins the line

       

        //Popping three items out of the stack

        pop(); //First Testing Station

        pop(); //Second Testing Station

        pop(); //Third Testing Station

    }

    public static void push(int a){//method for push operation

        if(tos>=2){//checking if the stack is full

            System.out.println("Stack overflow");

            return;

        }

        //increasing top of the stack by 1

        tos++;

        //inserting an item to the top of the stack

        stack[tos] = a;

    }

   

    public static void pop(){//method for pop operation

        if(tos<=-1){//checking if the stack is empty

            System.out.println("Stack underflow");

            return;

        }

        //displaying the item being popped

        System.out.println("Item popped: " + stack[tos]);

        tos--; //decreasing the top of stack by 1

    }

}

Description of the algorithm:

This is an array implementation of a Stack.

The algorithm starts with initialization of the ‘tos’ variable which represents top of the stack. It is initially set to -1 to denote an empty stack. Keeping it -1 makes it easier to use with an array because the first element is stored in the position 0 in an array.

In the main method, we simply push three items 2, 1 and 0 one by one. As suggested in the manufacturing assembly line assumption, 0 is pushed last into the stack. Then we pop the elements once by one to represent different stages of assembly line.

The push method checks if the stack is full or not first. If it is full, it simply displays “Stack overflow” and returns. And if there is space, it inserts the element into top of the stack and increases ‘tos’ by 1 to denote the new top of the stack..

Likewise, the pop method checks if the stack is empty or not first. If it is empty, it simply displays “Stack underflow” and returns. And if there are elements, it displays the popped item into console and decreases ‘tos’ by 1 to denote the new top of the stack.

It should be noted that the popped element is not erased. Since the new ‘tos’ is now less that the index of the popped element, it will be overwritten when any element is pushed in future. So, just leaving the element as it is makes our approach more efficient by decreasing the number of operations.

Asymptotic analysis of the algorithm:

Pushing an item into top of the stack is a trivial operation which requires just writing the item into array and incrementing ‘tos’ by 1. So, it always has 2 operations, and its complexity is hence O(1).

Note that normally pushing 'n' items into Stack has complexity of O(n) in Worst Case but since we always push only three items in this implementation, it has complexity of constant time i.e. O(1).

In the same way, popping an item has just one operation of decreasing ‘tos’ by 1. So, its complexity is also O(1).

As we can see in the algorithm, we push 3 items and pop 3 items making it total of

2*3 + 3 = 9 operations

And it will always have same operations no matter the values pushed or popped. That is to say, this algorithm always runs in “Constant Time”. Thus, the complexity of this algorithm in terms of Big-O notation is O(1).