How to implement 3 stacks with one array?

Question

Sometimes, I come across the following interview question: How to implement 3 stacks with one array ? Of course, any static allocation is not a solution.

Answer 1

Python

class Stack:

    def __init__(self):
        self.pos_1 = 0
        self.pos_2 = 1
        self.pos_3 = 2
        self.stack = [None, None, None]

    def pop_1(self):
        if self.pos_2 - 1 > 0:
            to_ret = self.stack.pop(self.pos_1)
            self.pos_2 -= 1
            self.pos_3 -= 1
        return to_ret

    def push_1(self, value):
        self.stack.insert(self.pos_1, value)
        self.pos_2 += 1
        self.pos_3 += 1
        return None

    def pop_2(self):
        if self.pos_2 - 1 < self.pos_3:
            to_ret = self.stack.pop(self.pos_2)
            self.pos_3 -= 1
        return to_ret

    def push_2(self, value):
        self.stack.insert(self.pos_2, value)
        self.pos_3 += 1
        return None

    def pop_3(self):
        if self.pos_3 - 1 > self.pos_2:
            to_ret = self.stack.pop(self.pos_3)
        return to_ret

    def push_3(self, value):
        self.stack.insert(self.pos_3, value)
        return None

if __name__ == "__main__":
    stack = Stack()
    stack.push_2(22)
    stack.push_1(1)
    stack.push_1(2)
    print stack.pop_1()
    print stack.pop_1()
    print stack.pop_2()

prints: 2 1 22

Answer 2

enum stackId{LEFT, MID, RIGHT };

class threeStacks {

int* arr;

int leftSize;
int rightSize;
int midSize;
int mid;
int maxSize;
public:
    threeStacks(int n):leftSize(0), rightSize(0), midSize(0), mid(n/2), maxSize(n)
    {
        arr = new int[n];
    }

    void push(stackId sid, int val){
        switch(sid){
            case LEFT:
                pushLeft(val);
            break;

            case MID:
                pushMid(val);
            break;

            case RIGHT:
                pushRight(val);
        }
    }

    int pop(stackId sid){
        switch(sid){
            case LEFT:
                return popLeft();
            case MID:
                return popMid();
            case RIGHT:
                return popRight();
        }
    }


    int top(stackId sid){
        switch(sid){
            case LEFT:
                return topLeft();
            case MID:
                return topMid();
            case RIGHT:
                return topRight();
        }
    }

    void pushMid(int val){
        if(midSize+leftSize+rightSize+1 > maxSize){
            cout << "Overflow!!"<<endl;
            return;
        }
        if(midSize % 2 == 0){
            if(mid - ((midSize+1)/2) == leftSize-1){
                //left side OverFlow
                if(!shiftMid(RIGHT)){
                    cout << "Overflow!!"<<endl;
                    return; 
                }
            }
            midSize++;
            arr[mid - (midSize/2)] = val;
        }
        else{
            if(mid + ((midSize+1)/2) == (maxSize - rightSize)){
                //right side OverFlow
                if(!shiftMid(LEFT)){
                    cout << "Overflow!!"<<endl;
                    return; 
                }
            }
            midSize++;
            arr[mid + (midSize/2)] = val;                           
        }
    }

    int popMid(){
        if(midSize == 0){
            cout << "Mid Stack Underflow!!"<<endl;
            return -1;
        }
        int val;
        if(midSize % 2 == 0)
            val = arr[mid - (midSize/2)];
        else
            val = arr[mid + (midSize/2)];
        midSize--;
        return val;
    }

    int topMid(){
        if(midSize == 0){
            cout << "Mid Stack Underflow!!"<<endl;
            return -1;
        }
        int val;
        if(midSize % 2 == 0)
            val = arr[mid - (midSize/2)];
        else
            val = arr[mid + (midSize/2)];
        return val;
    }

    bool shiftMid(stackId dir){
        int freeSpace;
        switch (dir){
            case LEFT:
                freeSpace = (mid - midSize/2) - leftSize;
                if(freeSpace < 1)
                    return false;               
                if(freeSpace > 1)
                    freeSpace /= 2;
                for(int i=0; i< midSize; i++){
                    arr[(mid - midSize/2) - freeSpace + i] = arr[(mid - midSize/2) + i];
                }
                mid = mid-freeSpace;
            break;
            case RIGHT:
                freeSpace = maxSize - rightSize - (mid + midSize/2) - 1;
                if(freeSpace < 1)
                    return false;               
                if(freeSpace > 1)
                    freeSpace /= 2;
                for(int i=0; i< midSize; i++){
                    arr[(mid + midSize/2) + freeSpace - i] = arr[(mid + midSize/2) - i];
                }
                mid = mid+freeSpace;
            break;              
            default:
                return false;
        }
    }

    void pushLeft(int val){
        if(midSize+leftSize+rightSize+1 > maxSize){
            cout << "Overflow!!"<<endl;
            return;
        }
        if(leftSize == (mid - midSize/2)){
            //left side OverFlow
            if(!shiftMid(RIGHT)){
                cout << "Overflow!!"<<endl;
                return; 
            }
        }
        arr[leftSize] = val;
        leftSize++;
    }

    int popLeft(){
        if(leftSize == 0){
            cout << "Left Stack Underflow!!"<<endl;
            return -1;
        }
        leftSize--;
        return arr[leftSize];
    }

    int topLeft(){
        if(leftSize == 0){
            cout << "Left Stack Underflow!!"<<endl;
            return -1;
        }
        return arr[leftSize - 1];
    }

    void pushRight(int val){
        if(midSize+leftSize+rightSize+1 > maxSize){
            cout << "Overflow!!"<<endl;
            return;
        }
        if(maxSize - rightSize - 1 == (mid + midSize/2)){
            //right side OverFlow
            if(!shiftMid(LEFT)){
                cout << "Overflow!!"<<endl;
                return; 
            }
        }
        rightSize++;
        arr[maxSize - rightSize] = val;
    }

    int popRight(){
        if(rightSize == 0){
            cout << "Right Stack Underflow!!"<<endl;
            return -1;
        }
        int val = arr[maxSize - rightSize];
        rightSize--;
        return val;
    }

    int topRight(){
        if(rightSize == 0){
            cout << "Right Stack Underflow!!"<<endl;
            return -1;
        }
        return arr[maxSize - rightSize];
    }

};