A stack is a common data structure used in many applications. It is an abstract data type defined not by its data type, but by its operations.
Stack operations are critical to its implementation. We will create a C++ stack using linked-list in this article.
This program demonstrates the implementation of a stack and its operations using simple functions and the program is compiled using Dev-C++ compiler 4.9.9.2 installed on windows 7 64-bit computer.
In this article, you will find the following sections – problem definition, flowchart, program source code and verified output to help you learn to programme effectively. Since the level of the program is difficult, it is for intermediate level learners of C programming language.
Problem Definition
A stack is a linear data structure with a predefined size. It is possible to increase or decrease the stack size, but that depends on the application using the stack data structure.
To build a stack data structure, you can use two methods – an array or a linked -list. A fixed size array can work as an array for a simple data type, however, for a stack that uses dynamic memory allocation, we need a linked-list.
A stack works in a specific way called the LIFO principle –Last in, First out. The last item inserted onto the stack is processed first because items are inserted from the top of the stack and removed from the top first. The stack operations implemented in this program are
push()
Whenever you insert on to stack use push () function and the item cannot be inserted if the stack is full. So this check is performed first.
pop()
It removes the top item of the stack immediately.
display()
This displays the top item of a stack.
Flowchart – Program to Implement a Stack
Program Code – Program to Implement a Stack
/* program to implement stack */
#include <stdio.h>
int stack[100],top,size,choice,i,num;
main()
{
void push();
void pop();
void traverse();
top =0;
/* get the size of stack */
printf("ENTER THE SIZE OF STACK:");
scanf("%d",&size);
/* menu for stack */
i=0;
while(choice != 4)
{
printf("n***MENU***\n");
printf("1.PUSH:\n");
printf("2.POP:\n");
printf("3.DISPLAY:\n");
printf("4.QUIT:\n");
printf("ENTER YOUR CHOICE:");
scanf("%d",&choice);
i++ ;
switch(choice)
{
case 1:
push(stack,top,size);
break;
case 2:
pop(stack,top);
break;
case 3:
traverse();
break;
case 4:
exit(0);
default:
for(i=0;i<35;i++)
printf("_");printf("\n\\n");
printf("WRONG CHOICE:\n");
for(i=0;i<35;i++)
printf("_");printf("\n\\n");
}
}
getch();
return 0;
}
/* PUSH OPERATION */
void push()
{
int i,num;
printf("ENTER THE NUMBER TO PUSH:");
scanf("%d",&num);
if(top == size)
{
for(i=0;i<35;i++)
printf("_");printf("\n\n");
printf("STACK IS FULL!\n");
for(i=0;i<35;i++)
printf("_");printf("\n\n");
}
else
{
top++; stack[top] = num;
}
}
/* POP OPERATION */
void pop()
{
int i,num;
printf("ENTER THE NUMBER TO POP:");
scanf("%d",&num);
if(top == 0)
{
for(i=0;i<35;i++)
printf("_");printf("\n\n");
printf("STACK IS EMPTY:\n");
for(i=0;i<35;i++)
printf("_");printf("\n\n");
}
else
{
num= stack[top];
top--;
}
}
/* Traverse The Stack */
void traverse()
{
int i;
if (top==0)
{
for(i=0;i<35;i++)
printf("_");printf("\n\n");
printf("STACK IS EMPTY:\n");
for(i=0;i<35;i++)
printf("_");printf("\n\n");
}
else
{
for(i=0;i<35;i++)
printf("_");printf("\n\n");
printf("Stack Display\n");
for(i=1;i<=top;i++)
if(i==top)
{
printf("%d at %d -> top\n",stack[i],i);
for(i=0;i<35;i++)
printf("_");printf("\n\n");
}
else
{
printf("%d at %d\n",stack[i],i);
for(i=0;i<35;i++)
printf("_");printf("\n\n");
}
}
}Output
The output of the above program is given in the following figure.
