---

Implementation of stack

Stack can be easily implemented using an Array or a Linked List. Arrays are quick, but are limited in size and Linked List requires overhead to allocate, link, unlink, and deallocate, but is not limited in size. Here we will implement Stack using array.

Array Implementation of Stacks

Implementation of stack using array avoids pointers and is probably the more popular solution. The only potential hazard with this strategy is that we need to declare an array size ahead of time. Generally this is not a problem, because in typical applications, even if there are quite a few stack operations, the actual number of elements in the stack at any time never gets too large. It is usually easy to declare the array to be large enough without wasting too much space. If this is not possible, then a safe course would be to use a linked list implementation.

If we use an array implementation, the implementation is trivial. Associated with each stack is the top of stack, top, which is -1 for an empty stack (this is how an empty stack is initialized). To push some element d onto the stack, we increment top and then set STACK[tos] = d, where STACK is the array representing the actual stack. To pop, we set the return value to STACK[top] and then decrement top. Of course, since there are potentially several stacks, the STACK array and top are part of one structure representing a stack. It is almost always a bad idea to use global variables and fixed names to represent this (or any) data structure, because in most real-life situations there will be more than one stack. When writing your actual code, you should attempt to follow the model as closely as possible, so that no part of your code, except for the stack routines, can attempt to access the array or top-of-stack variable implied by each stack. This is true for all ADT operations. Modern languages such as Ada and C++ can actually enforce this rule.

Implementation Steps

push() Function:

A simple algorithm for Push operation can be derived as follows

/* Definition of the push function */

void push(int s[], int d)
{
	if(top ==(size-1)) // Checking for overflow
		flag = 0;
	else
	{
		flag = 1;
		++top;	
		s[top] = d;
	}
}

pop() Function:

A simple algorithm for Pop operation can be derived as follows

/* Definition of the pop function */

int pop(int s[])
{
	int popped_element;
	if(top == -1)  // Cheking for underflow 
	{
		popped_element = 0;
		flag = 0;
	}
	else
	{
		flag = 1;
		popped_element = s[top];
		--top;
	}
	return (popped_element);
}

dispaly() Function to show the list

/* Definition of the display function */

void display(int s[])
{
	int i;
	if(top == -1)
	{
		printf("\n Stack is empty");
	}
	else
	{
		for(i = top; i >= 0; --i)
			printf("\n %d", s[i] );
	}
}

Full Code to Implementaion the stack using array

Implementation of this algorithm in C, is very easy. See the following code ?

/* IMPLEMENTATION OF THE STACK USING ARRAYS */
/* STACK_A.C */

# include<stdio.h>
# include<string.h>
# include<ctype.h>

# define size  100


int top = -1;
int flag = 0;
int stack[size];

void push(int *, int);
int pop(int *);
void display(int *);

/* Definition of the push function */

void push(int s[], int d)
{
	if(top ==(size-1))
		flag = 0;
	else
	{
		flag = 1;
		++top;	
		s[top] = d;
	}
}

/* Definition of the pop function */

int pop(int s[])
{
	int popped_element;
	if(top == -1)
	{
		popped_element = 0;
		flag = 0;
	}
	else
	{
		flag = 1;
		popped_element = s[top];
		--top;
	}
	return (popped_element);
}

/* Definition of the display function */

void display(int s[])
{
	int i;
	if(top == -1)
	{
		printf("\n Stack is empty");
	}
	else
	{
		for(i = top; i >= 0; --i)
			printf("\n %d", s[i] );
	}
}

/* Function main */

void main()
{

	int  data;
	char choice;
	int q = 0;
	int top = -1;

	do
	{
		printf(" \nPush->i Pop->p Quit->q:");
		printf("\nInput the choice : ");
		do
		{
			choice = getchar();
			choice =tolower(choice);
		}while(strchr("ipq",choice)==NULL);
		printf("Your choice is: %c",choice);

		switch(choice)
		{
		case 'i' :
			printf("\n Input the element to push:");
			scanf("%d", &data);
			push(stack, data);
			if(flag)
			{
				printf("\n After inserting ");
				display(stack);
				if(top == (size-1))
					printf("\n Stack is full");
			}
			else
				printf("\n Stack overflow after pushing");
			break;

		case 'p' : 
			data = pop(stack);
			if(flag)
			{
				printf("\n Data is popped: %d", data);
				printf("\n Rest data in stack is as follows:\n");

				display(stack);
			}
			else
				printf("\n Stack underflow" );
			break;
		case 'q': 
			q = 1;
		}
	} while(!q);
}

 

Push->i Pop->p Quit->q:
Input the choice : i
Your choice is: i
 Input the element to push:12

 After inserting
 12
Push->i Pop->p Quit->q:
Input the choice : i
Your choice is: i
 Input the element to push:13

 After inserting
 13
 12
Push->i Pop->p Quit->q:
Input the choice : i
Your choice is: i
 Input the element to push:14

 After inserting
 14
 13
 12
Push->i Pop->p Quit->q:
Input the choice : p
Your choice is: p
 Data is popped: 14
 Rest data in stack is as follows:

 13
 12
Push->i Pop->p Quit->q:
Input the choice : q
Your choice is: qPress any key to continue . . .

---