Find Minimum In Stack In O(1) Time and O(1) Space

Find Minimum In Stack In O(1) Time and O(1) Space

For this problem I have used a stack of pointer to nodes. A node have two members one is the value part and another is the link to another node.

Conditions

• Update the minimum with each push operation
• A node (current) will point to another node if the current node have a previous minimum node else it will point to null
• During pop check the top node and the minimum node if they point to the same location then update the current minimum to previous minimum by assigning the link of the top node to minimum pointer
• If the top node has null to its link part then it is not the minimum node and no pointer manipulation needed,

Sample Operations

C++ Implementation

#include <iostream>
using namespace std;
#define MAX 9999

struct Node {
    int val;
    struct Node *add;
};

class Stack
{
    Node **arr, *minn;
    int s, top;

    public:
        Stack(int s) : s(s) {
            arr = new Node*[s];
            top = -1;
            minn = new Node();
            minn->val = MAX;
        }
        ~Stack() {
            delete [] arr;
        }

        void push(int item);
        int pop();
        int minimum() const {
            return (top ==-1)? -1 : minn->val;
        };
};

void Stack::push(int item) {
    if (top == s-1) {
        cout << "Stack full!" << endl;
    }
    else {
        Node *tmp = new Node();
        tmp->add = NULL;
        if (top == -1) {
            minn = tmp;
        }
        else {
            if (item <= minn->val) {
                tmp->add = minn;
                minn = tmp;
            }
        }
        tmp->val = item; ++top;
        arr[top] = tmp;
    }
}

int Stack::pop()
{
    int retVal = -1;
    if (top == -1) {
        delete minn;
        cout << "Stack empty!" << endl;
    }
    else {
        retVal = arr[top]->val;
        if (arr[top] == minn){
            minn = arr[top]->add;
        }
        top--;
    }
    return retVal;
}

int main()
{
    Stack s(6);
    s.push(7);
    s.push(1);
    s.push(1);
    s.push(2);
    s.push(4);
    s.push(0);
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    return 0;
}

Current Min: 0
Popped: 0
Current Min: 1
Popped: 4
Current Min: 1
Popped: 2
Current Min: 1
Popped: 1
Current Min: 1
Popped: 1
Current Min: 7
Popped: 7

Process returned 0 (0x0)   execution time : 0.044 s
Press any key to continue.

If you find anything wrong please comment below. And if you have any other approach then mail me at itsaboutcs@gmail.com.