如何使用优先级队列或堆实现堆栈？-yiteyi-C++库

如何使用优先级队列（使用最小堆）实现堆栈？。

null

问：微软，Adobe。

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

解决方案：

在优先级队列中，我们为被推送的元素分配优先级。堆栈要求以后进先出的方式处理元素。这样做的目的是关联一个计数，以确定推送的时间。此计数用作优先级队列的密钥。

因此，堆栈的实现使用一个成对的优先级队列，第一个元素作为密钥。

pair < int , int > (key, value)

请参见下图，以便更好地理解

图片[1]-如何使用优先级队列或堆实现堆栈？-yiteyi-C++库

下面是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

现在，正如我们所看到的，这个实现对于push和pop操作都需要O（logn）时间。这可以通过使用优先级队列的斐波那契堆实现来稍微优化，这将为推送操作提供O（1）时间复杂度，但pop仍然需要O（logn）时间。

本文由 Somesh Awasthi先生 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章