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)**.
## No comments:

## Post a Comment

Was this post helpful? Ask any questions you have, I will try to answer them for you.