CareerCup-3.1
Describe how you could use a single array to implement three stacks.
Approach 1:
#include <iostream>
using namespace std;
#define SIZE 60
#define PERSIZE SIZE/3
typedef int Data;
class Stack
{
public:
Stack(int type):mType(type)
{
if(type < 0 || type > 2)
{
throw "Error Stack Type";
} else {
tag = mType * PERSIZE - 1;
}
};
void push(Data d)
{
if(tag >= (mType + 1) * PERSIZE - 1)
{
throw "Out of Size";
} else {
data[++tag] = d;
}
};
void pop()
{
if(tag < mType * PERSIZE)
{
throw "Empty Stack";
} else {
tag --;
}
};
Data peek()
{
if(tag < mType * PERSIZE)
{
throw "Empty Stack";
} else {
return data[tag];
}
};
bool isEmpty(){return tag >= mType * PERSIZE;};
private:
static Data data[SIZE];
int mType;
int tag;
};
Data Stack::data[SIZE];
Approach 2:
#include <iostream>
using namespace std;
#define SIZE 60
typedef int Data;
struct Node
{
Data data;
int next;
};
class Stack
{
public:
Stack(int type):mType(type)
{
if(type < 0 || type > 2)
{
throw "Error Stack Type";
}
};
void push(Data d)
{
if(tag >= SIZE-1)
{
throw "Stack Full";
}
data[++tag].data = d;
if(top[mType] < 0)
data[tag].next = -1;
else
data[tag].next = top[mType];
top[mType] = tag;
};
void pop()
{
if(top[mType] < 0)
{
throw "Empty Stack";
}
top[mType] = data[top[mType]].next;
tag--;
};
Data peek()
{
if(top[mType] < 0)
{
throw "Empty Stack";
} else {
return data[top[mType]].data;
}
};
bool isEmpty(){return top[mType] >= 0;};
private:
static Node data[SIZE];
int mType;
static int top[3];
static int tag;
};
Node Stack::data[SIZE];
int Stack::tag = -1;
int Stack::top[3] = {-1, -1, -1};
#include <iostream>
using namespace std;
#define SIZE 60
typedef int Data;
struct Node
{
Data data;
int next;
};
class Stack
{
public:
Stack(int type):mType(type)
{
if(type < 0 || type > 2)
{
throw "Error Stack Type";
}
};
void push(Data d)
{
if(tag >= SIZE-1)
{
throw "Stack Full";
}
data[++tag].data = d;
if(top[mType] < 0)
data[tag].next = -1;
else
data[tag].next = top[mType];
top[mType] = tag;
};
void pop()
{
if(top[mType] < 0)
{
throw "Empty Stack";
}
top[mType] = data[top[mType]].next;
tag--;
};
Data peek()
{
if(top[mType] < 0)
{
throw "Empty Stack";
} else {
return data[top[mType]].data;
}
};
bool isEmpty(){return top[mType] >= 0;};
private:
static Node data[SIZE];
int mType;
static int top[3];
static int tag;
};
Node Stack::data[SIZE];
int Stack::tag = -1;
int Stack::top[3] = {-1, -1, -1};