Implementing Stack with Arrays

Stack

The stack is a data structure where all insertions and deletions are performed at on end. The end at which insertions and deletions are performed is called tos (top of the stack). Suppose, we keep one book on the top of the other. The pile of such collection of books where a book is on top of other is called a stack. The stack is also known as pushdown list or LIFO (Last In First Out).  That means the book which is kept at the end on the stack will be the first book to be taken out of the stack.

The operations which can be performed on Stack are :

  • Push – It is used to push the value onto the stack. Before pushing the value on the stack, the value of the top is incremented to point at the new position where the value pushed can be added
  • Pop- It is used to get the value from the stack. The value where the stack top is pointing is extracted
  • Peep – It is used to get the value on the top of the stack without extracting it out of the stack
  • Underflow – When we try to pop an item from an empty stack, it results in underflow
  • Overflow – When we try to push the item to the stack which is already full, it results in an overflow

Stack can be implemented with the help of Arrays as well as with the help of Linked List

Implementing Stack with Arrays

Here an array of integers is used and is named stack (see Figure 1).  To add any element in the stack, the function push is used and to extract any value out of the stack, pop function is used. Initially, the subscript top is set to -1 as shown in Figure 1.

Figure 1 – Value of top is -1 initially and stack is empty

When a value is to be pushed, the value of the subscript top is incremented by 1 and the element is added to the array at the location of top. Suppose, user enters value 10 in the stack, it will be stored in the stack array at the subscript location 0 because top which was initially -1 is incremented to value 0 (see Figure 2).

Figure 2 – Value of top is incremented to 0 and first value pushed into stack

Again, when a new value is to be pushed, the value of subscript top is incremented by 1 and the new element is pushed at location specified by top. That is, if value 20 is entered in the stack, it will be stored at subscript location 1 because the value of top which was 0 is incremented to 1 (see Figure 3).

Figure 3 – Value of top is incremented to 1 and second value pushed at subscript 1

Again, if one more value is pushed into the stack, again the value of top is incremented making its value 2 and the value supplied is stored at subscript location 2 in the stack array as shown in Figure  4.

Figure 4 – Value of top incremented to 2 and value pushed at location pointed to by top

Popping Value From Stack

While popping a value from the stack, the element where subscript top is pointing is extracted and the value of  top is decremented by 1. Assuming there are three values in the stack and top is pointing at subscript location 2 as shown in Figure 5.

Figure 5 – Three value present in stack and value of top=2

The value where top is pointing is popped i.e. value 30 is popped and the value of top is decremented by 1 as shown in Figure 6.

Figure 6 – Value of top is decremented by 1 after popping of value

Again, if pop operation is applied, the value where top is pointing will be extracted. Currently, the value of top is 1, so the valued popped from the stack is 20. After popping the value, the value of top will be decremented to 0 as shown in Figure 7.

Figure 7 – Value of top decremented to 0 after popping of value

Again, if pop operation is applied, the value pointed to be top will be popped. The value of top is 0, so the value extracted from stack will be 10. After popping of the last value from the stack, the value of top will be decremented by 1 making it -1. When the value of top becomes -1, it represents that the stack is empty.

‘C’ program for implementing stack with arrays.

/* Implementing stack with Arrays */

# include <stdio.h>

#define max 5

int top=-1;

int stack[max];

main()

{

int n=0,j,p;

while(n!=3)

{

printf(“\n\n1………Pushing an element into the stack\n”);

printf(“2………Popping out an element from the stack\n”);

printf(“3………Quit\n”);

printf(“Enter your choice 1/2/3:”);

scanf(“%d”,&n);

switch(n)

{

case 1:

if(top <max-1)

{

printf(“Enter the value to push “);

scanf(“%d”,&p);

push(p);

printf(“%d Value is pushed\n”,p);

}

else

printf(“Sorry the stack is full\n”);

break;

 

case 2:

j=pop();

if(j==-1)printf(“Stack is empty\n”);

else

printf(“The value popped is %d\n”,j);

break;

}

}

}

 

push(int m)

{

top++;

stack[top]=m;

}

 

int pop()

{

int j;

if(top==-1)return(top);

else

{

j=stack[top];

top–;

return(j);

}

}