To implement the STACK, a simple one-dimensional array can be used. The size the array is the size of the STACK. Instead of using the normal index to access the elements of the array a special index TOP is used to access the individual elements of the array. Initially TOP is stored with 0, considering the lower bound of array as 1. If the lower bound of the array is other than 1, suppose say LB, then LB-1, may be used as TOP value. STACK may be treated as name of the array.

If any insertion, PUSH is to be done on the STACK, TOP is incremented by one and the element is stored at TOP i.e. TOP<--TOP+1 and STACK [TOP]<--ITEM, ITEM is the item to be inserted by 1 and the ITEM is placed at TOP. While PUSHing the ITEM the TOP is checked for size, if the TOP is equal to the STACK size N, then no more PUSH operations are possible, the STACK is full. The ‘overflow’ occurs.

If any deletion, POP, is to be done from the STACK, the item pointed by TOP is stored in a variable, and the TOP is decremented by 1 and the variable is returned. Similarly further POP operations are done. While POPping the STACK is empty and ‘underflow’, occurs.

To implement the STACK using one-dimensional array the following PUSH and POP operations’ algorithms are used.

Algorithm for PUSH:

PUSH (STACK,TOP,N,ITEM)

[STACK is name of the array, ITEM is the data to be PUSHed, TOP is the current index of STACK and N is the size of STACK]

If TOP=N Then;

write: ’Overflow’; Exit.

[End of If]

TOP<--TOP+1

STACK[TOP]<--ITEM

Exit.

Function in C to implement PUSH operation:

void push (int stack[],int n,int *top, int item)

{

if(top= =n-1)

{

printf(“Over flow”); exit(0);

}

top++; stack[top]=item;

}

Algorithm for POP operation:

POP (STACK, TOP)

[STACK is name of the array and TOP is the current index]

If TOP=O Then;

Write: ’Underflow’; Exit.

[End of If]

ITEM<--STACK[TOP]

TOP<--TOP-1

Return ITEM

Exit.

Function in C to implement POP operation:

int pop (int stack[], int *top)

{

int item;

if(top= =1)

{

printf(“Under flow”);

exit(0);

}

item=stack[top];

top--;

return item;

}

## 0 comments:

## Post a Comment