fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. class MinStack
  8. {
  9. private:
  10.     int * stk;
  11.     size_t capacity, size_;
  12.     int m = 0;
  13.     void resize_()
  14.     {
  15.         if (capacity == size_)
  16.         {
  17.             int * tmp = new int[capacity *= 2];
  18.             for(size_t i = 0; i < size_; ++i)
  19.                 tmp[i] = stk[i];
  20.             delete[] stk;
  21.             stk = tmp;
  22.         }
  23.     }
  24.     void swap(MinStack& s)
  25.     {
  26.         std::swap(stk,s.stk);
  27.         std::swap(capacity,s.capacity);
  28.         std::swap(size_,s.size_);
  29.         std::swap(m,s.m);
  30.     }
  31. public:
  32.     MinStack(size_t sz = 16):stk(new int[sz+1]),capacity(sz+1),size_(0){}
  33.     ~MinStack()
  34.     {
  35.         delete[] stk;
  36.     }
  37.     MinStack(const MinStack& s):stk(new int[s.size_]),capacity(s.size_)
  38.         ,size_(s.size_),m(s.m)
  39.     {
  40.         for(size_t i = 0; i < s.size_; ++i)
  41.             stk[i] = s.stk[i];
  42.     }
  43.     MinStack& operator = (const MinStack& s)
  44.     {
  45.         MinStack tmp(s);
  46.         swap(tmp);
  47.         return *this;
  48.     }
  49.  
  50.     void push(int i)
  51.     {
  52.         resize_();
  53.         m = (size_ == 0) ? i : std::min(m,i);
  54.         stk[size_++] = i;
  55.     }
  56.     bool empty() const
  57.     {
  58.         return size_ == 0;
  59.     }
  60.     int pop()
  61.     {
  62.         if (empty()) throw runtime_error("pop from empty stack");
  63.         int r = stk[--size_];
  64.         if (r == m && size_) m = *std::min_element(stk,stk+size_);
  65.         return r;
  66.     }
  67.     int min() const
  68.     {
  69.         if (empty()) throw runtime_error("min from empty stack");
  70.         return m;
  71.     }
  72.     int back() const
  73.     {
  74.         if (empty()) throw runtime_error("back from empty stack");
  75.         return stk[size_-1];
  76.     }
  77.     void clear()
  78.     {
  79.         size_ = 0;
  80.     }
  81.     size_t size() const { return size_; }
  82. };
  83.  
  84. int main()
  85. {
  86.     MinStack s;
  87.     for(int i = 0; i < 20; ++i)
  88.     {
  89.         int d = rand()%90+10;
  90.         cout << d << "  ";
  91.         s.push(d);
  92.     }
  93.     cout << endl;
  94.  
  95.     for(int i = 0; i < 20; ++i)
  96.     {
  97.         cout << setw(2) << s.size() << ": " << s.min() << "  ";
  98.         cout << s.pop() << endl;
  99.     }
  100. }
  101.  
Success #stdin #stdout 0.01s 5476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
83  26  37  35  33  35  56  22  79  11  42  77  60  89  33  86  70  46  62  56  
20: 11  56
19: 11  62
18: 11  46
17: 11  70
16: 11  86
15: 11  33
14: 11  89
13: 11  60
12: 11  77
11: 11  42
10: 11  11
 9: 22  79
 8: 22  22
 7: 26  56
 6: 26  35
 5: 26  33
 4: 26  35
 3: 26  37
 2: 26  26
 1: 83  83
https://ideone.com/6bv5Xh
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!