Stack is a linear data structure which enables the user to add and remove elements from the top end only, using the concept of LIFO (Last In First Out).

**Note:** Since insertion and deletion both takes place from the top end only, we have to keep record of the position of the topmost (last) element only.

Consider a stack implemented using an array ST[ ]. The index of the last element inserted (top most element) is stored in the stack pointer variable ‘top’.

Let the size of the stack be denoted by the variable ‘size’.

In the given diagram, value of ‘size’ = 5

Initially when the stack is empty, the value of Stack Pointer (top) should be = -1 (and not any other index from 0-4)

#### PUSH Operation (Inserting element in the stack)

The first element which you insert in the stack must go to index ‘0’ so, the value of stack pointer ‘top’ should increase from 0 to 1 and then we insert the element at index 1.

Similarly, when we insert the next element, the value of stack pointer ‘top’ should increase from 1 to 2 and then we insert the element at index 2 and so on.

Now when the stack is full, the index of stack pointer ‘top’ will become 4 (size-1). So now no more element can be inserted. This situation is known as ‘OVERFLOW’

While inserting element in the stack, always remember to check for a condition where the stack is full and no more element can be inserted.

So, **if(top == size – 1)** then OVERFLOW will occur and you cannot insert any more element. In all other cases you can insert, by first increasing ‘top’ and then saving the element at this index.

**To cut the long story short, while inserting ‘top’ increases.**

**Programming Code Implementing Push Operation:**

void push(int n) // Function to insert element in Stack { if(top == size-1) // Condition for Overflow { System.out.println("OVERFLOW"); } else { top = top + 1; ST[top] = n; } }

#### POP Operation (Deleting element from the stack)

The first element which you delete will be from the ‘top’ index (following the LIFO pattern). Before deleting, save the element to be deleted and print (or return it as asked in the question). After that, the value of stack pointer ‘top’ should decrease from 4 to 3.

Similarly, when we delete the next element, the value of stack pointer ‘top’ should decrease from 3 to 2 and so on.

Now when the stack is empty, the index of stack pointer ‘top’ will become -1. So now no more element can be deleted. This situation is known as ‘UNDERFLOW’

While deleting element from the stack, always remember to check for a condition where the stack is empty and no more element can be deleted.

So, **if(top == – 1)** then UNDERFLOW will occur and you cannot delete any more element. In all other cases you can delete, by decreasing ‘top’.

**To cut the long story short, while deleting, ‘top’ decreases.**

**Programming Code Implementing Pop Operation:**

int pop() // Function to delete element in Stack { if(top == -1) // Condition for Underflow { System.out.println("UNDERFLOW"); return -999; } else { int val = ST[top]; // Storing the element which will be removed top = top - 1; return val; } }

#### Complete Java Program implementing Operations on Stack:

/** * The class Stack implements operations of stack using Java * @author : www.guideforschool.com * @Program Type : BlueJ Program - Java */ class Stack { int ST[]; // Array to implement stack int size; // Maximum size of the stack int top; // Index of topmost element (Stack Pointer) Stack() // Default constructor { size = 0; top = 0; } Stack(int cap) // Parameterised Constructor { size = cap; ST = new int[size]; top = -1; // Initialising top with -1 } void push(int n) // Function to insert element in Stack { if(top == size-1) // Condition for Overflow { System.out.println("OVERFLOW"); } else { top = top + 1; ST[top] = n; // Storing value in Stack } } int pop() // Function to delete element from Stack { if(top == -1) // Condition for Underflow { System.out.println("UNDERFLOW"); return -999; } else { int val = ST[top]; // Storing the element which will be removed top = top - 1; return val; } } void display() { if(top == -1) { System.out.println("The stack is empty"); } else { System.out.println("The elements in the stack are : "); for(int i = top; i>=0; i--) { System.out.println(ST[i]); } } } }

sir,why are we required to save the element to be deleted in a variable.And what is the purpose of returning the variable?is it a required one.

The reason is that while adding element to a stack, the user is providing the vlaue. So he knows the number to be added. But while removing elements he doesn’t know which number will be deleted. He only knows that a LIFO approach will be followed. So we display or return the element which we are deleting to the user.

At the end, it all depends on the question asked. If you are asked to return, then do so, otherwse not..

initially when the stack is empty, the value of Stack Pointer (top) should be = -1 (and not any other index from 0-4)

sir,why this has been done? why cant the value of top be 0??

If value in stack pointer is 0, it means that there is an element in the stack at index 0. So the stack is not empty if stack pointer has a value equal to any of the stack index.

This is why we take the stack pointer to be initially -1 since -1 is not from the index of stack.

Sir, this program is different from that given in the isc marking scheme.

if I write this answer will I get the full marks ?

Yes you will get marks.

Thanks Sir, for solving my doubt.

you are doing an exceptional job!

why is your program returning -999 if top == -1;.

Because the question which comes in ISC, asks you to return a number when Underflow condition occurs. It can be given to return any random number.