Open In App

How to implement stack using priority queue or heap?

Last Updated : 23 May, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

How to Implement stack using a priority queue(using min heap)? Asked In: Microsoft, Adobe. 

Solution: In the priority queue, we assign priority to the elements that are being pushed. A stack requires elements to be processed in the Last in First Out manner. The idea is to associate a count that determines when it was pushed. This count works as a key for the priority queue. So the implementation of stack uses a priority queue of pairs, with the first element serving as the key.

CPP 
#include <bits/stdc++.h>
using namespace std;

int main() {
    // Creating a pair of integers (key, value)
    pair<int, int> pair = make_pair(1, 42);

    // Accessing key and value
    int key = pair.first;
    int value = pair.second;

    // Printing key and value
    cout << "Key: " << key <<endl;
    cout << "Value: " << value <<endl;

    return 0;
}
Java 
import java.util.AbstractMap;
import java.util.Map;

public class Main {
    public static void main(String[] args)
    {
        // Creating a pair of integers (key, value)
        Map.Entry<Integer, Integer> pair
            = new AbstractMap.SimpleEntry<>(1, 42);

        // Accessing key and value
        int key = pair.getKey();
        int value = pair.getValue();

        // Printing key and value
        System.out.println("Key: " + key);
        System.out.println("Value: " + value);
    }
}
Python 
# Creating a pair of integers (key, value)
pair = (1, 42)

# Accessing key and value
key = pair[0]
value = pair[1]

# Printing key and value
print("Key:", key)
print("Value:", value)
C# 
using System;
using System.Collections.Generic;

class Program {
    static void Main(string[] args)
    {
        // Creating a list of KeyValuePairs
        List<KeyValuePair<int, int> > myList
            = new List<KeyValuePair<int, int> >();

        // Adding elements to the list
        myList.Add(new KeyValuePair<int, int>(1, 10));
        myList.Add(new KeyValuePair<int, int>(2, 20));
        myList.Add(new KeyValuePair<int, int>(3, 30));

        // Displaying the elements in the list
        Console.Write("Elements in the list: ");
        foreach(var pair in myList)
        {
            Console.Write($"({pair.Key}, {pair.Value}) ");
        }
        Console.WriteLine();

        // Accessing elements by index
        int firstElement = myList[0].Value;
        int secondElement = myList[1].Value;

        // Modifying an element
        myList[1] = new KeyValuePair<int, int>(2, 25);

        // Removing an element by value
        for (int i = 0; i < myList.Count; i++) {
            if (myList[i].Value == 30) {
                myList.RemoveAt(i);
                break;
            }
        }

        // Displaying the updated list
        Console.Write("Updated list: ");
        foreach(var pair in myList)
        {
            Console.Write($"({pair.Key}, {pair.Value}) ");
        }
        Console.WriteLine();
    }
}
Javascript 
// JavaScript does not have a built-in Pair or Map.Entry class like Java,
// but we can achieve similar functionality using an object literal.

// Main function
function main() {
    // Creating a pair of integers (key, value)
    const pair = { key: 1, value: 42 };

    // Accessing key and value
    const key = pair.key;
    const value = pair.value;

    // Printing key and value
    console.log("Key: " + key);
    console.log("Value: " + value);
}

// Calling the main function
main();

Below is the implementation of the above approach:

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();
    }
}
Java 
// Java program to implement a stack using
// Priority queue(min heap)
import java.util.PriorityQueue;

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;
  PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

  public Stack() {
    cnt = 0;
  }

  public void push(int n) {
    cnt++;
    pq.offer(new int[]{cnt, n});
  }

  public void pop() {
    if (pq.isEmpty()) {
      System.out.println("Nothing to pop!!!");
      return;
    }
    cnt--;
    pq.poll();
  }

  public int top() {
    int[] temp = pq.peek();
    return temp[1];
  }

  public boolean isEmpty() {
    return pq.isEmpty();
  }

  public static void main(String[] args) {
    Stack s = new Stack();
    s.push(3);
    s.push(2);
    s.push(1);
    while (!s.isEmpty()) {
      System.out.println(s.top());
      s.pop();
    }
  }
}

// This code is contributed by adityamaharshi21
Python 
import heapq

# 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.
    def __init__(self):
        self.cnt = 0
        self.pq = []

    def push(self, n):
        # push function increases cnt by 1 and
        # inserts this cnt with the original value.
        self.cnt += 1
        heapq.heappush(self.pq, (-self.cnt, n))

    def pop(self):
        # pops element and reduces count.
        if not self.pq:
            print("Nothing to pop!!!")
        self.cnt -= 1
        return heapq.heappop(self.pq)[1]

    def top(self):
        # 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
        return self.pq[0][1]

    def isEmpty(self):
        # return true if stack is empty
        return not bool(self.pq)

# Driver code
s = Stack()
s.push(1)
s.push(2)
s.push(3)
while not s.isEmpty():
    print(s.top())
    s.pop()
C# 
// C# program to implement a stack using
// Priority queue(min heap)
using System;
using System.Collections.Generic;

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.
    List<int> stack = new List<int>();

    public void Push(int n)
    {
        stack.Add(n);
    }

    public int Pop()
    {
        if (stack.Count == 0)
        {
            Console.WriteLine("Nothing to pop!!!");
            return -1;
        }
        int lastIndex = stack.Count - 1;
        int last = stack[lastIndex];
        stack.RemoveAt(lastIndex);
        return last;
    }

    public int Top()
    {
        if (stack.Count == 0)
        {
            Console.WriteLine("Nothing to get the top!!!");
            return -1;
        }
        return stack[stack.Count - 1];
    }

    public bool IsEmpty()
    {
        return stack.Count == 0;
    }
}

class Program
{
    static void Main(string[] args)
    {
        Stack s = new Stack();
        s.Push(1);
        s.Push(2);
        s.Push(3);
        while (!s.IsEmpty())
        {
            Console.WriteLine(s.Top());
            s.Pop();
        }
    }
}
Javascript 
class Stack {
    constructor() {
        this.stack = [];
    }

    push(n) {
        this.stack.push(n);
    }

    pop() {
        if (this.stack.length === 0) {
            console.log("Nothing to pop!!!");
        }
        return this.stack.pop();
    }

    top() {
        return this.stack[this.stack.length - 1];
    }

    isEmpty() {
        return this.stack.length === 0;
    }
}

// Driver code
let s = new Stack();
s.push(1);
s.push(2);
s.push(3);
while (!s.isEmpty()) {
    console.log(s.top());
    s.pop();
}

Output
3
2
1

Time Complexity: O(log n), Now, as we can see this implementation takes O(log n) time for both push and pop operations. This can be slightly optimized by using fibonacci heap implementation of priority queue which would give us O(1) time complexity for push operation, but pop still requires O(log n) time. 
Auxiliary Space: O(n) where n is size of priority queue



M

Mr. Somesh Awasthi
Improve
Previous Article
Implement a stack using single queue
Next Article
Create a customized data structure which evaluates functions in O(1)

Similar Reads

Should we declare as Queue or Priority Queue while using Priority Queue in Java?
Queue: Queue is an Interface that extends the collection Interface in Java and this interface belongs to java.util package. A queue is a type of data structure that follows the FIFO (first-in-first-out ) order. The queue contains ordered elements where insertion and deletion of elements are done at different ends. Priority Queue and Linked List are
3 min read
What is Priority Queue | Introduction to Priority Queue
A priority queue is a type of queue that arranges elements based on their priority values. Elements with higher priority values are typically retrieved before elements with lower priority values. In a priority queue, each element has a priority value associated with it. When you add an element to the queue, it is inserted in a position based on its
15+ min read
How to implement Priority Queue - using Heap or Array?
A Priority Queue is a data structure that allows you to insert elements with a priority, and retrieve the element with the highest priority. You can implement a priority queue using either an array or a heap. Both array and heap-based implementations of priority queues have their own advantages and disadvantages. Arrays are generally easier to impl
15+ min read
Can we use Simple Queue instead of Priority queue to implement Dijkstra's Algorithm?
What is Dijkstra's Algorithm? Dijkstra's Algorithm is used for finding the shortest path between any two vertices of a graph. It uses a priority queue for finding the shortest path. For more detail, about Dijkstra's Algorithm, you can refer to this article. Why Dijkstra's Algorithm uses a Priority Queue? We use min heap in Dijkstra's Algorithm beca
2 min read
Heap and Priority Queue using heapq module in Python
Heaps are widely used tree-like data structures in which the parent nodes satisfy any one of the criteria given below. The value of the parent node in each level is less than or equal to its children's values - min-heap.The value of the parent node in each level higher than or equal to its children's values - max-heap. The heaps are complete binary
5 min read
Priority Queue using Binary Heap
Priority Queue is an extension of the queue with the following properties:   Every item has a priority associated with it.An element with high priority is dequeued before an element with low priority.If two elements have the same priority, they are served according to their order in the queue.A Binary Heap is a Binary Tree with the following proper
15+ min read
Difference between Binary Heap, Binomial Heap and Fibonacci Heap
Binary Heap:A Binary Heap is a Binary Tree with following properties. It’s a complete binary tree i.e., all levels are completely filled except possibly the last level and the last level has all keys as left as possible. This property of Binary Heap makes them suitable to be stored in an array. A Binary Heap is either Min Heap or Max Heap. In a Min
2 min read
Why is Binary Heap Preferred over BST for Priority Queue?
A typical Priority Queue requires following operations to be efficient. Get Top Priority Element (Get minimum or maximum)Insert an elementRemove top priority elementDecrease Key A Binary Heap supports above operations with following time complexities: O(1)O(Logn)O(Logn)O(Logn) A Self Balancing Binary Search Tree like AVL Tree, Red-Black Tree, etc c
2 min read
Priority Queue using Queue and Heapdict module in Python
Priority Queue is an extension of the queue with the following properties. An element with high priority is dequeued before an element with low priority. If two elements have the same priority, they are served according to their order in the queue. queue.PriorityQueue(maxsize) It is a constructor for a priority queue. maxsize is the number of eleme
3 min read
Why can't a Priority Queue wrap around like an ordinary Queue?
Priority Queue: A priority queue is a special type of queue in which each element is assigned a priority value. And elements are served based on their priority. This means that elements with higher priority are served first. However, if elements with the same priority occur, they will be served in the order in which they were queued. A priority que
3 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox