Three in One

3.1 Three in One: Describe how you could use a single array to implement three stacks.

• Brain storm:

  • We can divide the array into 3 equal parts, and then define methods on each individual stack.

#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <utility>

using namespace std;

class stackArray3 {

public:
    stackArray3(int length) {

        if (length < 3) {
            cout << "size too small" << endl;
            return;
        }
        len = length;
        // create array
        stackArray = new int[length];

        // round down to ensure safe increments
        s1.first = ceil(length / 3) * 0;
        s2.first = ceil(length / 3) * 1;
        s3.first = ceil(length / 3) * 2;

        s1.second = s2.second = s3.second = 0;
    }

    void insert_top(int stackNum, int num) {
        switch (stackNum) {
        case 1:
            if (isFull(s1)) { cout << "stack is full" << endl; break; };
            stackArray[s1.first] = num;
            s1.first++; s1.second++;
            break;

        case 2:
            if (isFull(s2)) { cout << "stack is full" << endl; break; }
            stackArray[s2.first] = num;
            s2.first++; s2.second++;
            break;

        case 3:
            if (isFull(s3)) { cout << "stack is full" << endl; break; }
            stackArray[s3.first] = num;
            s3.first++; s3.second++;
            break;

        default: 
            cout << "invalid stack number" << endl;
            break;
        }
    }


    int top(int stackNum) {
        switch (stackNum) {
        case 1:
            if (isEmpty(s1)) { cout << "empty stack" << endl; return 0; }
            return stackArray[s1.first - 1];
            break;

        case 2:
            if (isEmpty(s2)) { cout << "empty stack" << endl; return 0; }
            return stackArray[s2.first - 1];
            break;

        case 3:
            if (isEmpty(s3)) { cout << "empty stack" << endl; return 0; }
            return stackArray[s3.first - 1];
            break;

        default:
            cout << "invalid stack number" << endl;
            break;
        }
    }

    int top_and_pop(int stackNum) {
        int ret;

        switch (stackNum) {
        case 1:
            if (isEmpty(s1)) { cout << "empty stack" << endl; return 0; }
            ret = stackArray[s1.first - 1];
            s1.first--; s1.second--;
            return ret;
            break;

        case 2:
            if (isEmpty(s2)) { cout << "empty stack" << endl; return 0; }
            return stackArray[s2.first - 1];
            ret = stackArray[s2.first - 1];
            s2.first--; s2.second--;
            return ret;
            break;

        case 3:
            if (isEmpty(s3)) { cout << "empty stack" << endl; return 0; }
            return stackArray[s3.first - 1];
            ret = stackArray[s2.first - 1];
            s2.first--; s2.second--;
            return ret;
            break;

        default:
            cout << "invalid stack number" << endl;
            break;
        }
    }

private:
    int *stackArray;
    int len;
    // index <-> count
    // current index in the stack <-> stack capacity
    std::pair<int, int> s1, s2, s3;

    bool isFull(pair<int, int> stackNum) {
        int num = ceil(len / 3);
        return stackNum.second >= ceil(len / 3);
    }

    bool isEmpty(pair<int, int> stackNum) {
        return stackNum.second == 0;
    }

};


int main()
{
    // even stack lengths -> cap = 2
    stackArray3 stackAr(6);

    stackAr.insert_top(1, 4);
    stackAr.insert_top(2, 5);
    stackAr.insert_top(3, 6);

    cout << stackAr.top(1) << endl;
    cout << stackAr.top(2) << endl;
    cout << stackAr.top(3) << endl;

    stackAr.insert_top(1, 7);
    stackAr.insert_top(2, 8);
    stackAr.insert_top(3, 9);

    cout << stackAr.top(1) << endl;
    cout << stackAr.top(2) << endl;
    cout << stackAr.top(3) << endl;

    // must be full
    stackAr.insert_top(1, 7);

    cout << endl << endl;


    // uneven stack lengths -> cap = 1
    stackArray3 stackAr2(4);

    stackAr2.insert_top(1, 4);
    stackAr2.insert_top(2, 5);
    stackAr2.insert_top(3, 6);

    cout << stackAr2.top(1) << endl;
    cout << stackAr2.top(2) << endl;
    cout << stackAr2.top(3) << endl;

    // must be full
    stackAr2.insert_top(1, 7);

}