¿Cómo implementar la pila usando la cola de prioridad o el montón?

¿Cómo implementar la pila usando una cola de prioridad (usando un montón mínimo)? Preguntado en: Microsoft, Adobe. 

Solución: En la cola de prioridad, asignamos prioridad a los elementos que se están empujando. Una pila requiere que los elementos se procesen de la manera Último en entrar, Primero en salir. La idea es asociar un conteo que determine cuándo fue empujado. Este conteo funciona como una clave para la cola de prioridad. Entonces, la implementación de stack usa una cola de prioridad de pares, con el primer elemento sirviendo como clave.

pair <int, int> (key, value)

Vea la imagen de abajo para entender mejor 

 A continuación se muestra la implementación de la idea en C++. 

// C++ program to implement a stack using
// Priority queue(min heap)
#include<bits/stdc++.h>
using namespace std;
 
typedef pair<int, int> pi;
 
// User defined stack class
class Stack{
     
    // cnt is used to keep track of the number of
    //elements in the stack and also serves as key
    //for the priority queue.
    int cnt;
    priority_queue<pair<int, int> > pq;
public:
    Stack():cnt(0){}
    void push(int n);
    void pop();
    int top();
    bool isEmpty();
};
 
// push function increases cnt by 1 and
// inserts this cnt with the original value.
void Stack::push(int n){
    cnt++;
    pq.push(pi(cnt, n));
}
 
// pops element and reduces count.
void Stack::pop(){
    if(pq.empty()){ cout<<"Nothing to pop!!!";}
    cnt--;
    pq.pop();
}
 
// returns the top element in the stack using
// cnt as key to determine top(highest priority),
// default comparator for pairs works fine in this case
int Stack::top(){
    pi temp=pq.top();
    return temp.second;
}
 
// return true if stack is empty
bool Stack::isEmpty(){
    return pq.empty();
}
 
// Driver code
int main()
{
    Stack* s=new Stack();
    s->push(1);
    s->push(2);
    s->push(3);
    while(!s->isEmpty()){
        cout<<s->top()<<endl;
        s->pop();
    }
}

3
2
1

Ahora, como podemos ver, esta implementación toma tiempo O (log n) para las operaciones push y pop. Esto se puede optimizar ligeramente mediante el uso de la implementación del montón de fibonacci de la cola de prioridad que nos daría una complejidad de tiempo O (1) para la operación de inserción, pero pop aún requiere un tiempo O (log n). 

Este artículo es una contribución del Sr. Somesh Awasthi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.