剑指offer C ++双栈实现队列

1. 基础

队列：先进先出，即插入数据在队尾进行，删除数据在队头进行；

栈：后进先出，即插入与删除数据均在栈顶进行。

2. 思路
两个栈实现一个队列的思想：用pushStack栈作为push数据的栈，用popStack栈作为pop数据的栈。

只要是对队列进行push操作，就将数据push入pushStack栈中。
要实现队列的pop操作，有二点原则，如果popStack为空的话那么我们就将pushStack所有的元素放到popStack中，然后取popStack栈顶元素就是队列的队头；如果popStack不为空的话，我们就直接获取popStack的栈顶元素。
对于top操作来说和pop操作类似，只是最后一步不用pop了。

3. 代码

// ReverseList.cpp : 定义控制台应用程序的入口点。
//#include <iostream>
#include <Stack>
using namespace std;class CQueue
{
public:CQueue() {}void appendTail(int value) {Sin.push(value);}int deleteHead() {if (Sout.empty()) {while (!Sin.empty()) {Sout.push(Sin.top());Sin.pop();}}if (!Sout.empty()) {int res = Sout.top();Sout.pop();return res;}else {return -1;}}stack<int> Sin, Sout;
};int main(int argc, char* argv[])
{CQueue test;test.appendTail(1);test.appendTail(2);test.appendTail(3);test.appendTail(4);test.appendTail(5);test.appendTail(6);test.appendTail(7);int result = test.deleteHead();std::cout << "result:" << result << std::endl;result = test.deleteHead();std::cout << "result:" << result << std::endl;result = test.deleteHead();std::cout << "result:" << result << std::endl;result = test.deleteHead();std::cout << "result:" << result << std::endl;result = test.deleteHead();std::cout << "result:" << result << std::endl;result = test.deleteHead();std::cout << "result:" << result << std::endl;result = test.deleteHead();std::cout << "result:" << result << std::endl;return 0;
}