两个栈实现一个队列 和 两个队列实现一个栈

两个栈实现一个队列
要求:只能使用栈的pop和push,以及测试栈是否为空三个操作。
实现思路:
队列里面使用stack one 和 stack two。
进队列时,直接进入栈one即可。
出队列时,从two弹出一个元素,如果two里面的元素为空,则将one里面的元素依次弹出并压入two中,再从two弹出一个元素返回。

用STL里面的stack模拟实现queue的代码如下:

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stack>
using std::stack;

template<class T> class CQueue
{
public:
CQueue()
{
nSize = 0;
}

void clear()
{
while (!one.empty())
{
one.pop();
}
while (!two.empty())
{
two.pop();
}
}

void push(const T& t)
{
one.push(t);
++nSize;
}

void pop()
{
if (two.empty())
{
while (!one.empty())
{
two.push(one.top());
one.pop();
}
}
two.pop();
--nSize;
}

T& front()
{
if (two.empty())
{
while (!one.empty())
{
two.push(one.top());
one.pop();
}
}
return two.top();
}

T& back()
{
return one.top();
}

bool empty()
{
return nSize == 0;
}

private:
stack<T> one;
stack<T> two;
int nSize;
};

#define MAX 20

int main()
{
CQueue<int> q;

srand(time(NULL));
for (int i = 0; i < MAX; ++i)
{
q.push(i);

if (rand() % 2)
{
printf("front: %d\n", q.front());
q.pop();
}
}

while (!q.empty())
{
printf("front: %d\n", q.front());
q.pop();
}

return 0;
}

两个队列实现一个栈
要求:只能使用从队列的尾部入和头部出,以及测试队列是否为空三个操作。
实现思路:
队列里面使用queue one 和 stack two。
进栈时,根据当前元素是全部存储在哪个队列而选择从one或者two的尾部进入。
出栈时,假设当前元素都存储在one里面,则不断出队列,直到队列为空之前的所有元素一次进入队列two,而one里面的最后一个元素作为栈弹出的值返回。
对于当前元素是存储在哪个队列里面,可以设置变量标记,初始化时候存储在one里面,操作一次,由于元素要倒转,则存储位置会变一次。

用STL里面的queue模拟实现的stack代码如下:

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

#include <stdio.h>
#include <queue>
using std::queue;

template<class T> class CStack
{
public:
CStack()
{
nSize = 0;
nTime = 1;
}

void clear()
{
while (!one.empty())
{
one.pop();
}
while (!two.empty())
{
two.pop();
}
}

void push(const T& t)
{
if (nTime % 2)
{
one.push(t);
}
else
{
two.push(t);
}
++nSize;
}

void pop()
{
if (nTime % 2)
{
while (!one.empty())
{
T t = one.front();
one.pop();
if (!one.empty())
{
two.push(t);
}
}
}
else
{
while (!two.empty())
{
T t = two.front();
two.pop();
if (!two.empty())
{
one.push(t);
}
}
}

nTime = (nTime + 1) % 2;
--nSize;
}

T& top()
{
if (nTime % 2)
{
while (!one.empty())
{
T t = one.front();
one.pop();
if (!one.empty())
{
two.push(t);
}
else
{
two.push(t);
nTime = (nTime + 1) % 2;
return two.back();
}
}
}
else
{
while (!two.empty())
{
T t = two.front();
two.pop();
if (!two.empty())
{
one.push(t);
}
else
{
one.push(t);
nTime = (nTime + 1) % 2;
return one.back();
}
}
}
}

bool empty()
{
return nSize == 0;
}

private:
queue<T> one;
queue<T> two;
int nSize;
int nTime;
};

#define MAX 20

int main()
{
CStack<int> stack;

for (int i = 0; i < MAX; ++i)
{
stack.push(i);
}

while (!stack.empty())
{
printf("top: %d\n", stack.top());
stack.pop();
}

return 0;
}