Max Stack

class EnhancedStack {
private:
    stack<pair<int, int>> elementStack;
    priority_queue<pair<int, int>> maxHeap;
    unordered_set<int> deletedIndices;
    int indexCounter;

public:
    EnhancedStack() { indexCounter = 0; }

    void push(int value) {
        elementStack.push({value, indexCounter});
        maxHeap.push({value, indexCounter});
        indexCounter++;
    }

    int pop() {
        while (deletedIndices.count(elementStack.top().second)) {
            elementStack.pop();
        }
        auto topElement = elementStack.top();
        elementStack.pop();
        deletedIndices.insert(topElement.second);
        return topElement.first;
    }

    int top() {
        while (deletedIndices.count(elementStack.top().second)) {
            elementStack.pop();
        }
        return elementStack.top().first;
    }

    int getMax() {
        while (deletedIndices.count(maxHeap.top().second)) {
            maxHeap.pop();
        }
        return maxHeap.top().first;
    }

    int popMax() {
        while (deletedIndices.count(maxHeap.top().second)) {
            maxHeap.pop();
        }
        auto maxElement = maxHeap.top();
        maxHeap.pop();
        deletedIndices.insert(maxElement.second);
        return maxElement.first;
    }
};

The provided C++ class, EnhancedStack, implements a stack data structure that supports advanced operations like retrieving and removing the maximum value in the stack. This is achieved by combining a stack, a max heap, and a hash set to coordinate elements and manage indices, ensuring efficient operations.

Key functionalities of the EnhancedStack class include:

• Push Operation: Adds a new value to the stack along with a unique index that increments with each push. This value-index pair is added both to the stack and to a max heap to keep track of the maximum efficiently.

• Pop Operation: Removes the top element from the stack. If the top element has been marked as deleted (information stored in a hash set), it skips those elements. Marks the removed element as deleted.

• Top Operation: Returns the top value of the stack without removing it. It skips the elements marked as deleted.

• Get Max Operation: Retrieves the maximum value currently in the stack by using the max heap. It ensures that it doesn't consider any elements that have been removed but not yet cleaned up from the max heap.

• Pop Max Operation: Removes and returns the maximum value from the stack. It first locates the max item from the heap, removes it, and marks its index as deleted.

These operations are made efficient with the combination of:

• A stack (elementStack) that handles the typical push and pop operations with appended unique indices for identifying each element.
• A priority queue (maxHeap) that allows for the quick retrieval of the maximum value.
• A hash set (deletedIndices) that keeps track of indices of elements that have been removed from the stack but might still be present in the heap.

This structure makes the EnhancedStack particularly suitable for applications needing frequent access to the maximum element of the stack in addition to regular stack operations. It offers a balanced trade-off between time complexity and additional space usage, making operations relatively efficient across different scenarios.

class EnhancedMaxStack {
    private Stack<int[]> mainStack;
    private PriorityQueue<int[]> maxHeap;
    private HashSet<Integer> deletedElements;
    private int sequence;

    public EnhancedMaxStack() {
        mainStack = new Stack<>();
        maxHeap = new PriorityQueue<>((x, y) -> y[0] - x[0] == 0 ? y[1] - x[1] : y[0] - x[0]);
        deletedElements = new HashSet<>();
    }

    public void push(int value) {
        mainStack.push(new int[] { value, sequence });
        maxHeap.offer(new int[] { value, sequence });
        sequence++;
    }

    public int pop() {
        while (deletedElements.contains(mainStack.peek()[1])) {
            mainStack.pop();
        }
        int[] element = mainStack.pop();
        deletedElements.add(element[1]);
        return element[0];
    }

    public int top() {
        while (deletedElements.contains(mainStack.peek()[1])) {
            mainStack.pop();
        }
        return mainStack.peek()[0];
    }

    public int peekMax() {
        while (deletedElements.contains(maxHeap.peek()[1])) {
            maxHeap.poll();
        }
        return maxHeap.peek()[0];
    }

    public int popMax() {
        while (deletedElements.contains(maxHeap.peek()[1])) {
            maxHeap.poll();
        }
        int[] maxElement = maxHeap.poll();
        deletedElements.add(maxElement[1]);
        return maxElement[0];
    }
}

The Max Stack implemented in Java allows for managing a stack data structure that supports operations to push and pop items like a regular stack but also enables retrieving and removing the maximum value efficiently. The EnhancedMaxStack class utilizes a combination of a Stack and a PriorityQueue to achieve these functionalities. Here is a breakdown of its key components and methods:

• Data Structures:

  • A Stack<int[]> mainStack to hold the element and its unique sequence number.
  • A PriorityQueue<int[]> maxHeap to track max elements using a comparator for descending order by values and tie-breaking by the recent sequence.
  • A HashSet<Integer> deletedElements to remember sequence numbers of elements that have been removed from the main stack but not yet from the heap.

• Constructor: Initializes the mainStack, maxHeap, and deletedElements along with a sequence number to ensure every element pushed onto the stack gets a unique identifier.

• push(int value): Inserts elements into both the stack and the heap with an incremented sequence number.

• pop(): Pops the element on top of the main stack out, ensuring it hasn't been marked as deleted (due to a max pop operation). Returns the value of the popped element.

• top(): Returns the top value of the main stack without popping it, skipping over any elements marked as deleted.

• peekMax(): Provides the maximum current value from the max heap, ensuring the heap's top hasn't been removed due to a previous operation.

• popMax(): Retrieves and removes the maximum element from the heap. Marks this element in the deleted set to indicate its removal when encountered in the main stack.

With these operations, the class provides a robust structure for handling complex stack operations efficiently while keeping track of maximums in constant time, ideal for performance-sensitive applications where frequent access to the maximum stack value is needed.

import heapq

class MaximumStack:
    def __init__(self):
        self.priority_queue = []
        self.index = 0
        self.stack_container = []
        self.deleted_indices = set()

    def push(self, value: int) -> None:
        heapq.heappush(self.priority_queue, (-value, -self.index))
        self.stack_container.append((value, self.index))
        self.index += 1

    def pop(self) -> int:
        while self.stack_container and self.stack_container[-1][1] in self.deleted_indices:
            self.stack_container.pop()
        element, idx = self.stack_container.pop()
        self.deleted_indices.add(idx)
        return element

    def top(self) -> int:
        while self.stack_container and self.stack_container[-1][1] in self.deleted_indices:
            self.stack_container.pop()
        return self.stack_container[-1][0]

    def peekMax(self) -> int:
        while self.priority_queue and -self.priority_queue[0][1] in self.deleted_indices:
            heapq.heappop(self.priority_queue)
        return -self.priority_queue[0][0]

    def popMax(self) -> int:
        while self.priority_queue and -self.priority_queue[0][1] in self.deleted_indices:
            heapq.heappop(self.priority_queue)
        value, index = heapq.heappop(self.priority_queue)
        self.deleted_indices.add(-index)
        return -value

The solution implements a custom data structure called MaximumStack using Python 3, which combines the functionality of a stack and a priority queue to support efficient retrieval of maximum values. Key functions and their roles are:

• Initialization (__init__): Set up the data structures required for the stack and priority queue operations. Utilize a list for the stack operations (stack_container), a heap-based priority queue (priority_queue) for tracking maximum values efficiently, and a set (deleted_indices) to manage lazy deletions.

• Push (push): Adds a new item to the stack and priority queue. The item gets added to stack_container with a unique index, and also as a negatively valued tuple in priority_queue to maintain maximum values at the top.

• Pop (pop): Removes and returns the top element of the stack. It handles elements flagged for deletion (via deleted_indices) by skipping them until the valid top element is found.

• Top (top): Retrieves the top value of the stack without removing it, accounting for lazily deleted elements.

• Peek Maximum (peekMax): Provides the current maximum value by checking the top of the priority queue, adjusting for any elements marked as deleted.

• Pop Maximum (popMax): Removes and returns the maximum element in the stack and marks it in the deleted_indices to ensure the integrity of stack order upon subsequent operations.

This structure ensures that operations on getting maximum values are efficient, addressing the common performance drawbacks in typical stack implementations when integrated with max retrieval operations. The use of a heap-based priority queue (min-heap with negative values for inversion) alongside lazy deletion strategy (deleted_indices) optimizes the management and retrieval of maximum values while maintaining the last-in-first-out (LIFO) order of the stack. The implementation is a robust solution for scenarios requiring frequent access to maximum elements alongside regular stack operations.