推荐订阅源

两个栈实现队列

可以知道栈是先进后出的，把元素先压进第一个栈，之后再把元素抛出，压进第二栈，从第二个栈抛出的元素满足先进先出的原则。

实现queue的push操作：直接把元素都压入第一个栈即可。

实现queue的pop操作：1：判断第二个栈是否有元素？2：若第二个栈有元素，抛出第二个栈的栈顶元素即可。3：若第二个栈没元素，把第一个栈的所有元素都压进第二个栈，再抛出第二个栈的栈顶元素。

实现queue的front操作：原理同pop操作，只要返回第二个栈的栈顶元素即可。

实现queue的back操作：返回第一个栈的栈顶元素即可，若第一个栈无元素，需要先把第二个栈的所有元素压进第一个栈，再返回第一个栈的栈顶元素。

参考代码：

template<typename T>
class queue {
private:
    stack<T>st1, st2;
public:
    void push(T x);
    void pop();
    T front();
    T back();
    int size();
    bool empty();
};
template<typename T>
int queue<T>::size() {
    return st1.size() + st2.size();
}
template<typename T>
bool queue<T>::empty() {
    return st1.empty() && st2.empty();
}
template<typename T>
void queue<T>::push(T x) {
    st1.push(x);
}
template<typename T>
void queue<T>::pop() {
    if (st2.empty()) {
        while (!st1.empty()) {
            st2.push(st1.top());
            st1.pop();
        }
    }
    if (!st2.empty()) {
         st2.pop();
    }
}
template<typename T>
T queue<T>::front() {
    assert(!st1.empty() || !st2.empty());
    if (st2.empty()) {
        while (!st1.empty()) {
            st2.push(st1.top());
            st1.pop();
        }
    }
    return st2.top();
}
template<typename T>
T queue<T>::back() {
    assert(!st1.empty() || !st2.empty());
    if (st1.empty()) {
        while (!st2.empty()) {
            st1.push(st2.top());
            st2.pop();
        }
    }
     return st1.top();

}