(C++)栈的链式存储结构(出栈、入栈、判空、遍历、销毁)(数据结构与算法)

链栈是运算受限的单链表、只能在链表头部进行操作
1.链表的头指针就是栈顶,链头为栈顶，链尾为栈底
2.栈的链式存储不需要附设头节点
3.基本不存在栈满的情况,不需要判断栈满，但要判空
4.空栈相当于头指针指向空
5.插入和删除仅在栈顶处执行
6.因为是动态分配空间，所以需要释放

#define MaxSize 100     //链栈的最大长度
typedef int SElemType;  //链栈的数据元素类型假设为int整型
//创建链栈结构
typedef struct StackNode 
{
	SElemType data;   				//结点数据域
	struct StackNode* next;			//结点指针域
}StackNode, *LinkStack;				//struct StackNode的结点形式、链栈形式别名

LinkStack stack;   //创建栈顶指针指向链栈的头结点
1
2
3
4
5
6
7
8
9
10

注意事项：

LinkStack temp1 = new StackNode;
这里 LinkStack 是一个指针类型别名，实际上是 StackNode* 的别名。
所以 temp1 是一个指针变量，指向 StackNode 类型的结点。

StackNode* temp2 = new StackNode;
这里直接声明了一个 StackNode* 类型的指针变量 temp2，指向 StackNode 类型的结点。

这两种声明方式是等价的。两者都创建了一个动态分配的 StackNode 类型的结点，并将它的地址赋给相应的指针变量。两者都可以通过 temp1->data 或 temp2->data 来访问结点的数据成员，以及 temp1->next 或 temp2->next 来访问结点的下一个结点的指针成员。

因此，在功能上，temp1 和 temp2 没有区别。不同的只是它们的声明方式，temp1 是通过别名 LinkStack 来声明的指针变量，而 temp2 是直接以 StackNode* 类型来声明的指针变量。

链栈存储结构及其实现如下：

#include
using namespace std;

#define MaxSize 100     //链栈的最大长度
typedef int SElemType;  //链栈的数据元素类型假设为int整型
//创建链栈结构
typedef struct StackNode 
{
	SElemType data;   				//结点数据域
	struct StackNode* next;			//结点指针域
}StackNode, *LinkStack;				//struct StackNode的结点形式、链栈形式别名

LinkStack stack;   //创建栈顶指针指向链栈的头结点

bool InitStack(LinkStack& stack);					//初始化链栈
bool StackEmpty(LinkStack& stack);					//链栈判空
bool PushStack(LinkStack& stack, SElemType value);	//入栈
bool PopStack(LinkStack& stack, SElemType& value);	//出栈
SElemType GetTop(LinkStack& stack);					//获取栈顶元素
bool StackPrint(LinkStack& stack);					//遍历元素
void DestoryStack(LinkStack& stack);				//销毁链栈，释放内存
int StackLength(LinkStack& stack);					//计算链栈长度/元素个数

//链栈的初始化
bool InitStack(LinkStack& stack)
{
	//构造一个空栈、栈顶指针置为空
	stack = NULL;
	return true; 
}

//判断链栈是否为空
bool StackEmpty(LinkStack& stack)
{
	if (stack == NULL)
	{
		return true; 
	}
	return false;
}

//链栈的入栈
bool PushStack(LinkStack& stack, SElemType value)   //不用判栈满
{
	StackNode* temp = new StackNode; 		//生成新结点temp
	temp->data = value; 					//将新节点数据域置为value
	temp->next = stack; 					//将新结点插入栈顶
	stack = temp; 							//更新栈顶指针
	return true;
}

//链栈的出栈：首先判空
bool PopStack(LinkStack& stack, SElemType &value)
{
	if (StackEmpty(stack))
	{
		return false; 
	}
	value = stack->data;  		//将栈顶数据域元素赋值给value
	StackNode* temp = stack;	//创建一个temp指针，并将其指向 stack 指针所指向的内存地址，以便找到出栈位置并释放。
	stack = stack->next; 		//令栈顶指针指向下一位结点，即更新栈顶指针
	delete temp;   				//释放temp所指向的空间，即出栈元素所占的内存空间,而temp本身会在函数结束后自动销毁。
	return true;  
}

//取栈顶元素
SElemType GetTop(LinkStack& stack)
{
	if (!StackEmpty(stack))  //若栈不为空
	{
		return stack->data;  //返回栈顶元素
	}
	return false; 
}
//获取栈顶长度
/*因为链表的最后一个节点的next指针是nullptr（或者说是NULL），代表链表的终止，
所以可以将链表的遍历条件设置为当前节点指针不等于nullptr，这样在遍历过程中，
当指针指向最后一个节点时，其next指针就会指向nullptr，循环条件就不再成立，
遍历结束，可以避免继续遍历下一个不合法的节点。*/
int StackLength(LinkStack& stack)
{
	int length = 0;
	StackNode* temp = stack;//创建临时指针temp与stack指向同一位置
	while (temp != nullptr)
	{
		length++;  //链栈长度即为栈中元素个数，循环一次，长度++
		temp = temp->next; //temp指针下移一位
	}
	return length; //返回链栈长度
}

//遍历栈元素
bool StackPrint(LinkStack& stack)
{
	if (stack != nullptr)
	{
		StackNode* temp = stack;//创建一个指针与stack指向同一位置
		cout << "出栈顺序：";
		while (temp != nullptr)
		{
			cout << temp->data << " ";
			temp = temp->next;  //temp向下移动一位
		}
		return true;  //遍历完毕
	}
	cout << "栈为空！" << endl;
	return false;
}

//销毁链栈，释放内存
void DestoryStack(LinkStack& stack)
{
	StackNode* temp = new StackNode;//创建一个指针
	while (stack != nullptr)
	{
		temp = stack;//使该临时指针与stack指向同一位置
		stack = temp->next;//更新栈顶指针
		delete temp;//释放临时指针
	}
	stack = nullptr;
	return;
}

//测试代码
int main()
{
	//创建链栈
	LinkStack stack;
	SElemType value;

	InitStack(stack);
	cout << "检查栈是否为空？" << (StackEmpty(stack) ? "\t是" : "\t否") << endl;

	int number = 0;//插入元素个数
	int num = 0; //插入元素值
	cout << "请输入需要插入的元素个数：";
	cin >> number;
	while ((number--) > 0) //计数
	{
		cin >> num;//输入数据
		PushStack(stack, num);//插入所输入元素
	}
	cout << "当前栈的元素个数：" << StackLength(stack) << endl; 
	cout << "获取栈顶元素：" << GetTop(stack) << endl;
	StackPrint(stack); //遍历打印栈顶元素

	cout << endl;
	PopStack(stack, value); //出栈
	cout << "出栈一次后栈顶元素为：" << GetTop(stack) << endl;
	StackPrint(stack);//遍历打印链栈元素

	DestoryStack(stack);
	cout << endl << "栈已被销毁释放" << endl;

	cout << "销毁栈后打印输出结果：" <<" ";
	StackPrint(stack);
	cout << "销毁栈后遍历栈结果：" << " ";
	StackPrint(stack);

	system("pause");
	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

结果：