Stack With Minimum Function

Question

Define a stack structure with “min” function — a function to get the minimum value within the stack. The time complexity of min, push and pop functions must be O(1).

Solution

Push data to the stack at the same time update the minimum stack if the
new data is smaller then the current minimum value. Throw exception if stack is empty.

Pop data to the stack at the same time pop from the min stack if it is popping the minimum value. Throw exception if stack is empty.

And then return the current minimum value.

結合鍊錶一起做。首先我做插入以下數字: 10, 7, 3, 3, 8, 5, 2, 6

0: 10 -> NULL (MIN=10, POS=0) 1: 7 -> [0] (MIN=7, POS=1) // 用數組表示堆棧，第0個元素表示棧底 2: 3 -> [1] (MIN=3, POS=2) 3: 3 -> [2] (MIN=3, POS=3) 4: 8 -> NULL (MIN=3, POS=3) // 技巧在這裡，因為8比當前的MIN大，所以彈出8不會影響當前的MIN 5: 5 -> NULL (MIN=3, POS=3) 6: 2 -> [2] (MIN=2, POS=6) // 如果2出棧了，那麼3就是MIN 7: 6 -> [6]

出棧的話採用類似方法修正。

所以，藉助輔助棧，保存最小值，且隨時更新輔助棧中的元素。push第一個元素進A，也把它push進B，當向Apush的元素比B中的元素小， 則也push進B，即更新B。否則，不動B，保存原值。向棧A push元素時，順序由下至上。輔助棧B中，始終保存著最小的元素。

然後，當pop A中的元素小於B中棧頂元素時，則也要pop B中棧頂元素。

Samples

The following is an optimized implementation. Repeated minimum value will not be stored through comparing values while pushing or popping values.

#include <vector> 
#include <cassert>

using namespace std;

template < typename T > class StackWithMin {
  
  private: 
  
  vector < T > dataStack; // stacks to store data 
  vector < size_t > minStack; // stack to store position of minimum value 

  public:
  
  void push(T data) {
    dataStack.push_back(data);
    if (minStack.empty() || data < dataStack[minStack.back()]) minStack.push_back(dataStack.size() - 1);
  }

  void pop() {
    assert(!dataStack.empty());
    if (dataStack.back() == dataStack[minStack.back()]) minStack.pop_back();
    dataStack.pop_back();
  }
  
  T min() {
    assert(!dataStack.empty() && !minStack.empty());
    return dataStack[minStack.back()];
  }
}

int main() {
  StackWithMin < int > stack = StackWithMin < int > ();
  stack.push(10);
  stack.push(7);
  stack.push(3);
  stack.push(3);
  stack.push(8);
  stack.push(5);
  stack.push(2);
  stack.push(6);
  printf("Minimum value: %dn", stack.min());
}

import java.util.Stack;
    
public class Pactice02 {
    
    public static void main(String[] args) {
        System.out.println("Hello World!");
        AdvancedStack stack = new AdvancedStack();
        stack.push(10);
        stack.push(7);
        stack.push(3);
        stack.push(3);
        stack.push(8);
        stack.push(5);
        stack.push(2);
        stack.push(6);
        System.out.println("Minimum value: " + stack.getMinimum());
        stack.pop();
        System.out.println("Minimum value: " + stack.getMinimum());
        stack.pop();
        System.out.println("Minimum value: " + stack.getMinimum());
        stack.pop();
        System.out.println("Minimum value: " + stack.getMinimum());
    }
    
    public static class AdvancedStack extends Stack {
        private Stack mMinimumStack = new Stack();
        @Override public E push(E item) {
            if (mMinimumStack.empty() || item.doubleValue() 0) {
                return mMinimumStack.peek();
            }
            return null;
        }
    }
}