2015年9月28日星期一

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 12 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.



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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);
        }
    }
};









没有评论:

发表评论