mariia-kornieva
8/11/2019 - 10:26 AM

Stack with max API

Stack with max API

class MaxStack {
public:
    /** initialize your data structure here. */
    MaxStack() {
        
    }
    
    void push(int x) {
        int max = maxs.empty() ? x : maxs.back();
        maxs.push_back(max > x ? max : x);
        stack.push_back(x);
      }
    
    int pop() {
        int back = stack.back();
        stack.pop_back();
        maxs.pop_back();
        return back;
    }
    
    int top() {
        return stack.back();
    }
    
    int peekMax() {
        return maxs.back();
    }
    
    int popMax() {
      int max = peekMax();
      std::vector<int> buffer;
      while(top() != max)
      {
        buffer.push_back(pop());
      }
      pop();
      while(!buffer.empty())
      {
        push(buffer.back());
        buffer.pop_back();
      }
      return max;
    }
  
private:
  std::vector<int> stack;
  std::vector<int> maxs;
};