CareerCup-3.3
Imagine a (literal) stack of plates If the stack gets too high, it might topple Therefore, 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 SetOfStacks 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)
FOLLOW UP
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack
#include <iostream>
using namespace std;
#define THRESHOLD 3
typedef int Data;
struct Node
{
Node(Data d):data(d){next = NULL;};
Data data;
Node* next;
};
class Stack
{
public:
Stack* next;
int mSize;
Stack():topNode(NULL), next(NULL), mSize(0){cout<<"new stack"<<endl;};
~Stack(){cout<<"deconstruct"<<endl;};
void pop()
{
if(topNode != NULL)
{
Node* p = topNode;
topNode = topNode->next;
delete p;
mSize--;
} else {
throw "Empty Stack";
}
};
Data top()
{
if(topNode != NULL)
{
return topNode->data;
} else {
throw "Empty Stack";
}
};
void push(Data data)
{
Node* d = new Node(data);
d->next = topNode;
topNode = d;
mSize++;
};
bool isEmpty(){return topNode == NULL;};
private:
Node* topNode;
};
class SetOfStacks
{
public:
SetOfStacks():topStack(NULL){};
void push(Data data)
{
cout<<"Push"<<endl;
if(topStack == NULL || topStack->mSize >= THRESHOLD)
{
Stack* stack = new Stack;
stack->push(data);
stack->next = topStack;
topStack = stack;
} else {
topStack->push(data);
}
};
void pop()
{
cout<<"Pop"<<endl;
if(topStack == NULL)
{
throw "Empty SetOfStack";
}
topStack->pop();
if(topStack->isEmpty())
{
Stack* p = topStack;
topStack = topStack->next;
delete p;
}
};
Data top()
{
if(topStack == NULL)
throw "Empty SetOfStack";
return topStack->top();
};
void popAt(int index)
{
Stack* pos = topStack;
Stack* pre = NULL;
while(pos != NULL && index--)
{
//cout<<index<<endl;
pre = pos;
pos = pos->next;
}
if(pos == NULL)
throw "Stack Do Not Exits";
pos->pop();
if(pos->isEmpty())
{
if(pre == NULL)
{
topStack = pos->next;
} else {
pre->next = pos->next;
}
delete pos;
}
};
bool isEmpty(){return topStack==NULL;};
private:
Stack* topStack;
};
int main()
{
SetOfStacks stacks;
for(int i=0; i<10; i++)
stacks.push(i);
cout<<stacks.top()<<endl;
stacks.popAt(3);
cout<<stacks.top()<<endl;
stacks.popAt(3);
cout<<stacks.top()<<endl;
stacks.popAt(3);
for(int i=0; i<7; i++)
{
cout<<"Top: "<<stacks.top()<<endl;
stacks.pop();
}
system("pause");
};
