Stack using array

Stack is a linear data structure in which elements can be inserted and deleted only from the top of the stack.
Stack can be implemented by using:

1. Array
2. Linked List

Inserting element into the stack is called Push and deleting element from the stack is called Pop.
In this tutorial we are going to implement stack using an array.

fig. 1

In the figure above you can see an array which can store up to 5 elements. We have to make this array behave like a stack but how are we going to make this array behave like a stack ?
We are going to do this by following the property of a stack and the property of a stack is that elements can only be inserted and deleted from one end called the top end of the stack. That’s the reason why we say implement stack using an array because we are using an array to create a stack.

To implement stack using array first we need to declare an array.
int stk[5];
or
int stk[MAX];      |  Here MAX is the maximum size of the stack, so if MAX = 5 then the size of the stack will be 5.

Initially the stack will be empty ie; there will be no elements in the stack as you can see in fig.1.
Always remember when the stack is empty the value of top is equal to -1.
When the stack is empty then this condition is known as underflow.  So  top = -1 means stack is empty and it is an underflow condition.

In figure 2 you can see first we pushed / inserted 5 into the stack. First the value of top is increased by 1 so from -1 the value of top becomes 0   (-1 + 1 = 0) and and element 5 is inserted.

Push 10
The value of top was 0, we incremented the value of top by 1 and top becomes 1 ( 0 + 1) = 1. Then the new element 10 gets inserted.

Push 16
The value of top was 1, we incremented the value of top by 1 so top becomes 2  (1 + 1 = 2) and the element 16 gets inserted.

Push 20
The value of top was 2, we incremented the vale of top by 1. Top becomes 3 (2 + 1 = 3) and the element 20 gets inserted.

To insert element into the stack we use this code in the program:
First we increment the value of top by 1.
top = top + 1;
Then we insert the element at the top position.
stk[top] = element;               | variable element stores the value to be inserted into the stack from the top.
So one property of stack is fulfilled which is, elements can only be inserted from the top.

 

Push 50
The value of top was 3 now we insert another element into the stack.
top = top + 1
top = 3    +  1 = 4
Top becomes 4 and the new element 50 is inserted at the top position which is the 4th index/position of the array / stack.
In figure 3 you can see that stack is full, there is no space left in the stack to accommodate a new element. Now we cannot insert any more elements into the stack because it is full.
When the stack is full then this condition is also known as overflow condition also called stack overflow.

So in the program we can check if the stack is full by using the following code:
 if(top == MAX – 1)
{
printf(“overflow”);
}

If  the value of  top = MAX – 1 then this means, stack is full. MAX is the maximum size of the stack/array so if MAX =  5 then stack/array can store up to 5 elements.
top  = (MAX – 1)
top  = (5   –      1) is  4
So top = 4 and when top is 4 it means stack is full when the maximum size of stack is 5.

fig. 4

Pop 50
To delete an element from the stack we first decrement / decrease the value of top by 1.
The value of top before deletion was 4 (see fig. 3). After decrementing value of top by 1 (4-1 = 3) the value of top becomes 3 and 50 gets deleted from the stack.

Pop 20
The value of top was 3. Decrement value of top by 1 so top becomes 2 (3-1=2).

Pop 16
The value of top before deleting 16 was 2. So after decrementing top by 1 top becomes 1 (2-1=1)

Pop 10
The value of top was 1 then we decrement top by 1 the value of top becomes 0 (1-1=0).

If we pop 5 then the value of top from 0 will become -1 (0 – 1 = -1) and the stack will become empty.

The following code is used in the program to pop an element from the stack:
top =  top – 1;