Min Stack

class MinStack {
private:
    std::stack<int> dataStack;
    std::stack<std::pair<int, int>> auxStack;

public:
    MinStack() {}

    void push(int value) {
        dataStack.push(value);

        if (auxStack.empty() || value < auxStack.top().first) {
            auxStack.push({value, 1});
        } else if (value == auxStack.top().first) {
            auxStack.top().second++;
        }
    }

    void pop() {
        if (dataStack.top() == auxStack.top().first) {
            auxStack.top().second--;
        }

        if (auxStack.top().second == 0) {
            auxStack.pop();
        }

        dataStack.pop();
    }

    int top() { return dataStack.top(); }

    int min() { return auxStack.top().first; }
};

The problem "Min Stack" involves creating a stack data structure that supports pushing, popping, and retrieving the smallest element in constant time. The provided C++ solution utilizes two stacks: one for storing all the elements and another auxiliary stack to keep track of the minimum elements.

Here's how the stacks function in the implemented Code:

• Data Stack: This stack holds all the elements of the stack.
• Auxiliary Stack: This is used to store the minimum elements. Each element is a pair where
  • the first part is the minimum value and
  • the second part is the count of how many times this minimum value occurs in the dataStack.

Functions and their operations:

1. Constructor (MinStack() {}): Initializes the stacks.

2. push(int value):

   • The value is pushed onto the dataStack.
   • If the auxStack is empty or the incoming value is less than the current minimum, a new pair is pushed onto the auxStack with the value and a count of one.
   • If the incoming value equals the current minimum, increment the count for that value in the top pair of auxStack.

3. pop():

   • Checks if the top value of dataStack equals the current minimum (top of auxStack).
   • If so, decrements the count of the top pair in the auxStack.
   • If the count of this minimum value in the auxStack becomes zero, it removes the top of auxStack.
   • The value is popped from the dataStack.

4. top():

   • Returns the top element of the dataStack without removing it.

5. min():

   • Returns the minimum element currently in the stack, by accessing the first value of the pair on top of the auxStack.

With this solution, each stack operation (push, pop, top, min) operates in constant time, O(1), which is efficient for scenarios involving frequent stack operations combined with frequent minimum value retrievals.

class MinStack {
    private Stack<Integer> mainStack = new Stack<>();
    private Stack<int[]> minimumStack = new Stack<>();

    public MinStack() {}

    public void push(int value) {
        mainStack.push(value);
        if (minimumStack.isEmpty() || value < minimumStack.peek()[0]) {
            minimumStack.push(new int[] { value, 1 });
        } else if (value == minimumStack.peek()[0]) {
            minimumStack.peek()[1]++;
        }
    }

    public void pop() {
        if (mainStack.peek().equals(minimumStack.peek()[0])) {
            minimumStack.peek()[1]--;
        }
        if (minimumStack.peek()[1] == 0) {
            minimumStack.pop();
        }
        mainStack.pop();
    }

    public int top() {
        return mainStack.peek();
    }

    public int getMin() {
        return minimumStack.peek()[0];
    }
}

The provided Java code implements a data structure called "MinStack". MinStack allows for efficient retrieval of the minimum element in the stack with operations similar to a standard stack, such as push and pop. Here's an overview of how the implemented functions are used in MinStack:

• MinStack() Constructor: Initializes the MinStack object.

• push(int value) Method:

  • Adds the value to the stack.
  • Keeps track of the minimum value. If the pushed value is smaller than the current minimum, or if it’s the first element, it updates the auxiliary minimum stack with this new minimum and resets the count of occurrences of this minimum.

• pop() Method:

  • Removes the top element from the stack.
  • Checks if the popped element is the current minimum. If it is, it decrements the count of this minimum in the auxiliary stack. If the count drops to zero, it removes the minimum from the auxiliary stack.

• top() Method:

  • Returns the top element of the main stack without removing it.

• getMin() Method:

  • Returns the current minimum value without altering the stack by peeking at the top of the auxiliary minimum stack.

This structure is pivotal in scenarios where operations related to both retrieval of the top element and minimum element need to be optimized in terms of time complexity. Such implementations are commonly used in problems involving state management and undo functionalities where constant-time retrieval is a must.

typedef struct {
    int* values;    // Stack for values
    int* mins;      // Stack for tracking minimums
    int* freq;      // Frequency of each minimum value
    int valueIndex; // Current top index for values
    int minIndex;   // Current top index for minimums
    int size;       // Max size of the stacks
} MinStack;

MinStack* createMinStack() {
    MinStack* stack = (MinStack*)malloc(sizeof(MinStack));
    stack->size = 10; // default size
    stack->values = (int*)malloc(stack->size * sizeof(int));
    stack->mins = (int*)malloc(stack->size * sizeof(int));
    stack->freq = (int*)malloc(stack->size * sizeof(int));
    stack->valueIndex = -1;
    stack->minIndex = -1;
    return stack;
}

void extendStack(MinStack* stack) {
    if (stack->valueIndex + 1 >= stack->size) {
        stack->size *= 2;
        stack->values = (int*)realloc(stack->values, stack->size * sizeof(int));
        stack->mins = (int*)realloc(stack->mins, stack->size * sizeof(int));
        stack->freq = (int*)realloc(stack->freq, stack->size * sizeof(int));
    }
}

void pushToMinStack(MinStack* stack, int value) {
    extendStack(stack);
    stack->values[++stack->valueIndex] = value;
    if (stack->minIndex == -1 || value < stack->mins[stack->minIndex]) {
        stack->mins[++stack->minIndex] = value;
        stack->freq[stack->minIndex] = 1;
    } else if (value == stack->mins[stack->minIndex]) {
        stack->freq[stack->minIndex]++;
    }
}

void popFromMinStack(MinStack* stack) {
    if (stack->values[stack->valueIndex] == stack->mins[stack->minIndex]) {
        stack->freq[stack->minIndex]--;
        if (stack->freq[stack->minIndex] == 0) {
            stack->minIndex--;
        }
    }
    stack->valueIndex--;
}

int getTopOfMinStack(MinStack* stack) { 
    return stack->values[stack->valueIndex]; 
}

int getMinimumFromMinStack(MinStack* stack) { 
    return stack->mins[stack->minIndex]; 
}

void freeMinStack(MinStack* stack) {
    free(stack->values);
    free(stack->mins);
    free(stack->freq);
    free(stack);
}

The provided C program implements a "Min Stack," a special type of stack designed to allow constant-time retrieval of the minimum element along with regular stack operations like push and pop. The implementation uses multiple arrays to manage stack data and control its operations efficiently.

Features of Min Stack:

• A traditional stack (values) stores the actual values pushed into the Min Stack.
• An additional stack (mins) keeps track of the current minimum values.
• A frequency stack (freq) records how often a particular minimum value occurs.
• The stack operations (push, pop, top, getMin) are enhanced to handle the minimum value tracking.

Detailed Explanation:

1. Initialization via createMinStack function:

   • Allocates memory for a MinStack structure and initializes the size to 10.
   • Allocates memory for the stacks (values, mins, freq) and initializes the index pointers for value and minimum stacks.

2. Resizing using extendStack:

   • Checks if the stack needs resizing when a new element is pushed.
   • If the current size is reached, doubles the size of the stack arrays to accommodate more elements.

3. Pushing Values (pushToMinStack):

   • Before adding a new element, it first calls extendStack to ensure there is enough space.
   • Pushes the value onto the values stack.
   • Updates the mins and freq stacks if the pushed value is less than or equal to the current minimum.

4. Pop Operation (popFromMinStack):

   • When popping, it decreases the frequency of the current minimum if the popped value equals the current minimum.
   • If the frequency drops to zero, decrement the minimum index, effectively removing the current minimum value from the mins stack.

5. Top and Min Retrieval:

   • getTopOfMinStack fetches the top value from the values stack.
   • getMinimumFromMinStack fetches the current minimum value from the mins stack.

6. Memory Deallocation (freeMinStack):

   • Frees the allocated memory for all stack arrays and the MinStack structure itself.

This implementation is efficient in terms of both time and space, ensuring O(1) time complexity for push, pop, and minimum retrieval operations, making it ideal for scenarios where quick access to the minimum element is frequently required.

function lastElement(items) {
    return items[items.length - 1];
}

class MinimumStack {
    _primaryStack = [];
    _auxiliaryStack = [];

    push(element) {
        this._primaryStack.push(element);
        if (this._auxiliaryStack.length === 0 || element < lastElement(this._auxiliaryStack)[0]) {
            this._auxiliaryStack.push([element, 1]);
        } else if (element === lastElement(this._auxiliaryStack)[0]) {
            lastElement(this._auxiliaryStack)[1]++;
        }
    }

    pop() {
        if (lastElement(this._auxiliaryStack)[0] === lastElement(this._primaryStack)) {
            lastElement(this._auxiliaryStack)[1]--;
        }
        if (lastElement(this._auxiliaryStack)[1] === 0) {
            this._auxiliaryStack.pop();
        }
        this._primaryStack.pop();
    }

    top() {
        return lastElement(this._primaryStack);
    }

    getMin() {
        return lastElement(this._auxiliaryStack)[0];
    }
}

This summary explains the functioning of a MinimumStack class implemented in JavaScript, which is designed to perform standard stack operations and additionally, track the minimum element present in the stack at any given time.

• The class incorporates two main data structures:

  • _primaryStack: holds all the elements of the stack.
  • _auxiliaryStack: maintains elements in a way to always have the current minimum element on top. It stores elements as pairs [element, count] where element is the value and count is the frequency of the minimum element at any given point.

• Key methods of the MinimumStack class:

  • push(element): Adds the element to _primaryStack. For _auxiliaryStack, it pushes the new element if it is smaller than the current minimum or increments the count if it is equal to the current minimum.
  • pop(): Removes the top element from _primaryStack. If the element is the current minimum (equal to the top of the _auxiliaryStack), it decrements the count or removes the minimum element from _auxiliaryStack if the count drops to zero.
  • top(): Returns the top element of _primaryStack without removing it.
  • getMin(): Returns the current minimum element by accessing the first element of the top entry in _auxiliaryStack.

This implementation allows efficient tracking of the minimum element with operations that are constant in time complexity, making the stack operations highly efficient while keeping track of the minimum in an auxiliary structure.

class MinimumStack:

    def __init__(self):
        self.primary_stack = []
        self.auxiliary_stack = []

    def push(self, value: int) -> None:
        self.primary_stack.append(value)
        if not self.auxiliary_stack or value < self.auxiliary_stack[-1][0]:
            self.auxiliary_stack.append([value, 1])
        elif value == self.auxiliary_stack[-1][0]:
            self.auxiliary_stack[-1][1] += 1

    def pop(self) -> None:
        if self.auxiliary_stack[-1][0] == self.primary_stack[-1]:
            self.auxiliary_stack[-1][1] -= 1
        if self.auxiliary_stack[-1][1] == 0:
            self.auxiliary_stack.pop()
        self.primary_stack.pop()

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

    def getMin(self) -> int:
        return self.auxiliary_stack[-1][0]

The solution provided implements a MinimumStack class that supports standard stack operations including push, pop, and retrieving the top element, alongside a custom functionality to retrieve the minimum element in constant time. It uses Python 3 as its programming language.

• The MinimumStack class manages two internal lists: primary_stack for storing the elements of the stack, and auxiliary_stack for tracking the minimum elements.

• When a new element is pushed into MinimumStack:

  • It is always added to primary_stack.
  • It is added to auxiliary_stack if it is smaller than the current minimum, or if it is equal to the current minimum (where a count of occurrences is maintained).

• Upon invocation of the pop() method:

  • The top element is removed from primary_stack.
  • If it matches the current minimum tracked by auxiliary_stack, its occurrence count is decremented. If the count drops to zero, it is removed from auxiliary_stack.

• The top() method returns the last element from primary_stack.

• The getMin() method retrieves the current minimum value by accessing the first element of the last entry in auxiliary_stack, which effectively tracks the minimum throughout.

By handling each stack operation efficiently and utilizing an auxiliary tracking stack, this design ensures that all operations — push, pop, top, and getMin — are performed in constant time.