C++利用两个栈实现队列的方法-创新互联

1. 基础

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

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

2. 思路

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

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

3. 代码

#include 
#include 
#include 

template class MyQueue {
 public:
 void push(const T& num); // 入队列
 T pop(); // 出队列
 T top();
 private:
 std::stack pushStack;
 std::stack popStack;
};
template
void MyQueue::push(const T& num) {
 pushStack.push(num);
}
template
T MyQueue::pop() {
 if (pushStack.empty() && popStack.empty()) { // 如果二个栈都为空
 throw std::runtime_error("queue is empty");
 } else if (popStack.empty()) { // 如果popStack为空,将pushStack全部元素倒popStack
 while (!pushStack.empty()) {
 T data = pushStack.top(); // 获取pushStack栈顶元素
 pushStack.pop(); // 出栈
 popStack.push(data);
 }
 }
 T data = popStack.top();
 popStack.pop();
 return data;
}
template
T MyQueue::top() {
 if (pushStack.empty() && popStack.empty()) { // 如果二个栈都为空
 throw std::runtime_error("queue is empty");
 } else if (popStack.empty()) { // 如果popStack为空,将pushStack全部元素倒popStack
 while (!pushStack.empty()) {
 T data = pushStack.top(); // 获取pushStack栈顶元素
 pushStack.pop(); // 出栈
 popStack.push(data);
 }
 } else { // 如果popStack不为空的话直接返回popStack栈顶
 T data = popStack.top();
 return data;
 }
}
int main() {
 MyQueue myQueue1;
 myQueue1.push(1);
 myQueue1.push(2);
 myQueue1.push(3);
 myQueue1.push(4);
 std::cout << "current pop is:" << myQueue1.pop() << std::endl;
 std::cout << "current pop is:" << myQueue1.pop() << std::endl;
 std::cout << "current pop is:" << myQueue1.pop() << std::endl;
 std::cout << "current pop is:" << myQueue1.pop() << std::endl;
 std::cout << "current pop is:" << myQueue1.pop() << std::endl;

 return 0;
}

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。