用两个栈实现队列

剑指OFFER题7------按牛客网通过率排序

时间：2018.10.16.2149
作者：Waitt

题目

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

时间限制：1秒 空间限制：32768K 热度指数：313614

解答

stack(栈)，是一种仅能够在栈顶插入和删除元素的一种数据结构，而且仅栈顶元素可见。
queue(队列)，是一种在队尾插入元素，在队头删除元素的一种数据结构。
C++中使用stack<>，需要包含头文件include<stack>。

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

    int pop() {
        int n=stack1.size();
        for(int i=0;i<n;i++)
        {
            int t=stack1.top();
            stack2.push(t);
            stack1.pop();
        }
        int b=stack2.top();
        stack2.pop();
        for(int i=0;i<n-1;i++)
        {
            int t=stack2.top();
            stack1.push(t);
            stack2.pop();
        }
        return b;
    }

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

小知识点

TIPS 1

stack 模板类的定义在<stack>头文件中。
stack 模板类需要两个模板参数，一个是元素类型，一个容器类型，但只有元素类型是必要的，在不指定容器类型时，默认的容器类型为deque。
定义stack 对象的示例代码如下：
stack s1;
stack s2;

stack 的基本操作有：
empty() 堆栈为空则返回真
pop() 移除栈顶元素
push(x) 在栈顶增加元素
size() 返回栈中元素数目
top() 返回栈顶元素

TIPS 2

queue 模板类的定义在<queue>头文件中。
与stack 模板类很相似，queue 模板类也需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为deque 类型。
定义queue 对象的示例代码如下：
queue q1;
queue q2;

queue 的基本操作有：
入队，如例：q.push(x); 将x 接到队列的末端。
出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。
访问队首元素，如例：q.front()，即最早被压入队列的元素。
访问队尾元素，如例：q.back()，即最后被压入队列的元素。
判断队列空，如例：q.empty()，当队列空时，返回true。
访问队列中的元素个数，如例：q.size()

TIPS 3

stack(栈)与queue(队列)的区别详见：https://www.cnblogs.com/qigaohua/p/5803730.html