# CCI题目3-1：Three Stacks in One Array

By | 2012 年 11 月 18 日

Describe how you could use a single array to implement three stacks.

```
//
//  main.cpp
//  CCI.3.1.Three Stacks in One Array
//
//  Created by Qiu Xiangyu on 12-11-17.
//

#include
using namespace std;

template
class stackNode {
public:
Ts                value;
stackNode    *pre;
stackNode() {pre = NULL;}
stackNode(Ts&avalue, stackNode*thePre):value(avalue),pre(thePre) {;}
};

template
class triStack {
int              stackSize[3];
stackNode    *tops[3];
stackNode    *empty;
stackNode    *buffer = NULL;
int              bufferSize = 0;
inline stackNode *getEmptySlot() {
if (empty == NULL) {
return NULL;
}
stackNode *etop = empty;
empty = etop->pre;
return etop;
}
inline void reuse(stackNode * node) {
node->pre = empty;
empty = node;
}
public:
inline int totleSize() {
int sum = 0;
for (int i = 0; i < 3; ++i) {
sum += stackSize[i];
}
return sum;
}
inline bool isFull() {
return NULL == empty;
}
bool push(int stackIndex,T value) {
if (stackIndex < 0 || stackIndex >= 3) {
return false;
}
stackNode *slot = getEmptySlot();
if (NULL == slot) {
//stack full
return false;
}
stackNode *last = tops[stackIndex];
slot->pre = last;
tops[stackIndex] = slot;
++stackSize[stackIndex];
return true;
}
bool pop(int stackIndex) {
if (stackIndex < 0 || stackIndex >= 3) {
return false;
}
stackNode *top = tops[stackIndex];
if (NULL == top) {
return false;
}
tops[stackIndex] = top->pre;
--stackSize[stackIndex];
reuse(top);
}
T *top(int stackIndex) {
if (stackIndex < 0 || stackIndex >= 3) {
//error
return NULL;
}
stackNode *topNode = tops[stackIndex];
if (NULL == topNode) {
return NULL;
}
return &topNode->value;
}
triStack(int totalSize) {
if (totalSize > 0) {
bufferSize = totalSize;
buffer = new stackNode [bufferSize];

//initilize the empty chain.
stackNode * last = NULL;
for (int i = 0; i < bufferSize; ++i) {
stackNode *pnode = buffer + i;
pnode->pre = last;
last = pnode;
}
empty = buffer + bufferSize - 1;

//initilize the stacks
for (int i = 0; i < 3; ++i) {
tops[i] = NULL;
stackSize[i] = 0;
}
} else {
cout<<"Error stack size\n";
}
}
~triStack() {
if (buffer) {
delete buffer;
buffer = NULL;
}
}
};

int main(int argc, const char * argv[])
{
std::cout << "Hello\n";

triStack teststack(3);
if (true != teststack.push(0, 0)) cout<<"err\n";
if (true != teststack.push(1, 1)) cout<<"err\n";
if (true != teststack.push(2,2)) cout<<"err\n";
if (false != teststack.push(2,3)) cout<<"err\n";
if (true != teststack.isFull()) cout<<"err\n";
return 0;
}
```