Stack Min

3.2 Stack Min: How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? Push, pop and min should all operate in 0(1) time.

• Brain storm:

  • Build a stack that contains stackNodes. Every time an a element is push onto the the stack, the minimum value will be assessed. The minimum will always be contained onto top of the stack and will always be the minimum of its substack. We will maintain order of the min values as we add or remove more elements into the stack.

using namespace std;

class stackNode {
public:
    stackNode() {}
    stackNode(int val, int mini) : min(mini), value(val) {}

    int min;
    int value;

};

class minStack {
public:
    minStack(int len) {
        myArray = new stackNode[len];
        cur_index = 0;
        length = len;
    }

    void push(int num) {
        stackNode* temp;
        if (isFull()) { cout << "full" << endl; return; }

        // new stack
        else if (isEmpty()) {
            temp = new stackNode(num, num);
            myArray[cur_index] = *temp;
            cur_index++;
        }

        // input is smaller than min, so use it as the new min
        else if (myArray[cur_index - 1].min > num) {
            temp = new stackNode(num, num);
            myArray[cur_index] = *temp;
            cur_index++;
        }

        // input is larger than min, so set previous min
        else {
            temp = new stackNode(num, myArray[cur_index - 1].min);
            myArray[cur_index] = *temp;
            cur_index++;
        }
    }

    void pop() {
        if (isEmpty()) { cout << "empty" << endl; return; }
        --cur_index;
    }

    int min() {
        if (isEmpty()) { cout << "empty" << endl; return 0; }
        return top();
    }



private:
    stackNode *myArray;
    int cur_index;
    int length;

    bool isFull() {
        return cur_index > length;
    }

    bool isEmpty() {
        return cur_index == 0;
    }

    int top() {
        return myArray[cur_index-1].min;
    }
};


int main()
{
    cout << "cascading down" << endl;
    minStack stack(10);
    stack.push(5);
    stack.push(4);
    stack.push(3);
    stack.push(2);

    cout << stack.min() << endl;
    cout << endl << endl;

    cout << "cascading up" << endl;
    minStack stack2(10);
    stack2.push(2);
    stack2.push(3);
    stack2.push(4);
    stack2.push(5);

    cout << stack2.min() << endl;
    cout << endl << endl;

    cout << "mixed" << endl;
    minStack stack3(10);
    stack3.push(1);
    stack3.push(5);
    stack3.push(3);
    stack3.push(10);
    stack3.push(4);

    cout << stack3.min() << endl;
    cout << endl << endl;


    cout << "pop operations" << endl;
    stack3.pop(); // remove 4
    stack3.pop(); // remove 10
    stack3.pop(); // remove 3

    cout << stack3.min() << endl;
    cout << endl << endl;


    cout << "pop operations with min removed // cascading up" << endl;
    stack2.pop(); // remove 2
    stack2.pop(); // remove 3
    stack2.pop(); // remove 4

    cout << stack2.min() << endl;
    cout << endl << endl;


    cout << "pop operations with min removed // cascading down" << endl;
    stack.pop(); // remove 2
    stack.pop(); // remove 3
    stack.pop(); // remove 4

    cout << stack.min() << endl;
    cout << endl << endl;
}