# CCI题目3-3：Set Of Stacks

By | 2012 年 11 月 20 日

Imagine a (literal) stack of plates. If the stack gets too high, it might topple. There- fore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOf- Stacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

//
//  main.cpp
//  CCI.3.3.SetOfStack
//
//  Created by Qiu Xiangyu on 12-11-20.
//

#include
#include
using namespace std;

template
class stackNode {
public:
T                value;
stackNode    *pre;
};

template
class singleStack {
int              _size;
stackNode    *_top;
public:
singleStack() {
_size = 0;
_top = NULL;
}
int size() {
return _size;
}
T *top() {
return _top ? &_top->value : NULL;
}
void push(T val) {
stackNode *newnode = new stackNode();
newnode->value = val;
newnode->pre = _top;
_top = newnode;
++_size;
}
void pop() {
if (_top) {
stackNode *oldtop = _top;
_top = _top->pre;
delete oldtop;
--_size;
}
}
};

template
class setOfStack {
int                          _size;
int                          _singleLmt;
vector >      _stacks;
public:
setOfStack(int sizeLimitOnSingleStack = 10){
_singleLmt = sizeLimitOnSingleStack;
_size = 0;
}
void push(T val) {
if (_stacks.size() > 0 && _stacks.back().size() < _singleLmt) {
singleStack &targetStack = _stacks.back();
targetStack.push(val);
} else {
cout<<"new stack for item: "< newstack;
newstack.push(val);
_stacks.push_back(newstack);
}
++_size;
}
void pop() {
if (_stacks.size() > 0) {
singleStack &targetStack = _stacks.back();
targetStack.pop();
if (targetStack.size() == 0) {
cout<<"remove stack at size: "<<_size< 0) {
return _stacks.back().top();
}
return NULL;
}
};

int main(int argc, const char * argv[])
{
// insert code here...
std::cout << "Hello\n";
setOfStack stk(3);
for (int i = 0; i < 10; ++i) {
stk.push(i);
}
while (stk.size() > 0) {
int v = * stk.top();
cout<