栈模型使用顺序存储的方式就相当于在数组上进行操作,而本文介绍的则是通过链式存储来实现栈的模型,那么我们就要思考一个问题了。栈只是栈顶来做插入和删除操作,栈顶放在链表的头部还是尾部呢?
由于单链表有头指针,而栈顶指针也是必须的,那干嘛不让他俩合二为一呢,所以比较好的办法就是把栈顶放在单链表的头部(如下图)。另外都已经有了栈顶在头部了,单链表中比较常用的头结点也就失去了意义,通常对于链栈来说,是不需要头结点的。(摘自 传智播客 教师课件)
【代码实现】
以下代码需要用到线性表链式存储的头文件。
#ifndef _LINKSTACK_H #define _LINKSTACK_H # typedef void LinkStack; //创建栈 LinkStack* LinkStack_Create(); //销毁栈 void LinkStack_Destroy(LinkStack* stack); //清空栈 void LinkStack_Clear(LinkStack* stack); //压栈 int LinkStack_Push(LinkStack* stack, void *item); //出栈 void* LinkStack_Pop(LinkStack* stack); //获取栈顶元素 void* LinkStack_Top(LinkStack* stack); //获取栈的大小 int LinkStack_Size(LinkStack* stack); #endif //_LINKSTACK_H
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <string.h> #include "LinkStack.h" #include "LinkList.h" //栈节点的数据结构 typedef struct tag_linkstacknode { //链表节点 LinkListNode node; //保存数据节点的地址 void * data; }LinkStackNode; //创建栈 LinkStack* LinkStack_Create() { return LinkList_Create(); } //销毁栈 void LinkStack_Destroy(LinkStack* stack) { // 先free所有堆上的内存 LinkStack_Clear(stack); // 销毁线性表 LinkList_Destroy(stack); } //清空栈 void LinkStack_Clear(LinkStack* stack) { // 无限循环弹出所有栈上的元素,直至长度为0 while (LinkStack_Size(stack)) { // 弹出 LinkStack_Pop(stack); } // 清空线性表 LinkList_Clear(stack); } //压栈 int LinkStack_Push(LinkStack* stack, void *item) { LinkStackNode* pNew = malloc(sizeof(LinkStackNode)); if (pNew == NULL) { return -1; } //初始化 pNew->data = item; pNew->node.next = NULL; //将栈节点插入到链表的头部 int ret = LinkList_Insert(stack, (LinkListNode*)pNew, 0); if (ret != 0) { free(pNew); } return ret; } //出栈 void* LinkStack_Pop(LinkStack* stack) { void* myData = NULL; //删除链表中的第一个数据节点 LinkListNode* pDel = LinkList_Delete(stack, 0); // //释放节点内存 if (pDel != NULL) { myData = ((LinkStackNode*)pDel)->data; free(pDel); } return myData; } //获取栈顶元素 void* LinkStack_Top(LinkStack* stack) { //获取链表第一个节点 LinkListNode* pNode = LinkList_Get(stack, 0); LinkStackNode * pp = (LinkStackNode*)pNode; return pp->data; } //获取栈的大小 int LinkStack_Size(LinkStack* stack) { return LinkList_Length(stack); }
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <string.h> #include "LinkStack.h" int main() { int i; int array[10] = { 0 }; LinkStack* stack = NULL; //创建栈 stack = LinkStack_Create(); //初始化数组 for (i = 0; i < sizeof(array) / sizeof(int); i++) { array[i] = i; //压栈 LinkStack_Push(stack, (void*)&array[i]); } //打印栈的大小 printf("stack size = %d\n", LinkStack_Size(stack)); //获取栈顶元素 printf("stack top element = %d\n", *(int*)LinkStack_Top(stack)); //所有元素出栈 while (LinkStack_Size(stack) > 0) { //出栈, 并打印弹出的元素值 printf("Pop -- stack top element = %d\n", *(int*)LinkStack_Pop(stack)); } //销毁栈 LinkStack_Destroy(stack); printf("Good good study, day day up!!!\n"); system("pause"); return 0; }