用链表实现栈(C语言版)

前言

栈的实现可以使用链表，也可以使用数组，本文先介绍链表的实现方法。

栈介绍

栈是限制插入和删除只能在一个位置上进行的表，该位置叫做栈的顶(top)。
栈有时也叫做LIFO(last in first out)。
其模型如如下：

代码部分

头文件

#include <stdio.h>
#include <stdlib.h>
1
2

第一个头文件是为了使用printf输出元素查看，实际使用中可根据自己需求删除或增加，第二个是链表所需要用到的malloc函数，为必须的，不能少。

栈定义：（为了方便，栈中存储的元素为int型）

struct node
{
	int val;
	struct node* next;
};
1
2
3
4
5

typedef struct node* stack;  //用于表示一个栈的表头
typedef struct node* ptrtonode;  //表示一个指向栈的结点的指针
1
2

这里定义两个一模一样类型，但是名字不一样，主要原因是为了可读性。本文用链表实现栈，需要使用表头，stack表示表头，而ptrtonode（pointer to node）表示只想一个节点的指针。

定义结束之后，就可以进行栈所需要用到的操作了。
可以为检查栈是否为空，push，pop，查看top元素，listall操作。

创建一个栈

stack creat() {
	stack s = (stack)malloc(sizeof(struct node));
	s->val = 0;
	s->next = NULL;
	return s;
}
1
2
3
4
5
6

调用该函数创建一个栈格式：

stack s=creat();//创建一个栈，其表头是s
1

往栈里面插入一个元素，即push

void push(stack s,int x) {
	ptrtonode ptr = (ptrtonode)malloc(sizeof(struct node)); //此处用ptrtonode,只是为了表示他是一个节点
	ptr->val = x;
	ptr->next = s->next;
	s->next = ptr;//将表头指向该元素
}
1
2
3
4
5
6

往栈里面去除一个元素，即pop

int pop(stack s) {
	if (s->next != NULL) { //判断栈是否非空，不能对空栈执行pop操作
		ptrtonode firstcell = s->next;
		s->next = s->next->next; //表头指向下一个元素
		int x = firstcell->val;  //保存要储存的元素
		free(firstcell);  //释放该内存空间
		return x;
	}
}
1
2
3
4
5
6
7
8
9

列出栈中所有元素

void liststack(stack s) {
	while (s->next != NULL) {
		s = s->next;
		printf("%d ", s->val);
	}
	printf("\n");//为了美观
}
1
2
3
4
5
6
7

判断是否为空栈

int isempty(stack s) {  //为空返回1，非空返回0
	return s->next == NULL;
}
1
2
3

完整代码如下：

#include <stdio.h>
#include <stdlib.h>
struct node
{
	int val;
	struct node* next;
};
typedef struct node* stack;  //用于表示一个栈的表头
typedef struct node* ptrtonode;  //表示一个指向栈的结点的指针

stack creat() {
	stack s = (stack)malloc(sizeof(struct node));
	s->val = 0;
	s->next = NULL;
	return s;
}

void push(stack s, int x) {
	ptrtonode ptr = (ptrtonode)malloc(sizeof(struct node)); //此处用ptrtonode,只是为了表示他是一个节点
	ptr->val = x;
	ptr->next = s->next;
	s->next = ptr;//将表头指向该元素
}


int pop(stack s) {
	if (s->next != NULL) { //判断栈是否非空，不能对空栈执行pop操作
		ptrtonode firstcell = s->next;
		s->next = s->next->next; //表头指向下一个元素
		int x = firstcell->val;  //保存要储存的元素
		free(firstcell);  //释放该内存空间
		return x;
	}
}

void liststack(stack s) {
	while (s->next != NULL) {
		s = s->next;
		printf("%d ", s->val);
	}
	printf("\n");//为了美观
}

int isempty(stack s) {  //为空返回1，非空返回0
	return s->next == NULL;
}

int main(){
	stack s = creat();
	for (int i = 0; i < 4; i++)//依次往栈里面写入0，1，2，3
		push(s, i);
	printf("全部栈元素：");
	liststack(s);
	for (int i = 0; i < 4; i++) {
		int a=pop(s);
		printf("\n");
		printf("出栈元素为：%d\n", a);
		printf("剩余栈元素：");
		liststack(s);
	}
	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

运行结果如下：

本文到这里就结束了，有任何问题可以评论区留言告诉我，我都会一一查看回复的~