栈：限定只能在表尾进行插入和删除的线性表。
链栈：使用链表表示的栈。
链栈特性：
- 只能栈顶插入和删除元素。
- 无需预先分配大量存储空间。
- 后进先出（Last In First Out）的线性表，后进入的元素先出栈，剩下的元素才能出栈。
优点：
- 具有记忆功能，可用于表达式求值等操作。
- 无需预先分配大量存储空间。
缺点：
- 需要为表中的逻辑关系增加额外的存储空间。
时间复杂度
- 读取时的时间复杂度为O(1)。
- 插入、删除时的时间复杂度为O(1)。
链栈节点示意图
链栈插入元素示意图
链栈删除元素示意图
实现代码如下：
// 链栈
#include <stdio.h>
#include <malloc.h>
#include <time.h>
#define OK 1 // 执行成功
#define ERROR 0 // 执行失败
#define TRUE 1 // 返回值为真
#define FALSE 0 // 返回值为假
typedef int Status; // 函数返回结果类型
typedef int ElemType; // 元素类型
// 链栈节点
typedef struct StackNode {
ElemType data; // 元素值
struct StackNode *next; // 指向下一个节点的指针
}StackNode, *LinkStackPtr;
// 链栈结构
typedef struct {
LinkStackPtr top; // 栈顶指针
int count; // 栈中元素个数
} LinkStack;
/**
* 初始化栈
* @param S 栈
* @return 执行状态
*/
Status InitStack(LinkStack *S) {
S->top = (LinkStackPtr) malloc(sizeof(StackNode)); // 为栈顶指针分配空间
// 分配空间失败，初始化错误
if (!S->top) {
return ERROR;
}
S->top = NULL; // 栈顶指针置空
S->count = 0; // 栈中元素为0
return OK;
}
/**
* 清空栈中元素
* @param S 栈
* @return 执行状态
*/
Status ClearStack(LinkStack *S) {
LinkStackPtr p, q; // p用于指向下一个元素，q指向被删除元素
p = S->top; // p指向栈顶
// 当栈中还有元素时
while (p) {
q = p; // q指向当前元素
p = p->next; // p指向下一个元素
free(q); // 删除q元素
}
S->count = 0; // 设置栈中元素个数为0
return OK;
}
/**
* 判断栈是否为空
* @param S 栈
* @return 执行状态
*/
Status StackEmpty(LinkStack *S) {
// 栈中元素个数为0
if (S->count == 0) {
return TRUE;
} else {
return FALSE;
}
}
/**
* 获取栈中元素个数
* @param S 栈
* @return 执行状态
*/
Status StackLength(LinkStack *S) {
return S->count; // 返回栈中元素个数
}
/**
* 获取栈顶元素的值，存到元素e中
* @param S 栈
* @param e 用于存储栈顶元素的值
* @return 执行状态
*/
Status GetTop(LinkStack *S, ElemType *e) {
// 栈空元素为空，获取失败
if (S->count == 0) {
return ERROR;
}
*e = S->top->data; // 将栈顶元素的值存到元素e中
return OK;
}
/**
* 添加新元素e到栈顶
* @param S 栈
* @param e 新元素
* @return 执行状态
*/
Status Push(LinkStack *S, ElemType e) {
// 创建新节点
LinkStackPtr s = (LinkStackPtr) malloc(sizeof(StackNode));
// 节点创建失败
if (!s) {
return ERROR;
}
s->data = e; // 将新元素值赋值给新节点
s->next = S->top; // 设置新节点的下一个元素指向栈顶元素
S->top = s; // 设置栈顶指针指向新节点
S->count++; // 栈中元素个数加1
return OK;
}
/**
* 弹出栈顶元素
* @param S 栈
* @param e 弹出元素
* @return 执行状态
*/
Status Pop(LinkStack *S, ElemType *e) {
LinkStackPtr p; // 指向被删除元素的指针
// 栈中元素为空，删除失败
if (S->count == 0) {
return ERROR;
}
*e = S->top->data; // 将栈顶元素的值赋值给元素e
p = S->top; // p指向被删除节点
S->top = S->top->next; // 设置新的栈顶元素为被删除节点的下一个元素
free(p); // 删除栈顶节点
S->count--; // 栈中元素个数减1
return OK;
}
/**
* 打印单个元素的值
* @param e 元素
* @return 执行状态
*/
Status visit(ElemType e) {
printf("%d ", e);
return OK;
}
/**
* 从栈顶开始遍历栈中元素
* @param S 栈
* @return 执行状态
*/
Status StackTravel(LinkStack *S) {
LinkStackPtr p; // 用于遍历栈中元素的指针
p = S->top; // p指向栈顶
printf("[ ");
// 当栈中还有元素
while (p) {
visit(p->data); // 打印该元素的值
p = p->next; // p指向下一个节点
}
printf("]\n");
return OK;
}
int main() {
int j; // 用于遍历
LinkStack s; // 栈
ElemType e; // 元素
// 如果初始化成功
if (InitStack(&s) == OK) {
// 向栈中插入10个元素
for (j = 1; j <= 10; j++) {
Push(&s, j); // 向栈顶插入元素j
}
}
printf("栈中的元素为：");
StackTravel(&s); // 遍历栈中元素
Pop(&s, &e); // 弹出栈顶元素
printf("弹出的栈顶元素为：e = %d\n", e);
printf("弹出一个元素之后，栈是否为空：%s\n", StackEmpty(&s) == TRUE ? "是" : "否");
GetTop(&s, &e); // 获取栈顶元素的值
printf("栈顶元素的值为：e = %d\n", e);
printf("栈的长度为：%d\n", StackLength(&s)); // 获取栈的长度
ClearStack(&s); // 清空栈中元素
printf("清空栈后，栈是否为空：%s\n", StackEmpty(&s) == TRUE ? "是" : "否");
return 0;
}
运行结果
