IMPLEMENTING STACK USING PRIORITY_QUEUE - Using Max Heap

This is the implementation of stack data-structure using a priority queue(Max Heap).

The idea is to use an extra field called count which acts as the priority to the elements that are being pushed. 

As we keep on inserting new elements, the count field gets incremented(for every push) and the max heap is built based on that count value.

The element which is pushed at the end will be in the top of the max heap because it will have the maximum count.
We know that STACK follows LAST IN FIRST OUT.

Remember that the priority here is the count value(order in which the element inserted) and not the number itself.

Source Code :

       


///implementing stack using priority queue
#include<bits/stdc++.h>
using namespace std;
#define SIZE 100
int current_size = 0,counts =0;


struct prior_queue{
    int num;
    int count;
}p[SIZE];


void push(int num){
    

    ++counts;
    int hole = ++current_size;
    

    for(; hole > 1 && counts > p[hole/2].count ; hole /= 2){
        p[hole].num = p[hole/2].num;
        p[hole].count = p[hole/2].count;
    }
    

    p[hole].num = num;
    p[hole].count = counts;
}


void perculate_down(int hole){
    

    int temp_num  = p[hole].num;
    int temp_count = p[hole].count;
    int child;
    

    for( ;hole*2 <= current_size; hole = child){
        child = hole * 2;
        if(child != current_size && p[child+1].count > p[child].count){
            child++;
        }
        if(p[child].count > temp_count){
            p[hole].count = p[child].count;
            p[hole].num = p[child].num;
        }
        else
            break;
    }
    

    p[hole].num = temp_num;
    p[hole].count = temp_count;
}


int pop(){
    

    if(current_size < 1){
        cout << "Cannot Be Dequeued\n";
        return -1;
    }
    

    int x = p[1].num;
    p[1] = p[current_size--];
    perculate_down(1);
    

    return x;
}


void display(){
    for(int i = 1; i <= current_size; i++){
        cout<<"Number :"<<p[i].num<<"  Count: "<<p[i].count<<"\n";
    }
}


int main(){
    

    int num,choice,x;
    cout << "1.PUSH\n2.POP\n3.DISPLAY\n4.EXIT\n";
    cin >> choice;
    

    while(choice != 4){
            switch(choice){
                case 1: cout << "\nEnter the number";
                        if(current_size < 1){
                            counts = 0;
                        }
                        cin >> num;
                        push(num);
                        break;
                case 2: x = pop();
                        if(x == -1){
                            break;
                        }
                        cout << x << "is POPPED\n";
                        break;
                case 3: display();
                        break;
            }
            cout << "1.PUSH\n2.POP\n3.DISPLAY\n4.EXIT\n";
            cin >> choice;
    }
    

    return 0;
}