企业官网建设流程全解析

一、前言

栈是后进先出的特殊线性表，主流分为顺序栈和链式栈。这一篇讲述的是链式栈。

顺序表尾部增删无需移动元素，时间复杂度是O（1），因此顺序栈以数组尾部作为栈顶，依靠尾插、尾删完成入栈、出栈。

反观单链表，访问尾部需要遍历整条链表，效率低下；而链表头部插入、删除仅修改头指针，时间复杂度同样为O(1)。基于该特性，链式栈将链表头部作为栈顶，通过头插实现Push入栈，头删实现Pop出栈，全部基础操作均为常数时间复杂度。

二、代码实现

typedef int ELEMTYPE; //链式栈的有效定义节点 typedef struct LSNode { ELEMTYPE data;//数据域：存放栈中存储的元素 struct LSNode* next;//指针域：指向栈中下一个节点 }LSNode; //链式栈的辅助节点，直接借用有效节点的结构体设计，不再单独设计 //1.初始化 void Init_LinkStack(LSNode* pls); //2.入栈 bool Push(LSNode* pls, ELEMTYPE val); //3.出栈 bool Pop(LSNode* pls); //4.获取栈顶元素值 ELEMTYPE Top(LSNode* pls); //5.判空 bool Empty(LSNode* pls); //6.打印 void Show(LSNode* pls); //7.销毁 void Destroy(LSNode* pls);

函数：

（1）初始化

void Init_LinkStack(LSNode* pls) { assert(pls!=NULL); pls->next=NULL;//栈为空 }LSNode;

（2）入栈（相当于单链表头删）

bool Push(LSNode* pls, ELEMTYPE val) { //0 assert(pls != NULL); //1.购买新节点 LSNode* pnewnode = (LSNode*)malloc(1 * sizeof(LSNode)); if (NULL == pnewnode) exit(EXIT_FAILURE); pnewnode->data = val; pnewnode->next = NULL; //2.找到合适的插入位置（找到插在哪个节点的后面），头插比较特殊，肯定是插入辅助节点后面 LSNode* p = pls; //3.进行插入（修改两个指针域） pnewnode->next = p->next; p->next = pnewnode; return true; }

（3）出栈（相当于单链表头删）

bool Pop(LSNode* pls) { //0 assert(pls != NULL); //1.判空 if (IsEmpty(pls)) return false; //2.找到待删除节点用指针q指向（头删比较特殊，q指向第一个节点） LSNode* q = pls->next; //3.再找到待删除节点的上家，用指针p指向 LSNode* p = pls; //4.pq就位，跨越指向+释放 p->next = q->next; free(q); q = NULL; return true; }

（4）获取栈顶元素

ELEMTYPE Top(LSNode* pls) { assert(pls != NULL); if (IsEmpty(pls)) return false; return pls->next->data; }

（5）判空

bool IsEmpty(LSNode* pls) { //0 assert(pls != NULL); return pls->next == NULL; }

（6）打印

bool IsEmpty(LSNode* pls) { //0 assert(pls != NULL); return pls->next == NULL; }

（7）销毁

void Destroy(LSNode* pls) { //1. while (!IsEmpty(pls)) { Pop(pls); } // /*LSNode* p = pls; LSNode* q = pls->next; p->next = q->next; free(q); q = NULL;*/ }

main

int main() { LSNode head; Init_LinkStack(&head); Push(&head, 12); Push(&head, 23); Push(&head, 34); Show(&head); Pop(&head); Show(&head); printf("TOP=%d\n", Top(&head)); Show(&head); return 0; }