题目

implement-queue-using-stacks/

算法

* 直接模拟

* 优化

代码

* 直接模拟

class Queue {
public:
    // Push element x to the back of queue.
    void push(int x) {
        stack<int> tmp;
        while (!s.empty()) {
            tmp.push(s.top());
            s.pop();
        }
        s.push(x);
        while (!tmp.empty()) {
            s.push(tmp.top());
            tmp.pop();
        }
    }

    // Removes the element from in front of queue.
    void pop(void) {
        s.pop();
    }

    // Get the front element.
    int peek(void) {
        return s.top();
    }

    // Return whether the queue is empty.
    bool empty(void) {
        return s.empty();
    }

private:
    stack<int> s;
};

* 优化

class Queue {
public:
    // Push element x to the back of queue.
    void push(int x) {
        _new.push(x);
    }

    void shiftStack() {
        if (_old.empty()) {
            while (!_new.empty()) {
                _old.push(_new.top());
                _new.pop();
            }
        }
    }

    // Removes the element from in front of queue.
    void pop(void) {
        shiftStack();
        if (!_old.empty()) _old.pop();
    }

    // Get the front element.
    int peek(void) {
        shiftStack();
        if (!_old.empty()) return _old.top();
        return 0;
    }

    // Return whether the queue is empty.
    bool empty(void) {
        return _old.empty() && _new.empty();
    }

private:
    stack<int> _old, _new;
};