数据结构（链栈）_链栈是什么

数据结构

链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作。

栈的定义
栈（Stack）又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。人们把此端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。

链栈

一、定义链栈

Ps：用链表来实现栈

typedef int ElemType;

typedef struct Node
{
	ElemType data;
	Node *next;
}*NodePtr;

typedef struct Stack
{
	NodePtr top;
}*StackPtr;
1
2
3
4
5
6
7
8
9
10
11
12

二、链栈所实现的功能
1.链栈初始化

int Init_LinkStack(StackPtr st)        //初始化
{
	assert(st!=NULL);
	if(st == NULL)
	{
		printf("%s:%d  Init  is  error\n",__FILE__,__LINE__);
		exit(0);
	}

	st->top = NULL;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.入栈

int Push_LinkStack(StackPtr st,ElemType val)        //入栈
{
	assert(st!=NULL);
	if(st == NULL)
	{
		printf("%s:%d  Push  is  error\n",__FILE__,__LINE__);
		exit(0);
	}

	NodePtr s = Apply_Node(val);

	if(Empty_LinkStack(st))
	{
		st->top = s;
	}
	else
	{
		s->next = st->top;
		st->top = s;
	}

	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.出栈

int Pop_LinkStack(StackPtr st)         //出栈
{
	assert(st!=NULL);
	if(st == NULL)
	{
		printf("%s:%d  Pop  is  error\n",__FILE__,__LINE__);
		exit(0);
	}

	if(Empty_LinkStack(st))
	{
		return false;
	}

	NodePtr s = st->top;
	st->top = s->next;
	free(s);
	s = NULL;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.获得栈顶元素

ElemType Get_Top(StackPtr st)          //弹出栈顶
{
	assert(st!=NULL);
	if(st == NULL)
	{
		printf("%s:%d  Get_Top  is  error\n",__FILE__,__LINE__);
		exit(0);
	}

	if(Empty_LinkStack(st))
	{
		return false;
	}
	else
	{
		return st->top->data;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5.申请新空间

static NodePtr Apply_Node(ElemType val)        //申请空间
{
	NodePtr s = (NodePtr)malloc(sizeof(Node));
	assert(s!=NULL);
	if(s == NULL)  return NULL;

	s->data = val;
	s->next = NULL;
	return s;
}
1
2
3
4
5
6
7
8
9
10

6.销毁

int Destroy_LinkStack(StackPtr st)        //销毁
{
	assert(st!=NULL);
	if(st == NULL)
	{
		printf("%s:%d  Destroy  is  error\n",__FILE__,__LINE__);
		exit(0);
	}
	if(Empty_LinkStack(st))
	{
		return false;
	}
	
	while(st->top!=NULL)
	{
		Pop_LinkStack(st);
	}
	st->top = NULL;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

7.判空

int Empty_LinkStack(StackPtr st)         //判空
{
	assert(st!=NULL);
	if(st == NULL)
	{
		printf("%s:%d  IsEmpty  is  error\n",__FILE__,__LINE__);
		exit(0);
	}

	if(st->top == NULL)
	{
		return true;
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

总代码：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int ElemType;

typedef struct Node      //链表 
{
	ElemType data;
	Node *next;
}*NodePtr;

typedef struct Stack      //栈 
{
	NodePtr top;
}*StackPtr;

static NodePtr Apply_Node(ElemType val)        //申请空间
{
	NodePtr s = (NodePtr)malloc(sizeof(Node));
	assert(s!=NULL);
	if(s == NULL)  return NULL;

	s->data = val;
	s->next = NULL;
	return s;
}

int Empty_LinkStack(StackPtr st)         //判空
{
	assert(st!=NULL);
	if(st == NULL)
	{
		printf("%s:%d  IsEmpty  is  error\n",__FILE__,__LINE__);
		exit(0);
	}

	if(st->top == NULL)
	{
		return true;
	}
	return false;
}

int Init_LinkStack(StackPtr st)        //初始化
{
	assert(st!=NULL);
	if(st == NULL)
	{
		printf("%s:%d  Init  is  error\n",__FILE__,__LINE__);
		exit(0);
	}

	st->top = NULL;
	return true;
}

int Push_LinkStack(StackPtr st,ElemType val)        //入栈
{
	assert(st!=NULL);
	if(st == NULL)
	{
		printf("%s:%d  Push  is  error\n",__FILE__,__LINE__);
		exit(0);
	}

	NodePtr s = Apply_Node(val);

	if(Empty_LinkStack(st))
	{
		st->top = s;
	}
	else
	{
		s->next = st->top;
		st->top = s;
	}

	return true;
}

int Pop_LinkStack(StackPtr st)         //出栈
{
	assert(st!=NULL);
	if(st == NULL)
	{
		printf("%s:%d  Pop  is  error\n",__FILE__,__LINE__);
		exit(0);
	}

	if(Empty_LinkStack(st))
	{
		return false;
	}

	NodePtr s = st->top;
	st->top = s->next;
	free(s);
	s = NULL;
	return true;
}

ElemType Get_Top(StackPtr st)          //弹出栈顶
{
	assert(st!=NULL);
	if(st == NULL)
	{
		printf("%s:%d  Get_Top  is  error\n",__FILE__,__LINE__);
		exit(0);
	}

	if(Empty_LinkStack(st))
	{
		return false;
	}
	else
	{
		return st->top->data;
	}
}

int Destroy_LinkStack(StackPtr st)        //销毁
{
	assert(st!=NULL);
	if(st == NULL)
	{
		printf("%s:%d  Destroy  is  error\n",__FILE__,__LINE__);
		exit(0);
	}
	if(Empty_LinkStack(st))
	{
		return false;
	}
	
	while(st->top!=NULL)
	{
		Pop_LinkStack(st);
	}
	st->top = NULL;
	return true;
}

int main()
{
	//以下为测试内容---------------- 
	Stack st;
	Init_LinkStack(&st);
	for(int i=0;i<10;i++)
	{
		Push_LinkStack(&st,i);
	}
	printf("%d  ",Get_Top(&st));
	Pop_LinkStack(&st);
	printf("%d  ",Get_Top(&st));
	Pop_LinkStack(&st);
	printf("%d  ",Get_Top(&st));
	Pop_LinkStack(&st);
	printf("%d  ",Get_Top(&st));
	Pop_LinkStack(&st);
	printf("%d  ",Get_Top(&st));
	Pop_LinkStack(&st);
	Destroy_LinkStack(&st);
	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
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164