EnggPedia - The Engineering Encyclopedia

Wed03292017

Last update06:04:15 AM

Cpanel
Back

Stack - Definition, Insertion, Deletion Operations on Stack

Stack is a linear list of elements in which the insertion and deletion is done by using only one end of the stack. The end at which the insertion and deletion takes place is called as the top of the stack.

This mean that the last item o\to be added to the stack is the first item to be deleted from the stack. Thus accordingly it is sometimes also known as First In Last Out (FILO) or Last In First Out (LIFO).

Example:

1. Boxes of shoes that are placed over one another from a stack.
2. Nearly clean shirts that are placed over one another form a stack.
3. Files in offices also form a stack.

The insertion of an element to the stack is called as pushing or stacking, while the deletion of an element from the stack is called as poping or unstacking.

Operations on stack:

First of all a vector is allocated to the stack which have to much capacity to keep all the elements of the stack. If the stack is empty then the pointer Top is zero. If it has only one item the pointer Top has the value one, and so on. Similarly if the pointer Top=max point then it means that the stack is full and there is no capacity to hold the other element.

Algorithm:

The step by step process to solve a particular problem is called algorithm.

1. Insertion
2. Deletion

Insertion:

To insert / add an element/ item on to the top of the stack, following algorithmic steps are followed.

1.   [check for overflow].
If Top=N then print overflow and Exit. Otherwise
2.   [increase Top by 1].
Top= Top+1
3.   [insert an element].
Stack[Top]=X
4.   [Exit].


Deletion:

To delete / remove an element / item from to the top of the stack, following algorithmic steps are followed.

1.   [check for underflow].
If Top=Null then print underflow and Exit. Otherwise
2.   [Delete item].
Delete Stack[Top].
3.   [decrease Top by 1].
Top= Top-1
4.   [Exit].


Stack Representation in Computer:

Stack may be represented in computer memory in various ways but generally stack is represented in computer memory by using array. Now for example, we maintained our stack by a linear array STACKARR and a pointer variable Top which contain the location of the top element of the stack and a variable Top which contain the location of the top element of the stack and a variable MAXSTACK, which gives the maximum number of elements that can be hold by the stack in the computer memory, as follow

 Aaa Bbb Ccc Ddd 1 2 3 4 5 6 7 8

In the above figure Top = 4, MAXSTACK = 8.

The condition Top = 0 or Top = Null will indicated that the stack is empty. The situation is called UNDERFLOW.

The condition Top = N or Top = Full will indicated that the stack is full. The situation is called OVERFLOW.

The above figure shows an array representation of a stack. That is, a stack is represented through an array.

Since when Top = 5 which shows that the stack has 5 elements and MAXSTACK = 8 shows that three more elements can be accommodated.