C++ 数据结构实现两个栈实现一个队列
栈为后进先出，队列为先进先出
用两个栈实现一个队列。是一个比较经典的问题。
看到这个问题，我的第一个解题思路为：
定义两个栈，s1,s2。s1作为入队列栈，s2作为出队列栈；
入队列：每次入队列的时候，将数值压入s1栈中；
出队列：出队列时，将s1中的所有数据，压进s2栈中，然后删除s2的栈顶数据，然后再将s2中的剩余数据压入s1中。
在这其中s1是一个存储空间，s2是一个辅助空间。
进一步想一下上述办法，在出队列时，每一次都要将s1倒进s2，然后删除s2栈顶后又将s2的数据倒入s1;有另一个思路可以减少倒的次数；
入队列时：将数据压进s1;
出队列时：判断如果s2为空，那么将s1中的数据，压进s2中，然后删除s2栈顶，如果s2不为空那么再删除s2的栈顶即可；
并且还可以优化，优化如下：
出队列时，判断如果s2为空，那么将s1中n-1个数据，压进s2中，然后删除s1中的栈顶，如果s2不为空那么直接删除s2的栈顶即可；
优化版的c++实现如下：
|
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
#include<iostream> using namespace std; #include<stack> //栈 后进先出 队列 先进先出 template<class T> class Queue { public: /*T Pop_back() { if (s2.size() <= 0) { while(s1.size() > 0) { T& temp = s1.top(); s1.pop(); s2.push(temp); } } if (s2.size() == 0) throw new exception("queue is empty "); T tep = s2.top(); s2.pop(); return tep; }*/ T Pop_back() //比上面少一次出栈 { if (s2.size() <= 0) { while (s1.size() > 1) { T& temp = s1.top(); s1.pop(); s2.push(temp); } T tep = s1.top(); s1.pop(); return tep; } else{ T tep = s2.top(); s2.pop(); return tep; } } void Push_back(const T& value) { s1.push(value); } bool Empty() { return (s1.empty() && s2.empty()); } protected: stack<T> s1; stack<T> s2; }; void TextQueue() { Queue<int> q1; q1.Push_back(1); q1.Push_back(2); q1.Push_back(3); q1.Push_back(4); cout << q1.Pop_back() << endl; cout << q1.Pop_back() << endl; cout << q1.Pop_back() << endl; cout << q1.Pop_back() << endl; } |
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://blog.csdn.net/he_shuai20/article/details/62892260
