栈的数组实现

转自:http://blog.csdn.net/qq_20366761/article/details/70053813

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
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
using namespace std;

#define MAXSIZE 0xffff

template<class Type>
class my_stack {
private:
int top;
int size;
Type* array;
public:
//默认大小
my_stack():top(-1), size(MAXSIZE) {
array = new Type[size];
if (array == NULL) {
cerr << "动态存储分配失败!" << endl;
exit(1);
}
}
//自定义大小
my_stack(int stackSize):top(-1), size(stackSize) {
array = new Type[size];
if (array == NULL) {
cerr << "动态存储分配失败!" << endl;
exit(1);
}
}
~my_stack() {
delete[] array;
}
bool Empty();
void Push(Type tp);
void Pop();
Type Top();
int Size();
};
template<class Type>
bool my_stack<Type>::Empty() {
if (top == -1) {
return true;
}
else {
return false;
}
}
template<class Type>
void my_stack<Type>::Push(Type tp) {
if (top + 1 < size) {
array[++top] = tp;
}
else {
cout << "栈满!" << endl;
exit(1);
}
}
template<class Type>
void my_stack<Type>::Pop() {
if (top >= 0) {
top--;
}
else {
cout << "栈空!" << endl;
exit(1);
}
}
template<class Type>
Type my_stack<Type>::Top() {
if (top != -1) {
return array[top];
}
else {
cout << "栈空!" << endl;
exit(1);
}
}
template<class Type>
int my_stack<Type>::Size() {
return top + 1;
}
int main() {
my_stack<int> st;
st.Push(1);
cout << st.Size() << endl;
cout << st.Top() << endl;
st.Pop();
cout << st.Size() << endl;
return 0;
}

队列的链实现
转自:https://www.cnblogs.com/qg-whz/p/5171123.html

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
#include<iostream>
#include<stdio.h>
using namespace std;
template <class Type>
struct queueItem {
Type value;
queueItem<Type>* next;
queueItem() = default;
queueItem(Type t):value(t),next(NULL){}
};
template <class Type>
class my_queue {
private:
int count;
queueItem<Type>* phead;
queueItem<Type>* pend;
public:
my_queue() :phead(NULL), pend(NULL), count(0) {
phead = new queueItem<Type>();
pend = phead;
count = 0;
}
~my_queue() {
while (phead->next != NULL) {
phead = phead->next;
}
}
bool IsEmpty();
int Size();
void Push(Type tp);
void Pop();
Type Front();
};
template <class Type>
bool my_queue<Type>::IsEmpty() {
return count == 0;
}
template <class Type>
int my_queue<Type>::Size() {
return count;
}
template <class Type>
void my_queue<Type>::Push(Type tp) {
queueItem<Type>* pnode = new queueItem<Type>(tp);
pend->next = pnode;
pend = pnode;
count++;
}
template <class Type>
void my_queue<Type>::Pop() {
if (count == 0) {
return;
}
queueItem<Type>* pnode = phead->next;
phead->next = phead->next->next;
delete pnode;
count--;
}
template <class Type>
Type my_queue<Type>::Front() {
return phead->next->value;
}
int main() {
my_queue<int> qu;
qu.Push(1);
if (!qu.IsEmpty()) {
cout << qu.Size() << endl;
}
qu.Pop();
cout << qu.Size() << endl;
return 0;
}

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

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
#include<stdio.h>
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
class solutionStoQ {
stack<int> stack1;
stack<int> stack2;
public:
void push(int a) {
stack1.push(a);
}
int pop() {
if (stack2.empty()) {
while (!stack1.empty()) {
int a = stack1.top();
stack1.pop();
stack2.push(a);
}
}
int tmp = stack2.top();
stack2.pop();
return tmp;
}
};
class solutionQtoS {
queue<int> queue1;
queue<int> queue2;
public:
void push(int a) {
if (queue1.empty()) {
queue2.push(a);
}
else {
queue1.push(a);
}
}
int pop() {
if (queue1.empty()) {
while (queue2.size() > 1) {
queue1.push(queue2.front());
queue2.pop();
}
int tmp= queue2.front();
queue2.pop();
return tmp;
}
else {
while (queue1.size() > 1) {
queue2.push(queue1.front());
queue1.pop();
}
int tmp = queue1.front();
queue1.pop();
return tmp;
}
}
};
int main() {
solutionStoQ s1;
s1.push(2);
cout << s1.pop() << endl;
solutionQtoS s2;
s2.push(20);
cout << s2.pop() << endl;
return 0;
}