Implement Queue by Two Stacks

Description

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.

Example
push(1)
pop()     // return 1
push(2)
push(3)
top()     // return 2
pop()     // return 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.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

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
        int topval = top();
        stack2.pop();
        return topval;   
    }
    int top() {
        // write your code here
        int topval;
        fillback();
        topval = stack2.top();
        return topval;
    }
private:
    void fillback() {
        // if stack2 is not empty, do noting
        if (!stack2.empty()) {
            return;
        }
        // put stack1 to stack2
        while (!stack1.empty()) {
            // int tmp = src.top();
            // src.pop();
            // dst.push(tmp);
            stack2.push(stack1.top());
            stack1.pop();
        }
        return;
    }
};

Similar problems

x

Tags

x