剑指Offer-9：用两个栈实现队列-CSDN博客

本文链接：https://blog.csdn.net/Koala_Tree/article/details/78865749

题目：

用两个栈来实现一个队列。实现该队列的两个函数appendTail和deleteHead，分别完成在队列尾部插入节点和在队列头部删除节点的功能。队列中的元素为int类型。

问题解析：

栈：后入先出；队列：先入先出。

链接：

剑指Offer（第2版）：P68

思路标签：

数据结构：栈、队列

栈1元素入栈2，先入先出。

解答：

1. C++

使用两个栈来实现队列的操作。
对于栈来说，数据是后入先出，而将栈1中已经入栈的数据弹出再如栈2的话，数据就反过来了，栈2的栈顶是最先入栈1的元素。
对于元素出队列：当栈2不为空时，直接弹出栈2的栈顶元素；当栈2为空时，先将栈1的元素弹出再入栈到栈2中，弹出栈2的栈顶元素；
对于元素入队列：直接将元素压入栈1。

两个栈实现队列：

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if(stack2.size() <= 0){
            while(stack1.size()>0){
                int data = stack1.top();
                stack1.pop();
                stack2.push(data);
            }
        }

        //if(stack2.size() == 0)
        //    throw new exception("queue is empty.");

        int head = stack2.top();
        stack2.pop();

        return head;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

两个队列实现栈：

class Solution
{
public:
    void push(int node) {
        if(!queue1.empty){
            queue2.push(node);

            while(!queue1.empty()){
                queue2.push(queue1.front());
                queue1.pop();
            }
        }
        else{
            queue1.push(node);

            while(!queue2.empty()){
                queue1.push(queue2.front());
                queue2.pop();
            }
        }
    }

    void pop() {
        if(queue1.empty() && queue2.empty())
            throw new exception("stack is empty!");
        else if(!queue1.empty())
            queue1.pop();
        else
            queue2.pop();
    }

    int top() {
        if (!queue1.empty()) 
            return queue1.front();
        else 
            return queue2.front();
    }


    bool empty() {
        return (queue1.empty() && queue2.empty());
    }

private:
    queue<int> queue1;
    queue<int> queue2;
};

C++相关：

template 模板2栈变队列实现：

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& element)
{
    stack1.push(element);
}

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;
}