fork download
copy 
  1. #include<iostream>
  2. #include<stdlib.h>
  3. using namespace std;
  4. class Stack
  5. {
  6. private:
  7.     static const int max = 100;
  8.     int arr[max];
  9.     int top;
  10. public:
  11.     Stack() { top = -1; }
  12.     bool isEmpty();
  13.     bool isFull();
  14.     int pop();
  15.     void push(int x);
  16. };
  17. bool Stack::isEmpty()
  18. {
  19.     if(top == -1)
  20.         return true;
  21.     return false;
  22. }
  23. bool Stack::isFull()
  24. {
  25.     if(top == max - 1)
  26.         return true;
  27.     return false;
  28. }
  29. int Stack::pop()
  30. {
  31.     if(isEmpty())
  32.     {
  33.         cout<<"Stack Underflow";
  34.         abort();
  35.     }
  36.     int x = arr[top];
  37.     top--;
  38.     return x;
  39. }
  40. void Stack::push(int x)
  41. {
  42.     if(isFull())
  43.     {
  44.         cout<<"Stack Overflow";
  45.         abort();
  46.     }
  47.     top++;
  48.     arr[top] = x;
  49. }
  50. //Stack
  51.  
  52. class SpecialStack: public Stack
  53. {
  54.     Stack min;
  55. public:
  56.     int pop();
  57.     void push(int x);
  58.     int getMin();
  59. };
  60.  
  61. void SpecialStack::push(int x)
  62. {
  63.     if(isEmpty()==true)
  64.     {
  65.         Stack::push(x);
  66.         min.push(x);
  67.     }
  68.     else
  69.     {
  70.         Stack::push(x);
  71.         int y = min.pop();
  72.         min.push(y);
  73.         if( x < y )
  74.           min.push(x);
  75.         else
  76.           min.push(y);
  77.     }
  78. }
  79. int SpecialStack::pop()
  80. {
  81.     int x = Stack::pop();
  82.     min.pop();
  83.     return x;
  84. }
  85. int SpecialStack::getMin()
  86. {
  87.     int x = min.pop();
  88.     min.push(x);
  89.     return x;
  90. }
  91. int main()
  92. {
  93.     SpecialStack s;
  94.     s.push(10);
  95.     s.push(5);
  96.     s.push(20);
  97.     s.push(30);
  98.     cout<<s.getMin()<<endl;
  99.     s.push(1);
  100.     cout<<s.getMin();
  101.     return 0;
  102. }
  103.  
Success #stdin #stdout 0s 3296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5
1
https://ideone.com/mgtTQY
GetMin in O(1) C
language:
C++ (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!