本文主要总结了栈的链式存储方式，包括有无头结点两种情况和相关的完整实现代码。

链栈

有头结点的完整实现代码

#include<iostream>
#include<string>

using namespace std;

/*
	链栈（有头结点）
*/

/* 链栈存储结构 */
typedef struct SNode
{
	int data;  //静态数组存放栈中元素
	struct SNode * next;
	int top;  //栈顶指针
}SNode,*SqStack;

//初始化栈(有头结点)
void InitStack(SqStack& S)
{
	S = new SNode;
	S->top = -1;
	S->next = NULL;
}

//判断栈空
bool StackEmpty(SqStack S)
{
	if (S->top == -1)
	{
		return true;
	}
	else {
		return false;
	}
}

//进栈(每次都插在头结点后面)
bool Push(SqStack& S, int e)
{
	SNode* p = new SNode;
	p->data = e;
	p->next = S->next;
	S->next = p;
	p->top = ++(S->top);

	return true;
}

//出栈
bool Pop(SqStack& S, int& e)
{
	if (S->top == -1)
	{
		return false;
	}
	e = S->next->data;
	if (!S->next->next)
	{
		S->top--;
		return true;
	}
	S->next = S->next->next;
	S->top--;
	return true;
}

//读取栈顶元素
void GetTop(SqStack S, int& e)
{
	if (S->top == -1)
	{
		return;
	}
	e = S->next->data;
}

int main()
{
	SqStack S;
	InitStack(S);
	cout << "栈是否为空：" << StackEmpty(S) << endl;
	int a = 10;
	int b;

	cout << "入栈：" << Push(S, a) << endl;
	GetTop(S, b);
	cout << "读取栈顶元素：" << b << endl;
	cout << "出栈：" << Pop(S, a) << endl;
	cout << "栈是否为空：" << StackEmpty(S) << endl;
	return 0;
}

无头结点的完整实现代码

#include<iostream>
#include<string>

using namespace std;

/*
	链栈(无头结点)
*/

/* 链栈存储结构 */
typedef struct SNode
{
	int data;  //静态数组存放栈中元素
	struct SNode* next;
	int top = 0;  //栈顶指针
}SNode, * SqStack;

//初始化栈(无头结点)
void InitStack(SqStack& S)
{
	S = NULL;
}

//判断栈空
bool StackEmpty(SqStack S)
{
	if (S == NULL)
	{
		return true;
	}
	else {
		return false;
	}
}

//进栈
bool Push(SqStack& S, int e)
{
	SNode* p = S;
	S = new SNode;
	S->data = e;
	S->next = p;
	if (!p) //如果p为NULL
	{
		S->top++;
		return true;
	}
	S->top = p->top+1;

	return true;
}

//出栈
bool Pop(SqStack& S, int& e)
{
	if (S == NULL)
	{
		return false;
	}
	e = S->data;
	SNode* p = S;
	
	S = p->next;
	
	//delete p;
	return true;
}

//读取栈顶元素
void GetTop(SqStack S, int& e)
{
	if (S == NULL)
	{
		return;
	}
	e = S->data;
}
//读取栈元素个数
int GetSize(SqStack S)
{
	if (S == NULL)
	{
		return 0;
	}
	return S->top;
}

int main()
{
	SqStack S;
	InitStack(S);
	cout << "栈是否为空：" << StackEmpty(S) << endl;
	int a = 10;
	int b;
	cout << "栈元素个数：" << GetSize(S) << endl;
	cout << "入栈：" << Push(S, a) << endl;
	cout << "栈元素个数：" << GetSize(S) << endl;
	GetTop(S, b);
	cout << "读取栈顶元素：" << b << endl;
	cout << "出栈：" << Pop(S, a) << endl;
	cout << "栈元素个数：" << GetSize(S) << endl;
	cout << "栈是否为空：" << StackEmpty(S) << endl;
	return 0;
}