本文参考自《大话数据结构》

栈的链式存储结构及实现

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间；而空栈，其实就是栈顶指针top=null的时候。

1.链栈的结构代码

typedef struct StackNode{ SElemType data; //数据域 struct StackNode *next; //下一个结点指针 }StackNode, *LinkStackPtr; typedef struct LinkStack{ LinkStackPtr top; //栈顶 int count; //栈元素的个数 }LinkStack;

2.进栈操作

/* 插入元素e为新的栈顶元素 */ Status Push(LinkStack *S, SElemType e){ LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode)); //申请一个新结点 s->data = e; //新结点的数据域赋值 s->next = S->top; //新结点的下一个结点指向栈顶 S->top = s; //栈顶指向新结点 S->count++; //栈元素个数+1 return OK; }

3.出栈操作

/* 若栈不为空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ Status Pop(LinkStack *S, SElemType e){ LinkStackPtr p; if(StackEmpty(*S)){ //如果栈为空，则返回ERROR return ERROR; } *e = S->top->data; //用e来返回删除的栈顶元素的值 p = S->top; //用p来暂存栈顶元素 S->top = S->top->next; //将栈顶元素指针指向原栈顶元素的下一个元素 free(p); //释放p指针所指向的内存单元 S->count--; //栈元素个数-1 return OK; }

出栈和入栈都没有任何循环操作，时间复杂度均为O(1)。

4.对比顺序栈和链栈

时间复杂度都为O(1)；空间性能：顺序栈需要事先固定一个长度，可能会存在内存空间浪费问题，但是优势是存取时定位方便；链栈要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制；如果栈在使用过程中元素变化不可预料，有时很小，有时很大，最好使用链栈；如果栈在使用过程中变化在可控范围内，建议使用顺序栈会好一些。

5.简单实现

#include <stdio.h> #include <stdbool.h> #include <stdlib.h> #define ERROR 0 #define OK 1 typedef int Status; typedef int SElemType; typedef struct StackNode{ SElemType data; struct StackNode* next = NULL; }StackNode; typedef struct LinkStack{ StackNode *top; int count; }LinkStack; /* 栈空 */ bool stackEmpty(LinkStack* S){ if(S->count == 0) return true; return false; } /* 入栈 */ Status push(LinkStack* S, SElemType e){ StackNode* newNode = (StackNode*)malloc(sizeof(StackNode)); newNode->data = e; newNode->next = S->top; S->top = newNode; S->count++; return OK; } /* 出栈 */ Status pop(LinkStack* S, SElemType* e){ if(stackEmpty(S)) return ERROR; *e = S->top->data; StackNode *p = S->top; S->top = S->top->next; S->count--; free(p); return OK; } /* 返回栈顶元素 */ bool getTop(LinkStack* S, SElemType* e){ if(S->count == 0) return false; *e = S->top->data; return OK; } /* 栈元素遍历 */ void printStack(LinkStack* S){ StackNode* p = S->top; int count = S->count; printf("元素遍历：\n"); while(count--){ printf("%d\n",p->data); p = p->next; } } int main(){ bool continueFlag = true; SElemType popNum, pushNum; LinkStack stack, *S = &stack; stack.count = 0; int functionNum; while(continueFlag){ printf("-----------菜单------------\n"); printf("-----------1.入栈----------\n"); printf("-----------2.出栈----------\n"); printf("-----------3.返回栈顶元素--\n"); printf("-----------4.栈元素遍历----\n"); printf("-----------5.栈元素个数----\n"); printf("-----------6.判断栈是否为空\n"); printf("-----------7.退出----------\n"); printf("输入功能号：\n"); scanf("%d",&functionNum); printf("-----------------------\n"); switch(functionNum){ case 1: printf("请输入要入栈的元素：\n"); scanf("%d", &pushNum); if(push(S, pushNum)) printf("入栈成功！\n"); else printf("入栈失败！\n"); break; case 2: if(pop(S, &popNum)) printf("出栈元素：%d\n",popNum); else printf("栈空！\n"); break; case 3: if(getTop(S, &popNum)) printf("栈顶元素：%d！\n",popNum); else printf("栈空！\n"); break; case 4: printStack(S); break; case 5: printf("栈元素个数：%d\n",S->count); break; case 6: if(stackEmpty(S)) printf("栈空！\n"); else printf("栈非空！\n"); break; case 7: continueFlag = false; printf("欢迎使用！\n"); break; default: printf("功能号不存在！\n"); break; } printf("-----------------------\n"); } return 0; }