一、栈的链式存储结构
如果一个栈存在频繁进栈和出栈操作，可以考虑链式结构。
栈的链式存储结构是指使用链表来实现栈这种数据结构。在链式存储结构中，栈的每个元素被封装成一个节点，节点之间通过指针相连，形成一个链表。栈顶元素对应链表的头部，栈底元素对应链表的尾部。这种结构可以动态地分配和管理存储空间，适合于需要频繁插入和删除操作的场景。
二、栈的基本操作（链表）
1、链栈的结构
typedef char SElemType;
/*栈元素结构体*/
typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackNode,*StackLinkList;
/*链栈结构体*/
typedef struct {
StackLinkList top;
SElemType count;
}StackLink;2、创建空栈
/*创建一个空栈*/
int StackInit(StackLink *S){
if(!S->top){
return ERROR;
}
S->top = (StackLinkList)malloc(sizeof(StackLinkList));
S->top = NULL;
S->count = 0;
return OK;
}3、插入栈顶元素
/*插入元素e为新的栈顶元素*/
int StackPush(StackLink *S,SElemType e){
StackLinkList p = (StackLinkList)malloc(sizeof(StackLinkList));
p->data = e;
p->next = S->top;/* 把当前的栈顶元素赋值给新结点的直接后继*/
S->top = p;/* 将新的结点s赋值给栈顶指针*/
S->count++;
return OK;
}4、 删除栈顶元素
/*若栈不空，则删除S的栈顶元素*/
/*将栈顶结点赋值给 p
使得栈顶指针下移一位,指向后一结点
释放结点p*/
int StackPop(StackLink *S){
if(StackEmpy(S))
{
return ERROR;
}
SElemType e = S->top->data;
StackLinkList q;
q = S->top;
S->top = S->top->next;
free(q);
S->count--;
return e;
}5、清空栈元素
/*清空所有的栈元素*/
void clearStack(StackLink *S){
if(!S->top){
return;
}
StackLinkList q;
while (S->count != 0)
{
q = S->top;
S->top = S->top->next;
free(q);
S->count--;
}
}6、打印所有栈元素
1）按出栈顺序打印
/*打印所有的栈元素*/
void printStack(StackLink *S,char *arr,int *size){
if(!S->top){
return;
}
int i = 0;
StackLinkList ptr;
ptr = S->top;
while (ptr != NULL)
{
// printf("%c",ptr->data);
arr[i++] = ptr->data;
ptr = ptr->next;
}
// printf("\n");
*size = i;
}2）按入栈顺序打印
核心思想是采用递归的栈底开始向栈顶打印元素。
/*打印所有的栈元素逆序*/
void printResverStack(StackLinkList S){
if(S == NULL){
return;
}
printResverStack(S->next);
printf("%c",S->data);
}
三、栈案例分析
案例：输入一串字符串，并判断该字符串是否为对称串。
代码思路：将字符串输入到栈中，并存储出栈元素到数组中，并将数组中的元素倒序输入到另一个数组中，判断两个数组元素是否一致。
代码示例：
#include "LinkStack.h"
int main()
{
StackLink Slist;
SElemType arr[50];
SElemType arr1[50];
printf("本程序判断字符串是否为对称串\n");
char ch;
int size = 0;
int j = 0;
int i = 0;
while (1)
{
StackInit(&Slist);
ch = '\0';
arr[50] = '\0';
arr1[50] = '\0';
j = 0;
printf("请输入字符串(输入q或者Q结束):");
while(1)
{
ch = getchar();
if(ch == '\n'||ch == 'q'||ch == 'Q'){
break;
}
StackPush(&Slist,ch);
}
if(ch == 'q'||ch == 'Q'){
break;
}
printStack(&Slist,arr1,&size);
for(int i = 0;i < size;i++)
{
arr[size-i-1] = arr1[i];
}
for(int i = 0;i < size;i++)
{
if(arr1[i] != arr[i])
{
j = 1;
break;
}
}
if(j == 0){
printf("是对称串\n");
}
else{
printf("不是对称串\n");
}
}
clearStack(&Slist);
printf("程序结束，再见！\n");
return 0;
}运行结果：
四、链栈的适用情况
对比一下顺序栈与链栈，它们在时间复杂度上是一样的，均为O(1)。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的 优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。
