NO CODING NO LIFE: Stack

2015年9月28日星期一

Lintcode: Min Stack

Implement a stack with min() function, which will return the smallest number in the stack.

It should support push, pop and min operation all in O(1) cost.

Have you met this question in a real interview?

Yes

Example

Operations: push(1), pop(), push(2), push(3), min(), push(1), min() Return: 1, 2, 1

Note

min operation will never be called if there is no number in the stack

Reference my leetcode solution for the same problem:

class MinStack {
private:
    vector<int> data;
    int minV;
public:
    MinStack() {
        // do initialization if necessary
    }

    void push(int number) {
        // write your code here
        if(data.size() == 0) minV = number;
        else{
            int prev = minV + data.back();
            if(prev < minV) minV = prev;
        }
        data.push_back(number - minV);
    }

    int pop() {
        // write your code here
        int res = data.back() + minV;
        data.pop_back();
        if(data.back() < 0) minV = minV - data.back();
        return res;
    }

    int min() {
        // write your code here
        return ((data.back() + minV) < minV)?(data.back() + minV) : minV;
    }
};

Lintcode second:
Space: O(n)

class MinStack {
public:
    vector<int> data;
    vector<int> minData;
    MinStack() {
        // do initialization if necessary
    }

    void push(int number) {
        // write your code here
        data.push_back(number);
        if(minData.empty() || number <= minData.back()) minData.push_back(number);
    }

    int pop() {
        // write your code here
        if(data.back() == minData.back()) minData.pop_back();
        int res = data.back();
        data.pop_back();
        return res;
    }

    int min() {
        // write your code here
        return minData.back();
    }
};

Lintcode: Implement Queue by Two Stacks

As the title described, you should only use two stacks to implement a queue's actions.

The queue should support push(element), pop() and top() where pop is pop the first(a.k.a front) element in the queue.

Both pop and top methods should return the value of first element.

Have you met this question in a real interview?

Yes

Example

For push(1), pop(), push(2), push(3), top(), pop(), you should return 1, 2 and 2

Challenge

implement it by two stacks, do not use any other data structure and push, pop and top should be O(1) by AVERAGE.

class Queue {
   
public:
    stack<int> stack1;
    stack<int> stack2;
   
    Queue() {
        // do intialization if necessary
    }
 
    void push(int element) {
        // write your code here
        stack1.push(element);
    }
    
    int pop() {
        // write your code here
        move();
        int res;
        res = stack2.top();
        stack2.pop();
        return res;
    }

    int top() {
        // write your code here
        int res;
        move();
        res = stack2.top();
        return res;
    }
private:
    void move(){
        if(!stack2.empty()) return;
        while(!stack1.empty()){
            int temp;
            temp = stack1.top();
            stack1.pop();
            stack2.push(temp);
        }
    }
};