C++利用两个栈实现队列的方法

时间:2022-05-15 08:07:12

1. 基础

队列:先进先出,即插入数据在队尾进行,删除数据在队头进行;

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

2. 思路

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

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

C++利用两个栈实现队列的方法

3. 代码

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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. 参考文献

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对服务器之家的支持。

原文链接:https://blog.csdn.net/alxe_made/article/details/89886453