fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. typedef struct MinStackElement {
  5.     int val;
  6.     MinStackElement* next;
  7.  
  8.     MinStackElement():
  9.     val(0),
  10.     next(NULL){}
  11.  
  12.     MinStackElement(int val_) :
  13.     val(val_),
  14.     next(NULL){}
  15.  
  16. } MinStackElement;
  17.  
  18. typedef struct MinStackElementInMin {
  19.     MinStackElement elem;
  20.     MinStackElementInMin* nextInMin;
  21.  
  22.     MinStackElementInMin(int val_) {
  23.         elem.val = val_;
  24.         elem.next = NULL;
  25.         nextInMin = NULL;
  26.     }
  27. } MinStackElementInMin;
  28.  
  29.  
  30. class MinStack {
  31.  
  32.  
  33. MinStackElement* stackHead;
  34. MinStackElementInMin* stackMin;
  35. public:
  36.     void push(int x) {
  37.  
  38.         if (stackHead == NULL)
  39.         {
  40.             MinStackElementInMin* newElem = new MinStackElementInMin(x);
  41.             stackHead = (MinStackElement*) (newElem);
  42.             stackMin = newElem;
  43.         }
  44.         else
  45.         {
  46.             if (x <= stackMin->elem.val)
  47.             {
  48.                 MinStackElementInMin* newElem = new MinStackElementInMin(x);
  49.                 newElem->nextInMin = stackMin;
  50.                 stackMin = newElem;
  51.                 stackHead = (MinStackElement*) (newElem);
  52.             }
  53.             else
  54.             {
  55.                 MinStackElement* newElem = new MinStackElement(x);
  56.                 newElem->next = stackHead;
  57.                 stackHead = newElem;
  58.             }
  59.         }
  60.     }
  61.  
  62.     void pop() {
  63.         if (stackHead != NULL)
  64.         {
  65.             MinStackElement* deleted = stackHead;
  66.             if (deleted->val == stackMin->elem.val)
  67.             {
  68.                 stackMin = stackMin->nextInMin;
  69.                 stackHead = stackHead->next;
  70.                 delete ((MinStackElementInMin*) (deleted));
  71.             }
  72.             else
  73.             {
  74.                 stackHead = stackHead->next;
  75.                 delete deleted;
  76.             }
  77.         }
  78.     }
  79.  
  80.     int top() {
  81.         return stackHead->val;
  82.     }
  83.  
  84.     int getMin() {
  85.         return stackMin->elem.val;
  86.     }
  87.  
  88.     MinStack() :
  89.     stackHead(NULL),
  90.     stackMin(NULL) {}
  91. };
  92.  
  93. int main() {
  94. 	MinStack m;
  95. 	m.push(-10);
  96. 	m.push(14);
  97. 	m.getMin();
  98. 	m.getMin();
  99. 	m.push(-20);
  100. 	m.getMin();
  101. 	cout << m.getMin();
  102. 	m.top();
  103. 	m.getMin();
  104. 	m.pop();
  105. 	m.push(10);
  106. 	m.push(-7);
  107. 	cout << m.getMin();
  108. 	m.push(-7);
  109. 	m.pop();
  110. 	m.top();
  111. 	cout << m.getMin();
  112. 	m.pop();
  113. 	// your code goes here
  114. 	return 0;
  115. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-20-7-7
https://ideone.com/SeszFZ
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!