【C++/C】【学习笔记】只能存整型的栈(Stack)?泛型/模板编程(template)了解一下!
本文旨在实现三个目的:
1.为对数据结构——栈(Stack)的链表实现不熟悉的朋友再次进行讲解
2.介绍利用模板编程思想写出的栈(Stack)(链表实现)
3.同时检测自己对以上内容的理解是否到位
在往下读之前,可以参考这两篇文章,调整一下你心中对泛型编程的态度:
若以下拙见有误欢迎指正!
一、链表栈&模板类
相信对于栈的定义以及原理不需要我多加赘述,所以就简单描述一下实现思路:
①定义链表节点
②定义Stack类
③实现各功能函数
与通常操作不同的是,在①和②步骤中使用了模板编程:
1. 结构体定义对比:
2. 类定义对比:
3. 实例化对比:
使用模板编程,可以方便地使用自定类型的栈,大大提高工作效率,提高了代码复用性,在一些情况下使用可大量减少工作量。
当然,并不是说所有情况下模板编程都是最佳选择,可以参考文章开头转载的两篇文章。
二、代码实现
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
|
#include<iostream> #include<string> #include<cstdlib> using namespace std;
template < typename T>
struct node {
T ele;
struct node<T> *next;
}; template < typename T>
using Node = struct node<T>;
template < typename T>
using PNode = struct node<T>*;
template < typename T>
class Stack {
public :
//constructors
Stack();
//destructors
~Stack();
//show
void show_stk_HTB(); //从栈顶到栈底逐一显示栈中内容
void show_stk_BTH(); //从栈底到栈顶逐一显示栈中内容
//operation
void stk_pop(); //栈顶元素出栈
void stk_push(T newele); //自定类型新元素入栈
void stk_clr(); //清空栈
private :
int ele_num; //栈中元素数量
PNode<T> stk_head; //栈头指针
PNode<T> stk_pointer; //活动指针(工作指针)
bool IsEmpty; //判断栈是否为空
}; template < typename T>
Stack<T>::Stack() :ele_num(0), IsEmpty( true ) {
stk_head = new Node<T>;
stk_pointer = nullptr;
} template < typename T>
Stack<T>::~Stack() { stk_pointer = stk_head->next;
while (ele_num) {
stk_head->next = stk_pointer->next;
delete stk_pointer;
stk_pointer = stk_head->next;
ele_num--;
}
delete stk_head;
stk_pointer = nullptr;
stk_head = nullptr;
} template < typename T>
void Stack<T>::show_stk_HTB() {
if (IsEmpty) {
cout << "Empty Stack!" << endl;
return ;
}
cout << "Stack (Head To Bottom ordered):" << endl;
stk_pointer = stk_head->next;
for ( int i = 0; i < ele_num; i++) {
cout << "\t" << stk_pointer->ele << endl;
stk_pointer = stk_pointer->next;
}
} template < typename T>
void Stack<T>::show_stk_BTH() {
if (IsEmpty) {
cout << "Empty Stack!" << endl;
return ;
}
cout << "Stack (Bottom To Head ordered):" << endl;
stk_pointer = stk_head->next;
for ( int i = 0; i < ele_num; i++) {
for ( int j = i; j < ele_num - 1; j++) {
stk_pointer = stk_pointer->next;
}
cout << "\t" << stk_pointer->ele << endl;
stk_pointer = stk_head->next;
}
} template < typename T>
void Stack<T>::stk_pop() {
if (IsEmpty) {
cout << "Empty Stack!" << endl;
return ;
}
ele_num--;
IsEmpty = ele_num ? false : true ;
stk_pointer = stk_head->next;
stk_head->next = stk_pointer->next;
cout << stk_pointer->ele << " popped out!" << endl;
cout << "Current Stack element:" << ele_num << endl;
delete stk_pointer;
stk_pointer = nullptr;
} template < typename T>
void Stack<T>::stk_push(T newele) {
ele_num++;
IsEmpty = IsEmpty ? false : true ;
PNode<T> ele_new = new Node<T>; //易出错!
ele_new->ele = newele;
ele_new->next = stk_head->next;
stk_head->next = ele_new;
cout << "New element(" << newele << ") pushed in!" << endl;
cout << "Current Stack element:" << ele_num << endl;
} template < typename T>
void Stack<T>::stk_clr() {
stk_pointer = stk_head->next;
while (ele_num) {
stk_head->next = stk_pointer->next;
delete stk_pointer;
stk_pointer = stk_head->next;
ele_num--;
}
IsEmpty = ele_num ? false : true ;
if (IsEmpty) {
cout << "Stack Cleard!" << endl;
cout << "Current Stack element:" << ele_num << endl;
}
else cout << "Stack Clear Operation Failed!" << endl;
} |
=======================================================================
希望以上内容能为看到这里的你们提供一些帮助!同时,若文章有误,还望不吝赐教!
//Szp 2018.5.23