栈结构之链栈详解（C语言版）

---

前言

        前面完成了栈结构中顺序栈的学习，下面开始对栈结构中的链栈进行学习。

一、链栈的定义

        栈是限定仅在表尾进行插人或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈。栈的修改是按后进先出的原则进行的，因此栈又称为后进先出的线性表，简称LIFO结构。而链栈就是使用链式结构来实现栈，链栈的空间可以是不连续分配。

二、链栈的结构

结构图

代码描述

#define ElemType int   //结点内数据类型

//链栈的结点
typedef struct StackNode
{
	ElemType data;          //数据域
	struct StackNode *next; //指针域
}StackNode;

typedef StackNode* LinkStack; //链栈指针
1
2
3
4
5
6
7
8
9
10

三、链栈的常用操作

初始化

//初始化栈
void InitStack(LinkStack *s)
{
	*s = NULL;
}
1
2
3
4
5

入栈

//入栈
void Push(LinkStack *s, ElemType x)
{
	//为栈结点分配空间
	StackNode *t = (StackNode*)malloc(sizeof(StackNode));
	assert(t != NULL);
	//将数据存入这个栈结点
	t->data = x;
	if(*s == NULL) //如果链栈里面的结点为空
	{
		*s = t;         //将链栈的指针指向这个结点
		t->next = NULL;
	}
	else  //如果栈里面已经有结点，直接进行头插
	{
		t->next = *s;//将新结点连接上之前的结点
		*s = t;//将栈指针指向最新的栈结点
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

显示栈内数据

//显示链栈内的所以元素
void Show(LinkStack *s)
{
	StackNode *p = *s;//指向栈顶
	while(p != NULL)//向下搜索栈结点，如果找到则将其数据输出
	{
		printf("%d\n",p->data);
		p = p->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11

出栈

//出栈（头删）
void Pop(LinkStack *s)
{
	StackNode *p = *s;
	//指向新的栈顶
	*s = p->next;
	//删除结点
	free(p);
	p = NULL;
}
1
2
3
4
5
6
7
8
9
10

判断栈是否为空

//判断栈是否为空
bool IsEmpty(LinkStack *s)
{
	//如果栈顶top的值等于0，则表示栈为空
	if(*s==NULL)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7
8
9

获取栈顶元素

//获取栈顶元素
bool GetTop(LinkStack *s, ElemType *v)
{
	//如果栈为空，则获取不了栈顶元素
	if(IsEmpty(s))
	{	
		printf("栈空间已空,不能取栈顶元素.\n");
		return false;
	}
	//获取栈顶元素
	*v = (*s)->data;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

获取栈内元素个数

//获取栈内元素的个数
int Length(LinkStack *s)
{
	int len=0;
	StackNode *p = *s;
	while(p!=NULL)
	{//不断下移查找元素个数
		p=p->next;  
		len++;
	}
	return len;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

清空栈

//清空栈
void Clear(LinkStack *s)
{
	while(*s!=NULL)
	{//只要栈内还有元素就出栈
		Pop(s);
	}
}
1
2
3
4
5
6
7
8

销毁栈

//销毁栈
void Destroy(LinkStack *s)
{
	//此处链栈当将栈清空，相当于销毁
	Clear(s);
}
1
2
3
4
5
6

结语

        对链栈的介绍就到这里，希望这篇文章能够给努力学习的你一些帮助。

附录

以下提供链栈的测试代码

LinkStack.h

#ifndef __LINKSTACK_H__
#define __LINKSTACK_H__

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

#define ElemType int   //结点内数据类型

//链栈的结点
typedef struct StackNode
{
	ElemType data;          //数据域
	struct StackNode *next; //指针域
}StackNode;

typedef StackNode* LinkStack; //链栈指针

void InitStack(LinkStack *s);
void Push(LinkStack *s, ElemType x);
void Show(LinkStack *s);
void Pop(LinkStack *s);
bool IsEmpty(LinkStack *s);
bool GetTop(LinkStack *s, ElemType *v);
int Length(LinkStack *s);
void Clear(LinkStack *s);
void Destroy(LinkStack *s);

#endif //__LINKSTACK_H__
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

LinkStack.cpp

#include"LinkStack.h"

//初始化栈
void InitStack(LinkStack *s)
{
	*s = NULL;
}

//入栈
void Push(LinkStack *s, ElemType x)
{
	//为栈结点分配空间
	StackNode *t = (StackNode*)malloc(sizeof(StackNode));
	assert(t != NULL);
	//将数据存入这个栈结点
	t->data = x;
	if(*s == NULL) //如果链栈里面的结点为空
	{
		*s = t;         //将链栈的指针指向这个结点
		t->next = NULL;
	}
	else  //如果栈里面已经有结点，直接进行头插
	{
		t->next = *s;//将新结点连接上之前的结点
		*s = t;//将栈指针指向最新的栈结点
	}
}
//显示链栈内的所以元素
void Show(LinkStack *s)
{
	StackNode *p = *s;//指向栈顶
	while(p != NULL)//向下搜索栈结点，如果找到则将其数据输出
	{
		printf("%d\n",p->data);
		p = p->next;
	}
	printf("\n");
}

//出栈（头删）
void Pop(LinkStack *s)
{
	StackNode *p = *s;
	//指向新的栈顶
	*s = p->next;
	//删除结点
	free(p);
	p = NULL;
}

//判断栈是否为空
bool IsEmpty(LinkStack *s)
{
	//如果栈顶top的值等于0，则表示栈为空
	if(*s==NULL)
		return true;
	else
		return false;
}

//获取栈顶元素
bool GetTop(LinkStack *s, ElemType *v)
{
	//如果栈为空，则获取不了栈顶元素
	if(IsEmpty(s))
	{	
		printf("栈空间已空,不能取栈顶元素.\n");
		return false;
	}
	//获取栈顶元素
	*v = (*s)->data;
	return true;
}

//获取栈内元素的个数
int Length(LinkStack *s)
{
	int len=0;
	StackNode *p = *s;
	while(p!=NULL)
	{//不断下移查找元素个数
		p=p->next;  
		len++;
	}
	return len;
}


//清空栈
void Clear(LinkStack *s)
{
	while(*s!=NULL)
	{//只要栈内还有元素就出栈
		Pop(s);
	}
}

//销毁栈
void Destroy(LinkStack *s)
{
	//此处链栈当将栈清空，相当于销毁
	Clear(s);
}
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

Main.cpp

#include"LinkStack.h"

void main()
{
	LinkStack st;
	InitStack(&st);
	

	for(int i=1; i<=5; ++i)
	{
		Push(&st,i);
	}

	Show(&st);
	printf("栈长度：%d\n",Length(&st));
	ElemType v;
	if(GetTop(&st, &v))
		printf("栈顶元素：%d\n\n",v);

	Pop(&st);
	Show(&st);

	Clear(&st);
	if(IsEmpty(&st))
		printf("true\n");
	else 
		printf("false\n");

	Destroy(&st);

}
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