Implement Three Stacks by Single Array (Ladder)

Description

Implement three stacks by single array. You can assume the three stacks has the same size and big enough, you don't need to care about how to extend it if one of the stack is full.

Example
ThreeStacks(5)  // create 3 stacks with size 5 in single array. stack index from 0 to 2
push(0, 10) // push 10 in the 1st stack.
push(0, 11)
push(1, 20) // push 20 in the 2nd stack.
push(1, 21)
pop(0) // return 11
pop(1) // return 21
peek(1) // return 20
push(2, 30)  // push 30 in the 3rd stack.
pop(2) // return 30
isEmpty(2) // return true
isEmpty(0) // return false

Assumption

How large?
corner case, isEmpty, size = 0, beyond size

Link

Lintcode_ladder

Method

1. use Vector<int> recording sequerence, size = longest StackNum * groupSize
2. use doubled LinkList, size = actual number, but doubled LinkList = 3 * size of int

Example

1. 1

class ThreeStacks {
public:
    // ---------------------------------------------------------
    // Version 1, 
    // stackbuffer: index 0 -> size * 3
    // stackNum = 0 : 0, 3, 6, 9 ....
    // stackNum = 1 : 1, 4, 7, 10 ....
    // stackNum = 2 : 2, 5, 8, 11 ....
    // So, index = curStack[stackNum] * groupSize + stackNum
    // ---------------------------------------------------------
    // Version 2, 
    // save node as doubled linkList
    // ---------------------------------------------------------
    ThreeStacks(int size) {
        // do intialization if necessary
        group = 3;
        buffer.reserve(size * group);
        curStack.resize(group, -1);
        stackSize = size;
    }
    void push(int stackNum, int value) {
        // Write your code here
        // Push value into stackNum stack
        if (stackNum < group) {
            curStack[stackNum]++;
            int index = (curStack[stackNum]) * group + stackNum;
            buffer[index] = value;  
        }
    }
    int pop(int stackNum) {
        // Write your code here
        // Pop and return the top element from stackNum stack
        if (stackNum >= group) {
            return INT_MIN;
        }
        if (isEmpty(stackNum)) {
            return INT_MIN;
        }
        int index = (curStack[stackNum]) * group + stackNum;
        curStack[stackNum]--;
        return buffer[index];
    }
    int peek(int stackNum) {
        // Write your code here
        // Return the top element
        if (stackNum >= group) {
            return INT_MIN;
        }
        if (isEmpty(stackNum)) {
            return INT_MIN;
        }
        int index = (curStack[stackNum]) * group + stackNum;
        return buffer[index];
    }
    bool isEmpty(int stackNum) {
        // Write your code here
        if (stackNum >= group) {
            return true;
        }
        int index = (curStack[stackNum]) * group + stackNum;
        if (index < 0) {
            return true;
        } else {
            return false;
        }
    }
private:
    vector<int> buffer;
    vector<int> curStack;
    int group;
    int stackSize;
};

Similar problems

x

Tags

x