Stack Implementation using Array in C++

Definition

Stack is a linear data structure that consists of an ordered collection of elements with two principles.

1. Push :- That adds an element to the collection.
2. Pop :- That removes the most recent element from the collection.

In stack, the elements are inserted to and removed from only one end called Top of Stack (TOS). The items in the stack are homogenous.

As all the deletion and insertion is done from the TOS, the last added elements will be the first to be removed from the stack. Hence, the stack is also called the Last – in – First – out (FIFO) data structure. Eg:- Plates in a marriage party => Fresh plates are pushed onto the top and poped from the top.

Top Varying Method

Algorithm

1. Declare and initialize necessary variables
   • top =- 1, MAXSIZE etc.
2. For push operation
   • If top == MAXSIZE -1
     • print “Stack is full / stack overflow”
   • else
     • top = top + 1
     • read item from user
     • stack[top] = item
3. For next push operation goto step 2
4. For pop operation
   • If top == -1
     • print “Stack is empty / stack underflow”
   • else
     • item = stack[top]
     • top = top -1
     • dispaly item
5. For next pop operation goto step 4
6. Stop

Code in C++

#include<iostream>
#include<stdio.h>
#include<conio.h>
#define MAXSIZE 5

using namespace std;

class Stack {
    private: 
    int top, st[MAXSIZE], item;

    public:
    Stack():top(-1) {}

    void push();
    void pop();
    void display();

};

void Stack::push() {
    if(top == MAXSIZE-1) {
        cout<<"Stack is full / stack overflow";
    }
    else {
        top++;
        cout<<"Enter item for stack: ";
        cin>>item;
        st[top] = item;
    }
}

void Stack::pop() {
    if(top == -1) {
        cout<<"Stack is empty/stack underflow";
    }
    else {
        item = st[top];
        cout<<"Poped item = "<<item<<endl;
        top--;
    }
}

void Stack::display() {
    cout<<endl;
    for(int i = top; i>=0; i--) {
        cout<<st[i]<<endl;
    }
    cout<<endl;
}

void mainMenu() {
    cout<<"Stack operation: "<<endl;
    cout<<"1. Push \n2. Pop \n3. Display \n4. Exit"<<endl;
}

int main() {
    Stack s;
    bool decision = true;
    int choice;
    while(decision) {
        mainMenu();
        cout<<"Enter choice: "<<endl;
        cin>>choice;
        switch(choice) {
            case 1: s.push();
                break;
            case 2: s.pop();
                break;
            case 3: s.display();
                break;
            case 4: decision = false;
                break;
            default: cout<<"Enter a valid choice"<<endl;
        }
    }
    getch();
    return 0;
}

Bottom Varying Method / Top Fixed Method

Algorithm

1. Declare and initialize necessary variables
   • bos = 0, MAXSIZE etc.
2. For push operation
   • If bos == MAXSIZE
     • print “Stack is full / stack overflow”
   • else
     • insert new element of making vacant space at stack[0]
     • i.e. for(i=bos; i>0; i–)
       • stack[i] = stack[i-1]
     • stack[0] = data
     • bos++
3. For next push operation goto step 2
4. For pop operation
   • If bos == 0
     • print “Stack is empty / stack underflow”
   • else
     • extract item from stack[0], decrement bos and refill empty space by shifting each item by step 1
     • i.e. item = stack[0]
     • bos–
     • for(i=0; i<bos; i++)
       • stack[i] = stack[i+1]
     • return item
5. For next pop operation goto step 4
6. Stop

Code in C++

#include<iostream>
#include<stdio.h>
#include<conio.h>
#define MAXSIZE 5

using namespace std;

class Stack {
    private: 
    int bos, st[MAXSIZE], item;

    public:
    Stack():bos(0) {}

    void push();
    void pop();
    void display();

};

void Stack::push() {
    if(bos == MAXSIZE) {
        cout<<"Stack is full / stack overflow";
    }
    else {
        cout<<"Enter item for stack: ";
        cin>>item;
        for(int i=bos; i>0; i--)
            st[i] = st[i-1];
        st[0] = item;
        bos++;
    }
}

void Stack::pop() {
    if(bos == 0) {
        cout<<"Stack is empty/stack underflow";
    }
    else {
        item = st[0];
        bos--;
        for(int i=0; i<bos; i++)
            st[i] = st[i+1];
        cout<<"Poped item = "<<item<<endl;
    }
}

void Stack::display() {
    cout<<endl;
    for(int i = 0; i<bos; i++) {
        cout<<st[i]<<endl;
    }
    cout<<endl;
}

void mainMenu() {
    cout<<"Stack operation: "<<endl;
    cout<<"1. Push \n2. Pop \n3. Display \n4. Exit"<<endl;
}

int main() {
    Stack s;
    bool decision = true;
    int choice;
    while(decision) {
        mainMenu();
        cout<<"Enter choice: "<<endl;
        cin>>choice;
        switch(choice) {
            case 1: s.push();
                break;
            case 2: s.pop();
                break;
            case 3: s.display();
                break;
            case 4: decision = false;
                break;
            default: cout<<"Enter a valid choice"<<endl;
        }
    }
    getch();
    return 0;
}