顺序栈

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
#include <stdio.h>
#include <stdlib.h>
// 栈可用最大容量
#define MAXSIZE 100

// 函数结果状态代码
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
// infeasible 不可执行的
#define INFEASIBLE -1
// overflow 溢出的
#define OVEREFLOW -2

// Status 函数类型，用来表示函数结果状态代码
typedef int Status;
// ElemType 栈的数据类型
typedef char SElemType;

// 顺序栈的结构定义
typedef struct {
	// 栈顶指针
	SElemType* top;
	// 栈底指针
	SElemType* base;
	// 栈的可用最大容量
	int stacksize;
}SqStack;

// 顺序栈的初始化
Status initStack(SqStack& S) {
	// 将栈底指针指向栈的首元素
	S.base = new SElemType(MAXSIZE);
	// C语言语法
	//S.base = (SElemType*)malloc(MAXSIZE * sizeof（SElemType);
	// 分配失败，报错
	if (!S.base) {
		return OVEREFLOW;
	}
	// 让栈顶指针也指向首元素
	S.top = S.base;
	S.stacksize = MAXSIZE;
	return OK;
}

// 判断顺序栈是否为空
Status StackEmpty(SqStack& S) {
	if (S.base == S.top) {
		return OK;
	}
	else {
		return FALSE;
	}
}

// 清空顺序栈
Status StackClear(SqStack& S) {
	if(S.base)S.top = S.base;
	return OK;
}

// 求顺序栈的长度
Status StackLength(SqStack& S) {
	return S.top - S.base;
}

// 销毁顺序栈
Status DestoryStack(SqStack& S) {
	if (S.base) {
		delete S.base;
		S.stacksize = 0;
		S.base = S.top = NULL;
	}
	return OK;
}

// 顺序栈的入栈
Status Push(SqStack& S, SElemType e) {
	// 栈满
	if (S.top - S.base == S.stacksize) {
		return ERROR;
	}
	// 栈顶的值赋值为e，栈顶指针加一
	*S.top++ = e;
	return OK;
}

// 顺序栈的出栈
Status Pop(SqStack& S, SElemType& e) {
	if (StackEmpty(S)) {
		return ERROR;
	}
	e = *--S.top;
	return OK;
}

int main() {
	SqStack S;
	// 栈的初始化
	initStack(S);
	// 判断栈是否为空
	if (StackEmpty(S)) printf("顺序栈为空\n");
	printf("顺序栈的长度:%d\n", StackLength(S));
	for (int i = 0; i < 2; i++) {
		Push(S, i);
	}
	printf("顺序栈的长度:%d\n", StackLength(S));
	SElemType e;
	Pop(S, e);
	printf("顺序表出栈，元素：%d\n", e);
	StackClear(S);
	// 判断栈是否为被清空
	if (StackEmpty(S)) printf("顺序栈被清空\n");
	if (DestoryStack(S)) printf("顺序栈已被销毁");
	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
#include <stdio.h>
#include <stdlib.h>
// 栈可用最大容量
#define MAXSIZE 100

// 函数结果状态代码
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
// infeasible 不可执行的
#define INFEASIBLE -1
// overflow 溢出的
#define OVEREFLOW -2

// Status 函数类型，用来表示函数结果状态代码
typedef int Status;
// ElemType 栈的数据类型
typedef char SElemType;

typedef struct StackNode{
	SElemType data;
	struct StackNode* next;
}StackNode, * LinkStack;

// 链栈的初始化
Status initStack(LinkStack& S) {
	// 构造一个空栈，栈顶指针置为空
	S == NULL;
	return OK;
}

// 判断链栈是否为空
Status StackEmpty(LinkStack& S) {
	if (S == NULL) return TURE;
	return FALSE;
}

// 入栈
Status Push(LinkStack& S, SElemType e) {
	// 生成新结点p
	LinkStack p = new StackNode;
	// 结点p的数据域赋值为e
	p->data = e;
	// p的指针域指向S
	p->next = S;
	// 将头节点更新为新插入的结点
	S = p;
	return OK;
}

// 出栈
Status Pop(LinkStack& S, SElemType& e) {
	if (S == NULL) return ERROR;
	LinkStack p = new StackNode;
	e = S->data;
	p = S;
	S = S->next;
	free(p);
	return OK;
}

// 取栈顶元素
SElemType getTop(LinkStack& S) {
	if (S != NULL) {
		return S->data;
	}
}

int main() {
	LinkStack S;
	// 初始化链栈
	initStack(S);
	// 入栈
	for (int i = 0; i < 2; i++) {
		Push(S, i);
	}
	// 出栈
	SElemType e;
	Pop(S, e);
	printf("出栈元素：%d\n", e);
	// 取栈顶元素
	printf("栈顶元素：%d\n", getTop(S));
	return 0;
}