本文实例为大家分享了C语言利用模板实现简单的栈类(数组和单链表),供大家参考,具体内容如下
主要的功能是实现一个后进先出的列表,有入栈、出栈、返回大小、判空等基本功能
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
|
#pragma once
using namespace std;
const int MAXSIZE = 0xfff;
template < class type>
class Class_Linkstack
{
int top;
type* my_s;
int max_size;
public :
Class_Linkstack() :top(-1), max_size(MAXSIZE)
{
my_s = new type[max_size];
if (my_s == NULL)
{
cerr << "动态存储分配失败!" << endl;
exit (1);
}
}
Class_Linkstack( int size) :top(-1), max_size(size)
{
my_s = new type[size];
if (my_s == NULL)
{
cerr << "动态存储分配失败!" << endl;
exit (1);
}
}
~Class_Linkstack() { delete [] my_s; }
bool Empty_Linkstack();
void Push_Linkstack(type tp);
void Pop_Linkstack();
type Top_Linkstack();
int Size_Linkstack();
void Print_Linkstack();
};
template < class type>
void Class_Linkstack<type>::Print_Linkstack()
{
if (top == -1)
cout << "空栈" << endl;
else
{
for ( int i = 0; i < top+1; i++)
cout << my_s[i] << '\t' ;
}
}
template < class type>
bool Class_Linkstack<type>::Empty_Linkstack()
{
if (top == -1)
return true ;
else
{
return false ;
}
}
template < class type>
void Class_Linkstack<type>::Push_Linkstack(type tp)
{
if (top + 1 < max_size)
my_s[++top] = tp;
else
{
cout << "栈已满" << endl;
exit (1);
}
}
template < class type>
void Class_Linkstack<type>::Pop_Linkstack()
{
if (top == -1)
{
cout << "为空栈" << endl;
exit (1);
}
else
{
my_s[top--] = 0;
}
}
template < class type>
type Class_Linkstack<type>::Top_Linkstack()
{
if (top != -1)
return my_s[top];
else
{
cout << "为空栈" << endl;
exit (1);
}
}
template < class type>
int Class_Linkstack<type>::Size_Linkstack()
{
return top + 1;
}
|
测试代码
1
2
3
4
5
6
7
8
9
10
|
#include "Class_Linkstack.h"
int main()
{
Class_Linkstack< int > sk1(5);
for ( int i = 0; i < 5;i++ )
sk1.Push_Linkstack(i * 2 + 1);
sk1.Print_Linkstack();
system ( "pause" );
return 0;
}
|
补充(通过单链表实现)
上面是通过数组来实现,与数组相比,链表实现更灵活,更容易增删元素。
单链表实现的核心思想是不断更新栈顶指针,来实现出栈压栈,每一个节点是一个结构体,包含一个value和一个next指针指向下一个元素,初始化时将栈顶指针置为NULL。
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
|
#pragma once
using namespace std;
template < class type>
struct listnode
{
type value;
listnode* next;
listnode(type v,listnode* p):value(v),next(p){ }
};
template < class type>
class List_stack
{
listnode<type>* top;
int size = 0;
public :
List_stack();
void Push(type &tp);
void Pop();
bool Empty();
int Size();
void Print();
~List_stack()
{
while (top)
{
listnode<type> * p = top;
top = top->next;
delete p;
}
}
};
template < class type>
bool List_stack<type>::Empty()
{
if (top == NULL)
return true ;
else
{
return false ;
}
}
template < class type>
List_stack<type>::List_stack()
{
top = NULL;
size = 0;
}
template < class type>
void List_stack<type>::Push(type &tp)
{
listnode<type> *tmp= new listnode<type>(tp,top);
top = tmp;
size++;
}
template < class type>
void List_stack<type>::Pop()
{
if (top == NULL)
{
cout << "为空栈" << endl;
}
else
{
top = top->next;
size--;
}
}
template < class type>
int List_stack<type>::Size()
{
return size;
}
template < class type>
void List_stack<type>::Print()
{
listnode<type>* tmp = top;
while (tmp != NULL)
{
cout << tmp->value << '\t' ;
tmp = tmp->next;
}
}
|
简单测试:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int main()
{
List_stack< int > ls;
for ( int i = 0; i < 5; i++)
ls.Push(i);
ls.Print();
ls.Pop();
ls.Pop();
cout << endl;
ls.Print();
cout << endl;
cout << ls.Size();
system ( "pause" );
return 0;
}
|
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:https://blog.csdn.net/weixin_37944830/article/details/79455925