数据结构——6.链式栈

一、前言栈是后进先出的特殊线性表主流分为顺序栈和链式栈。这一篇讲述的是链式栈。顺序表尾部增删无需移动元素时间复杂度是O1因此顺序栈以数组尾部作为栈顶依靠尾插、尾删完成入栈、出栈。反观单链表访问尾部需要遍历整条链表效率低下而链表头部插入、删除仅修改头指针时间复杂度同样为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-nextNULL;//栈为空 }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;*/ }mainint 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; }