# 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);

}``````

Last updated