Stack implementation using C++

Written by

Sonal Moga

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 &lt;&lt;”\n Main Menu”;

    cout &lt;&lt;”\n Adding in stack”;

    cout &lt;&lt;”\n Deleting from stack”;

    cout &lt;&lt;”\n Traverse the stack”;

    cout &lt;&lt;”\n Exit”;

    cout &lt;&lt;”\n\n Enter choice”;

    cin &gt;&gt; choice;

    switch (choice)

    {

    case 1:

        do

        {

            cout &lt;&lt;”Enter the item to be added”;

            cin &gt;&gt; value;

            push(stack, value, top);

            cout &lt;&lt;”\n Do you want to add more item&lt;Y / N&gt; ?”;

            cin &gt;&gt; option;
        }
         

            while (toupper(option) ==’Y’);

        break;

    case 2:

        option =’Y’;

        do

        {

            value = pop(stack, top);

            if (val != -1)

                cout &lt;&lt;”Item deleted from stack is”&lt;&lt; value;

            cout &lt;&lt;”\n Do you want to delete more items&lt;Y / N&gt; ?”;

            cin &gt;&gt; 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 &lt;&lt;”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 &lt; 0)

{

    cout &lt;&lt;”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 &lt;&lt;”items of stack are”;

do

{

    cout &lt;&lt;”\n”&lt;&lt; stack[i];

    i = i - 1;

}

while (i &gt;= 0);

}

Stack implementation using C++