Min and max stacks

Questions 1 to 5 of 6

1. 1. A MinStack gets pushes 5, 3, 7, 3, 1 and then one pop. What does minimum() return now?

   1357
2. 2. What does this program print? ``cpp #include <algorithm> #include <iostream> #include <vector> class MinStack { public: void push(int value) { values_.push_back(value); mins_.push_back(mins_.empty() ? value : std::min(value, mins_.back())); } void pop() { values_.pop_back(); mins_.pop_back(); } int minimum() const { return mins_.back(); } bool empty() const { return values_.empty(); } private: std::vector<int> values_; std::vector<int> mins_; }; int main() { MinStack s; for (int x : {4, 1, 4}) { s.push(x); std::cout << s.minimum() << ' '; } s.pop(); std::cout << s.minimum() << ' '; s.pop(); std::cout << s.minimum() << '\n'; } ``

   4 1 4 1 14 1 1 4 44 1 1 1 41 1 1 4 4
3. 3. What does this program print? ``cpp #include <cstddef> #include <iostream> #include <vector> class CompactMinStack { public: void push(int value) { values_.push_back(value); if (mins_.empty() || value <= mins_.back()) { mins_.push_back(value); } } void pop() { if (values_.back() == mins_.back()) { mins_.pop_back(); } values_.pop_back(); } int minimum() const { return mins_.back(); } std::size_t value_count() const { return values_.size(); } std::size_t min_count() const { return mins_.size(); } private: std::vector<int> values_; std::vector<int> mins_; }; int main() { CompactMinStack c; for (int x : {5, 2, 2, 6}) { c.push(x); } c.pop(); c.pop(); std::cout << "values " << c.value_count() << ", min entries " << c.min_count() << ", min " << c.minimum() << '\n'; } ``

   values 2, min entries 3, min 2values 3, min entries 2, min 2values 4, min entries 3, min 2values 2, min entries 2, min 2
4. 4. What does minimum() cost in the full MinStack as the stack grows to n items?

   O(n), because it scans every valueO(log n), because it searches a sorted listO(1), because it reads the top of mins_O(n log n), because it sorts the stack first
5. 5. Why does the full MinStack store a running minimum for every value, not just for some of them?

   So a pop never has to scan, because each entry already holds the smallest value at or below itSo the stack stays sortedSo top() runs in O(log n)So duplicate values are removed