Implement stack using priority queue

Problem

Design and implement a stack using a priority queue. The stack should support the following operations:

push(x): Push element x onto the stack.
pop(): Removes the element on top of the stack and returns it.
top(): Get the top element.
isEmpty(): Return whether the stack is empty.

Recall that a heap has the following operations:

push(item), which adds a new key to the heap
pop(), which removes and returns the max value of the heap

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: 
Operations: ["push(1)", "push(2)", "top()", "pop()", "isEmpty()"]
Output: 
[null, null, 2, 2, false]
Explanation: 
- push(1) adds 1 to the stack with priority 1.
- push(2) adds 2 to the stack with priority 2.
- top() returns the current top element, which is 2.
- pop() removes and returns the current top element, which is 2.
- isEmpty() returns false as the stack is not empty.

Solution

Method 1 - Using PriorityQueue

A stack follows the Last In First Out (LIFO) principle. In contrast, a priority queue or heap orders elements by their priority.

To emulate stack behavior using a priority queue, we can assign each element a priority that increases with every push operation. This priority serves as a timestamp or sequence number, ensuring the most recently added element is given the highest priority.

By using a priority queue where each element is associated with a priority level that increases as we push elements, we can simulate stack behavior:

Each push operation will associate the pushed element with an increasing priority (timestamp or sequence number).
The pop operation will then remove the element with the highest priority (most recent timestamp).
The top operation will peek at the element with the highest priority.

Here is the approach:

Assigning Priority: Each push operation increments a counter, which acts as the priority for the pushed element. The priority helps determine the order of elements in the priority queue.
Heap Structure: Utilize a max-heap to store pairs of (priority, element). If a max-heap is not available, a min-heap with negative priorities can serve the same purpose.
Push Operation: Insert the element into the priority queue with the current counter as its priority, then increment the counter.
Pop Operation: Remove and return the element with the highest priority.
Top Operation: Peek at the element with the highest priority.
isEmpty Operation: Check if the priority queue is empty.

graph TD
	A[Push 1, 2, 3] --> |Enqueue Operation increases priority by 1 for each push| B[(val = 3, priority = 3 \n val = 2, priority = 2 \n val = 1, priority = 1)]
	B --> |Dequeue Operation pops element by highest priority| C[3,2,1]
style B fill:#96f,stroke:#333,stroke-width:4px;
style C fill:#f96,stroke:#333,stroke-width:4px;

Here is the pseudocode:

1
2
3
4
5
6
7
8
9


// Stack implementation using priority queue
class Stack {
    class Element { int priority; Key element; };
    MaxPriorityQueue<Element> queue;
    int top_priority = 0;

    void push(Key x) { queue.push(Element(top_priority++, x)); }
    Key pop() { top_priority--; return queue.pop().element; }
};

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


public class Solution {
    private static class Element {
        int value;
        int priority;

        Element(int value, int priority) {
            this.value = value;
            this.priority = priority;
        }
    }

    private PriorityQueue<Element> maxHeap;
    private int counter;

    public Solution() {
        maxHeap = new PriorityQueue<>(Comparator.comparingInt(e -> -e.priority));
        counter = 0;
    }

    public void push(int x) {
        maxHeap.add(new Element(x, counter++));
    }

    public int pop() {
        return maxHeap.poll().value;
    }

    public int top() {
        return maxHeap.peek().value;
    }

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

    public static void main(String[] args) {
        Solution stack = new Solution();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.top());     // Outputs: 2
        System.out.println(stack.pop());     // Outputs: 2
        System.out.println(stack.isEmpty()); // Outputs: false
        stack.push(5);
        System.out.println(stack.pop());     // Outputs: 5
        System.out.println(stack.isEmpty()); // Outputs: true
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution:
    def __init__(self) -> None:
        self.heap: List[tuple] = []
        self.counter: int = 0

    def push(self, x: int) -> None:
        heapq.heappush(self.heap, (-self.counter, x))
        self.counter += 1

    def pop(self) -> int:
        return heapq.heappop(self.heap)[1]

    def top(self) -> int:
        return self.heap[0][1]

    def isEmpty(self) -> bool:
        return len(self.heap) == 0

# Example usage
stack = Solution()
stack.push(1)
stack.push(2)
print(stack.top())     # Outputs: 2
print(stack.pop())     # Outputs: 2
print(stack.isEmpty()) # Outputs: False
stack.push(5)
print(stack.pop())     # Outputs: 5
print(stack.isEmpty()) # Outputs: True

Complexity

⏰ Time complexity: O(log n), for push, pop, and top, where n is the number of elements in the stack
🧺 Space complexity: O(n), due to storing elements and their priorities in the heap.

Problem#

Examples#

Example 1:#

Solution#

Method 1 - Using PriorityQueue#

Code#

Complexity#