1. 基础
队列：先进先出，即插入数据在队尾进行，删除数据在队头进行；
栈：后进先出，即插入与删除数据均在栈顶进行。
2. 思路
两个栈实现一个队列的思想：用pushStack栈作为push数据的栈，用popStack栈作为pop数据的栈。
3. 代码
#include <iostream>
#include <stack>
#include <exception>
template<class T> class MyQueue {
public:
void push(const T& num); // 入队列
T pop(); // 出队列
T top();
private:
std::stack<T> pushStack;
std::stack<T> popStack;
};
template<typename T>
void MyQueue<T>::push(const T& num) {
pushStack.push(num);
}
template<typename T>
T MyQueue<T>::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<typename T>
T MyQueue<T>::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<int> 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;
}
4. 参考文献
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对脚本之家的支持。
