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};

Comments

comments powered by Disqus