fork(1) download
copy 
  1. #include <cassert>
  2. #include <iostream>
  3.  
  4. class StackWithMin
  5. {
  6.     int min;
  7.     int size;
  8.     int data[1024];
  9.  
  10.   public:
  11.     StackWithMin& push ( int val ) {
  12.         if ( size == 0 ) {
  13.             data[size] = val;
  14.             min = val;
  15.         } else if ( val < min) {
  16.             data[size] = 2 * val - min;
  17.             min = val;
  18.  
  19.             assert (data[size] < min); 
  20.         } else {
  21.             data[size] = val;
  22.         }
  23.  
  24.         ++size;
  25.  
  26.         // check size and grow array
  27.         return *this;
  28.     }
  29.  
  30.     int getMin () {
  31.         return min;
  32.     }
  33.  
  34.     int pop () {
  35.         --size;
  36.  
  37.         int val = data[size];
  38.  
  39.         if ( ( size > 0 ) && ( val < min ) ) {
  40.             int prevMin = min;
  41.             min += min - val;
  42.             return prevMin;
  43.         } else {
  44.             return val;
  45.         }
  46.     }
  47.  
  48.     bool isEmpty () {
  49.         return size == 0;
  50.     }
  51. };
  52.  
  53. int main () {
  54.     StackWithMin stack;
  55.  
  56.     stack.push(10).push(3).push(6).push(12).push(2).push(6).push(9).push(1);
  57.  
  58.     while ( ! stack.isEmpty() ) {
  59.         int min = stack.getMin();
  60.         int val = stack.pop();
  61.         std::cout << "popped " << val << ", min " << min << "->"
  62.             << stack.getMin() << '\n';
  63.     }
  64. }
Success #stdin #stdout 0s 3296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
popped 1, min 1->2
popped 9, min 2->2
popped 6, min 2->2
popped 2, min 2->3
popped 12, min 3->3
popped 6, min 3->3
popped 3, min 3->10
popped 10, min 10->10
https://ideone.com/j3x8Fw
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!