Stack implementation using C++
Stack implementation
As we have discussed earlier, Stacks are linear data structures and follow mainly two operations, Push & Pop. Addition in a stack is called Push and removal of an entity from the stack is called Pop.
Once we know the details of stack operations, we can understand its implementation in C++ as well. Let’s look at the algorithms for various operations in Stack.
Algorithm for Pushing an item in Stack
Pushing or inserting an element in a stack involves shifting of elements as the new element can be inserted at the top only. In case of the stack being Full and no new element can be inserted, the condition is called Overflow.
/* assume that stack can hold a max of N elements*/
top = -1
read item /*item to be pushed */
If(top == N - 1) then
{
print“ overflow!!!” /*if top is end of the array */
}
Else
{
top = top + 1 /*increment top to make new item hold top position */
Stack[top] = item
}
End
Algorithm for Popping an item from Stack
Popping or deletion of an entity from a stack will remove the topmost element of the stack. In a case where there is no item in the stack (stack is empty) making removal of item impossible, the condition is called Underflow.
If top == -1 then
{
Print“ underflow!!!”
Exit from program
}
Else
{
Print stack(top)
top = top + 1
/*top is moved making the top element inaccessible which can be considered a deletion*/
}
End
Program for addition and deletion in a stack
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX 100 //maximum length of stack
char stack[MAX]; //declaring array as global variable
int top;
void push(char stack[], char value, int& top); //add stack
void pop(char stack[], int& top); //delete stack
void show_Stack(char stack[], int top); //show stack
void main()
{
int choice;
char value;
char option =’Y’;
top = -1; //initializing the stack
clrscr();
do
{
cout <<”\n Main Menu”;
cout <<”\n Adding in stack”;
cout <<”\n Deleting from stack”;
cout <<”\n Traverse the stack”;
cout <<”\n Exit”;
cout <<”\n\n Enter choice”;
cin >> choice;
switch (choice)
{
case 1:
do
{
cout <<”Enter the item to be added”;
cin >> value;
push(stack, value, top);
cout <<”\n Do you want to add more item<Y / N> ?”;
cin >> option;
}
while (toupper(option) ==’Y’);
break;
case 2:
option =’Y’;
do
{
value = pop(stack, top);
if (val != -1)
cout <<”Item deleted from stack is”<< value;
cout <<”\n Do you want to delete more items<Y / N> ?”;
cin >> option;
} while (toupper(option) ==’Y’);
break;
case 3:
show_Stack(stack, top);
break;
case 4:
exit(0);
}
}
while (choice != 4);
}
//to add item in the stack
void push(char stack[], char value, int& top)
{
If(top == MAX)
{
cout <<”Stack is FULL”;
}
else
{
top = top + 1;
stack[top] = value;
}
}
//to delete an item from stack
char pop(char stack[], int& top)
{
char value;
if (top < 0)
{
cout <<”stack is EMPTY”;
value = -1;
}
else
{
value = stack[top];
top = top - 1;
}
return (value);
}
//to show items of stack
void show_Stack(char stack[], int top)
{
int i;
i = top;
clrscr();
cout <<”items of stack are”;
do
{
cout <<”\n”<< stack[i];
i = i - 1;
}
while (i >= 0);
}