1. 基础
成都创新互联公司企业建站,十余年网站建设经验，专注于网站建设技术，精于网页设计，有多年建站和网站代运营经验，设计师为客户打造网络企业风格，提供周到的建站售前咨询和贴心的售后服务。对于网站制作、做网站中不同领域进行深入了解和探索，创新互联在网站建设中充分了解客户行业的需求，以灵动的思维在网页中充分展现，通过对客户行业精准市场调研，为客户提供的解决方案。
队列：先进先出，即插入数据在队尾进行，删除数据在队头进行；
栈：后进先出，即插入与删除数据均在栈顶进行。
2. 思路
两个栈实现一个队列的思想：用pushStack栈作为push数据的栈，用popStack栈作为pop数据的栈。
- 只要是对队列进行push操作，就将数据push入pushStack栈中。
- 要实现队列的pop操作，有二点原则，如果popStack为空的话那么我们就将pushStack所有的元素放到popStack中，然后取popStack栈顶元素就是队列的队头；如果popStack不为空的话，我们就直接获取popStack的栈顶元素。
- 对于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;
}
4. 参考文献
- 用两个栈实现一个队列——我作为面试官的小结
- C++之用两个栈实现一个队列
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对创新互联的支持。
当前文章：C++利用两个栈实现队列的方法
转载来源：
http://cdkjz.cn/article/ghdces.html
