两个栈实现一个队列

　　这道题面试的时候经常遇到，特此收录。全部代码来自《剑指offer》。

template <typename T> 
class CQueue
{
public:
    CQueue(void);
    ~CQueue(void);

    void appendTail(const T &node);
    T deleteHead();
private:
    stack<T> stack1;
    stack<T> stack2;
};

template <typename T>
void CQueue<T>::appendTail(const T &node)
{
    stack1.push(node);
}

template <typename T>
T CQueue<T>::deleteHead()
{
    if (stack2.size() <= 0)
    {
        while (stack1.size() > 0)
        {
            T &data = stack1.top();
            stack1.pop();
            stack2.push(data);
        }
    }
    if(stack2.size() == 0)
        throw new exception("queue is empty");
    T head = stack2.top();
    stack2.pop();
    return head;
}

LeetCode上一道题 Implement Queue using Stacks

 solution：

class Queue {
private:
    stack<int> stk1, stk2;
public:
    // Push element x to the back of queue.
    void push(int x) {
        stk1.push(x);
    }

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

    // Get the front element.
    int peek(void) {
        if (stk2.empty())
        {
            while (stk1.size() > 0)
            {
                stk2.push(stk1.top());
                stk1.pop();
            }
        }
        return stk2.top();
    }

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

PS:

　　两个队列实现一个栈http://www.cnblogs.com/xwdreamer/archive/2012/05/03/2480651.html

LeetCode上一道题： Implement Stack using Queues

solution：    //使用一个队列实现栈

class Stack {
private:
    queue<int> que;
public:
    // Push element x onto stack.
    void push(int x) {
        que.push(x);
        for (int i = 0; i < que.size()-1; ++i)
        {
            que.push(que.front());
            que.pop();
        }
    }

    // Removes the element on top of the stack.
    void pop() {
        que.pop();
    }

    // Get the top element.
    int top() {
        return que.front();
    }

    // Return whether the stack is empty.
    bool empty() {
        return que.empty();
    }
};