Im trying to create a stack class that gets the minimum elem

Im trying to create a stack class that gets the minimum element in the stack in constant time. Currently mine is in linear time. Any tips would help.

#include <iostream>

using namespace std;
#define MAX_SIZE 100

class Stack {
private:
int S[MAX_SIZE];
int top;

public:
Stack()
{
  top = -1;
}

void push(int a)
{
  if (top == MAX_SIZE - 1) {
   cout << \"Stack is Full.\" << endl;
   return;
  }
  S[++top] = a;
}

void pop() {
  if (top == -1) {
   cout << \"Stack is Empty.\" << endl;
   return;
  }
  top--;
}

int peek(){
  return S[top];
}

int isEmpty() {
  if (top == -1)
   return 1;
  else
   return 0;
}

int getMin()
{
  if (top != -1)
  {
   int min = S[0];
   for(int i = 0; i <= top; i++)
   {
    if (S[i] < min)
    {
     min = S[i];
    }
   }
   return min;
  }



}

};

int main() {

Stack s = Stack();
s.push(6);
s.push(2);
s.push(7);
s.push(5);
s.push(3);
s.push(10);
cout << s.peek() << endl;
cout << s.getMin() << endl;

Solution

HI, please read my idea.

Please let me know in case of any issue.

Use two stacks: one to store actual stack elements and other as an auxiliary stack to store minimum values. The idea is to do push() and pop() operations in such a way that the top of auxiliary stack is always the minimum. Let us see how push() and pop() operations work.

Push(int x) // inserts an element x to Special Stack
1) push x to the first stack (the stack with actual elements)
2) compare x with the top element of the second stack (the auxiliary stack). Let the top element be y.
…..a) If x is smaller than y then push x to the auxiliary stack.
…..b) If x is greater than y then push y to the auxiliary stack.

int Pop() // removes an element from Special Stack and return the removed element
1) pop the top element from the auxiliary stack.
2) pop the top element from the actual stack and return it.

The step 1 is necessary to make sure that the auxiliary stack is also updated for future operations.

int getMin() // returns the minimum element from Special Stack
1) Return the top element of auxiliary stack.

We can see that all above operations are O(1).
Let us see an example. Let us assume that both stacks are initially empty and 18, 19, 29, 15 and 16 are inserted to the SpecialStack.

When we insert 18, both stacks change to following.
Actual Stack
18 <--- top   
Auxiliary Stack
18 <---- top

When 19 is inserted, both stacks change to following.
Actual Stack
19 <--- top   
18
Auxiliary Stack
18 <---- top
18

When 29 is inserted, both stacks change to following.
Actual Stack
29 <--- top   
19
18
Auxiliary Stack
18 <---- top
18
18

When 15 is inserted, both stacks change to following.
Actual Stack
15 <--- top   
29
19
18
Auxiliary Stack
15 <---- top
18
18
18

When 16 is inserted, both stacks change to following.
Actual Stack
16 <--- top   
15
29
19
18
Auxiliary Stack
15 <---- top
15
18
18
18