门户网站排版百度网址大全 官网首页
一、个人理解
链栈相较于顺序栈不存在上溢（数据满）的情况，除非内存不足，但存储密度会低于顺序栈，因为会多存一个指针域，其他逻辑和顺序表一致。总结如下：
头指针指向栈顶。
链栈没有头节点直接就是首元节点。
基本不会出现上溢的情况。
头指针为空，表示链栈为空，没有元素。
插入删除操作都是在栈顶（首元节点）操作。
二、链栈图解
三、结构体定义
1、ElemType
（1）说明
数据域，存放自定义数据。
（2）源码
typedef struct ElemType
{char StudentNum[StudentNumLen];char StudentName[StudentNameLen];int StudentScore;
}ElemType;2、Stack
（1）说明
链栈的数据域和指针域。
（2）源码
typedef struct Stack
{ElemType Data;struct Stack* NextPointer;
}Stack;3、LinkStack
（1）说明
多加了一个StackLen是为了提升计算链栈长度的效率，因为链栈不能像顺序栈一样用栈顶指针减去栈底指针得到栈长度，而是需要遍历整个链栈得到栈长度，时间复杂度为O(n)，所以多加了一个参数StackLen，使得时间复杂度变为O(1)。
（2）源码
typedef struct LinkStack
{Stack* StackTop;StackLenType StackLen;
}LinkStack;四、函数定义
1、InitLinkStack
（1）用途
初始化链栈，头节点置为NULL，表示栈为空，后续入栈时，再申请空间。
（2）源码
Status InitLinkStack(LinkStack* LS)
{JudgeAllNullPointer(LS);LS->StackTop = NULL;LS->StackLen = 0;Log("Init LinkStack : OK\n",Info);return SuccessFlag;
}（3）参数
参数名 | 说明 |
LS | 需要初始化的LinkStack*类型链栈。 |
2、JudgeLinkStackIsEmpty
（1）用途
判断链栈是否为空，如果头指针为空，则链栈为空，反之非空。
（2）源码
Status JudgeLinkStackIsEmpty(LinkStack* LS)
{JudgeAllNullPointer(LS);if(LS->StackTop == NULL){Log("Judge LinkStack: Empty\n",Debug);return SuccessFlag;}Log("Judge LinkStack: Not Empty\n",Debug);return FailFlag;
}（3）参数
参数名 | 说明 |
LS | 需要判断是否为空的LinkStack*类型链栈。 |
3、GetLinkStackLen
（1）用途
获取链栈的长度。
（2）源码
StackLenType GetLinkStackLen(LinkStack* LS)
{JudgeAllNullPointer(LS);return LS->StackLen;
}（3）参数
参数名 | 说明 |
LS | 需要获取长度的LinkStack*类型链栈。 |
4、PushLinkStack
（1）用途
压栈，将数据放入链栈中。
（2）源码
Status PushLinkStack(LinkStack* LS, ElemType E)
{JudgeAllNullPointer(LS);Stack* NewStack = (Stack*)MyMalloc(sizeof(Stack));NewStack->Data = E;NewStack->NextPointer = LS->StackTop;LS->StackTop = NewStack;LS->StackLen++;Log("Push LinkStack : OK\n",Info);return SuccessFlag;
}（3）参数
参数名 | 说明 |
LS | 需要压栈的LinkStack*类型链栈。 |
E | 需要压栈的ElemType类型数据。 |
5、GetLinkStackTop
（1）用途
获取栈顶元素数据域，返回一个ElemType类型数据。
（2）源码
ElemType GetLinkStackTop(LinkStack* LS)
{JudgeAllNullPointer(LS);return LS->StackTop->Data;
}（3）参数
参数名 | 说明 |
LS | 需要获取栈顶元素数据域的LinkStack*类型链栈。 |
6、PopLinkStack
（1）用途
弹栈，将栈顶的数据删除。
（2）源码
Status PopLinkStack(LinkStack* LS, ElemType* E)
{JudgeAllNullPointer(LS);JudgeAllNullPointer(E);if(JudgeLinkStackIsEmpty(LS) == SuccessFlag){Log("LinkStack is Empty, Data cannot be poped\n",Warning);return FailFlag;}LS->StackLen--;*E = LS->StackTop->Data;Stack* Tmp = LS->StackTop;LS->StackTop = LS->StackTop->NextPointer;free(Tmp);Tmp = NULL;Log("Pop LinkStack : OK\n",Info);return SuccessFlag;
}（3）参数
参数名 | 说明 |
LS | 需要弹栈的LinkStack*类型链栈。 |
E | 需要弹栈的ElemType*类型数据，是一个输出参数。 |
五、虚机测试
[gbase@czg2 LinearTable_LinkStack]$ make
gcc -Wall -O3 ../Log/Log.c LinkStack.c main.c -o TestLinkStack -I ../Log/[gbase@czg2 LinearTable_LinkStack]$ ./TestLinkStack
2023-2--Info--Init LinkStack : OK
2023-2--Debug--Judge LinkStack: Empty
2023-2--Info--Push LinkStack : OK
2023-2--Info--Push LinkStack : OK
2023-2--Info--Push LinkStack : OK
2023-2--Info--Push LinkStack : OK
2023-2--Info--Push LinkStack : OK
2023-2--Info--Push LinkStack : OK
2023-2--Info--Push LinkStack : OK
2023-2--Info--Push LinkStack : OK
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Debug--ElemType Data :
StudentNum : X666
StudentName : Sun
StudentScore : 107
2023-2--Debug--LinkStack Data :
StudentNum : X666
StudentName : Sun
StudentScore : 107
+++++++++++++++
StudentNum : X666
StudentName : Sun
StudentScore : 106
+++++++++++++++
StudentNum : X666
StudentName : Sun
StudentScore : 105
+++++++++++++++
StudentNum : X666
StudentName : Sun
StudentScore : 104
+++++++++++++++
StudentNum : X666
StudentName : Sun
StudentScore : 103
+++++++++++++++
StudentNum : X666
StudentName : Sun
StudentScore : 102
+++++++++++++++
StudentNum : X666
StudentName : Sun
StudentScore : 101
+++++++++++++++
StudentNum : X666
StudentName : Sun
StudentScore : 100
+++++++++++++++
LinkStackLen : 8
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Info--Pop LinkStack : OK
2023-2--Debug--ElemType Data :
StudentNum : X666
StudentName : Sun
StudentScore : 107
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Info--Pop LinkStack : OK
2023-2--Debug--ElemType Data :
StudentNum : X666
StudentName : Sun
StudentScore : 106
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Info--Pop LinkStack : OK
2023-2--Debug--ElemType Data :
StudentNum : X666
StudentName : Sun
StudentScore : 105
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Info--Pop LinkStack : OK
2023-2--Debug--ElemType Data :
StudentNum : X666
StudentName : Sun
StudentScore : 104
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Info--Pop LinkStack : OK
2023-2--Debug--ElemType Data :
StudentNum : X666
StudentName : Sun
StudentScore : 103
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Info--Pop LinkStack : OK
2023-2--Debug--ElemType Data :
StudentNum : X666
StudentName : Sun
StudentScore : 102
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Info--Pop LinkStack : OK
2023-2--Debug--ElemType Data :
StudentNum : X666
StudentName : Sun
StudentScore : 101
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Info--Pop LinkStack : OK
2023-2--Debug--ElemType Data :
StudentNum : X666
StudentName : Sun
StudentScore : 100
2023-2--Debug--LinkStack Data :
LinkStackLen : 0