C语言实现链栈的步骤

1
2
3
4
5
6
7
8
9
10
/********************* 链栈的常规操作 ****************************/

LinkStack 	 InitLinkStack();			// 初始化链栈
int   	 	 StackEmpty();				// 判断链栈空
int   	 	 StackLength();				// 求链栈长(链栈元素个数)
int    		 Push();					// 入栈 压栈
ElemType 	 Pop();						// 出栈 弹栈
void 	 	 DestroyStack();			// 销毁链栈

/***************************************************************/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "stdio.h"
#include "malloc.h"


#define TRUE  1
#define FALSE 0

typedef int ElemType;		// 链栈存储元素的数据类型


/*
 *	定义链栈结构体
*/
typedef struct Node{
	ElemType data;			// 栈结点数据域
	struct Node *next;		// 栈结点指针域
}*LinkStack, Node;

1
2
3
4
5
6
// 初始化链栈（带头结点的链栈）
LinkStack InitLinkStack(){
	LinkStack s = (LinkStack)malloc(sizeof(struct Node));
	s -> next = NULL;
	return s;
}

1
2
3
4
5
6
7
8
9
10
/*
 *	判断链栈是否空
 *  s 链栈
*/
int StackEmpty(LinkStack s){
	if(s == NULL){
		return FALSE;
	}
	return s -> next == NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 *	求链栈长度（栈中元素个数）
 *  s 链栈
*/
int StackLength(LinkStack s){
	LinkStack p;
	int len = 0;
	if(StackEmpty(s)){
		return FALSE;
	}
	p = s -> next;	// 带头结点的链栈要先移动一下
	while(p != NULL){
		len ++;
		p = p -> next;
	}
	return len;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
 *	入栈 压栈
 *  s 链栈
 *  data 入栈数据
*/
int Push(LinkStack s, ElemType data){
	// 分配入栈结点
	Node *new_node = (Node *)malloc(sizeof(struct Node));
	if (new_node == NULL) return FALSE;		// 结点分配失败
	
	// 跟单链表一样使用头插法
	new_node -> data = data;
	new_node -> next = s -> next;
	s -> next = new_node;
	return TRUE;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 *	出栈 弹栈
 *	s 链栈
*/
ElemType Pop(LinkStack s){
	LinkStack top;
	ElemType data;
	// 判栈空
	if(StackEmpty(s)){
		return FALSE;
	}
	top = s -> next;	// 访问栈顶结点
	data = top -> data;	// 取出栈顶元素
	s -> next = top -> next;
	free(top);			// 释放栈顶空间
	return data;
}

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
// 程序主入口
int main(int argc, char const *argv[])
{
	LinkStack s = InitLinkStack();
	printf("StackEmpty():%dn", StackEmpty(s));
	printf("StackLength():%dnn", StackLength(s));

	// 入栈元素
	ElemType datas[] = {1, 3, 5, 7, 9};

	// 动态计算入栈元素个数
	int len = sizeof(datas) / sizeof(datas[0]);	

	// for循环依次入栈
	printf("Push():");
	for(int i = 0; i < len; i++){
		printf("%dt", datas[i]);
		Push(s, datas[i]);
	}
	printf("nStackEmpty():%dn", StackEmpty(s));
	printf("StackLength():%dnn", StackLength(s));

	// 出栈 弹栈
	printf("Pop(): ");
	while(!StackEmpty(s)){
		printf("%dt", Pop(s));
	}
	printf("nStackEmpty():%dn", StackEmpty(s));
	printf("StackLength():%dnn", StackLength(s));
	return 0;
}

1
2
3
4
5
6
7
8
9
10
StackEmpty():1
StackLength():0

Push():1        3       5       7       9
StackEmpty():0
StackLength():5

Pop(): 9        7       5       3       1
StackEmpty():1
StackLength():0