链式栈的基础知识-尧图网页设计

一, 链式栈结构typedef struct LSNode{int data;struct LSNode* next;}LSNode,*PLStack;栈的操作只有两个入栈 push、出栈 pop都只在栈顶操作。如果栈顶放在链表头部入栈新建结点插在链表最前面头插\(O(1)\)出栈删除链表第一个结点 \(O(1)\)头插 / 头删只需要修改指针不需要遍历链表常数时间。❌ 如果栈顶放在链表尾部单链表只能顺着 next 向后遍历要删除尾结点必须从头遍历找到尾结点的前驱入栈虽然可以保留尾指针做到 O (1)但出栈操作是\(O(n)\)效率很差违背栈设计初衷。//初始化void InitStack(PLStack ps){assert(ps ! NULL);if (ps NULL)return;ps-next NULL;}//往栈中入数据(入栈操作)bool Push(PLStack ps, int val){assert(ps ! NULL);if (ps NULL)return false;LSNode* p (LSNode*)malloc(sizeof(LSNode));assert(p ! NULL);p-data val;p-next ps-next;ps-next p;return true;}//获取栈顶元素的值,但是不删除bool GetTop(PLStack ps, int* rtval ){assert(ps ! NULL);if (ps NULL)return false;if (IsEmpty(ps))return false;*rtvalps-next-data;return true;}//获取栈顶元素的值,但是删除bool Pop(PLStack ps, int* rtval){assert(ps ! NULL);if (ps NULL)return false;if (IsEmpty(ps))return false;LSNode* p ps-next;*rtval p-data;ps-next p-next;free(p);return true;}//判空bool IsEmpty(PLStack ps){return ps-next NULL;}//获取栈中有效元素的个数int GetLength(PLStack ps){assert(ps ! NULL);if (ps NULL)return -1;int count 0;for (LSNode* p ps-next; p ! NULL; p p-next){count;}return count;}//清空所有的数据void Clear(PLStack ps){Destroy(ps);}//销毁void Destroy(PLStack ps){//总是删除第一个数据节点LSNode* p;while (ps-next ! NULL){p ps-next;ps-next p-next;free(p);}}

资讯详情

链式栈的基础知识