0%

两个栈实现队列 (C++)

概述

栈先进后出,一般用数组实现
队列先进先出,一般用链表实现
考虑到最终目的是实现队列,自定义栈,使用链表结构

原理

参照How to implement a queue using two stacks?
two-stacks-to-implement-queue

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void push_back(E it)
{
inbox.push(it);
size++;
}

E pop_front()
{
if (outbox.empty())
{
while (!inbox.empty())
{
outbox.push(inbox.pop());
}
}
size--;
return outbox.pop();
}

Code

stl 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
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

template <typename E>
class Queue
{
private:
stack<E> inbox;
stack<E> outbox;

public:
int size = 0;

void push_back(E it)
{
inbox.push(it);
size++;
}

E pop_front()
{
if (outbox.empty())
{
while (!inbox.empty())
{
E tmp = inbox.top();
outbox.push(tmp);
inbox.pop();
}
}
size--;
E tmp = outbox.top();
outbox.pop();
return tmp;
}
};

int main()
{
Queue<int> que;
//push 01234
for (int i = 0; i < 5; i++)
{
que.push_back(i);
}
//pop 012
for (int i = 0; i < 3; i++)
{
cout << que.pop_front() << endl;
}
//push 78
for (int i = 7; i < 9; i++)
{
que.push_back(i);
}
//pop all left elements (3478)
int len = que.size;
for (int i = 0; i < len; i++)
{
cout << que.pop_front() << endl;
}

return 0;
}

自实现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
#include <iostream>
using namespace std;

//Linked Node
template <typename E>
class Node
{
public:
E data;
struct Node<E> *next;
Node<E>()
{
next = NULL;
}

Node(E it, Node<E> *_next)
{
data = it;
next = _next;
}
};
//Linked Based Stack
template <typename E>
class Stack
{
private:
Node<E> *head;
int size;
void init()
{
head = new Node<E>;
size = 0;
}
public:
Stack()
{
init();
}
bool empty()
{
return size == 0;
}
E top()
{
return head->data;
}
void push(E it)
{
head = new Node<E>(it, head);
size++;
}
E pop()
{
E tmp = top();
size--;
Node<E> *temphead = head;
head = head->next;
delete temphead;
return tmp;
}
};
//Queue implement
template <typename E>
class Queue
{
private:
Stack<E> inbox;
Stack<E> outbox;

public:
int size = 0;

void push_back(E it)
{
inbox.push(it);
size++;
}

E pop_front()
{
if (outbox.empty())
{
while (!inbox.empty())
{
outbox.push(inbox.pop());
}
}
size--;
return outbox.pop();
}
};

int main()
{
Queue<int> que;
//push 01234
for (int i = 0; i < 5; i++)
{
que.push_back(i);
}
//pop 012
for (int i = 0; i < 3; i++)
{
cout << que.pop_front() << endl;
}
//push 78
for (int i = 7; i < 9; i++)
{
que.push_back(i);
}
//pop all left elements (3478)
int len = que.size;
for (int i = 0; i < len; i++)
{
cout << que.pop_front() << endl;
}

return 0;
}