栈和队列的互相转换

缘起

栈和队列可以互相转换.

分析

说白了就是倒来倒去的游戏

是不是秒懂?

2个队列实现栈

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
#include "stdafx.h"
#include <iostream>
#include <queue>

//#define LOCAL

using namespace std;

template<typename T> class Stack {
	queue<T> q1,q2;
public:
	void push(T e)
	{
		q1.push(e);
	}

	T pop() // 弹栈 并且返回弹栈元素
	{
		while(q1.size()>1)
		{
			q2.push(q1.front());
			q1.pop();
		}
		T result =  q1.front();
		q1.pop();
		while(!q2.empty()) // 将 q2中的元素逐一倒回q1中去
		{
			q1.push(q2.front());
			q2.pop();
		}
		return result;
	}

	bool empty()
	{
		return q1.empty();
	}
};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	Stack<int> s;
	s.push(1);
	s.push(2);
	s.push(3);
	while(!s.empty())cout << s.pop();
	return 0;
}

2个栈实现队列

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
#include "stdafx.h"
#include <iostream>
#include <stack>

//#define LOCAL

using namespace std;

template<typename T> class Queue {
	stack<T> s1,s2;
public:
	void push(T e)
	{
		s1.push(e);
	}

	T pop() // 出队列, 并且删除队首元素
	{
		while(s1.size()>1)
		{
			s2.push(s1.top());
			s1.pop();
		}
		T e = s1.top();
		s1.pop();
		while(!s2.empty())
		{
			s1.push(s2.top());
			s2.pop();
		}
		return e;
	}

	bool empty()
	{
		return s1.empty();
	}
};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	Queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	while(!q.empty())
	{
		cout << q.pop();
	}
	return 0;
}