常用的栈,你会自己实现吗
本来来自 微信公众号 :技术乱舞
原文链接
https://mp.weixin.qq.com/s/HK_W7bv3p35tSfh9IKk3NQ
大家晚上好,我是小艾同学,上期讲解了链表,本期讲解栈,相信大家或多或少的都会用到栈,可是它是怎么实现的好像并没有深入了解,那么今天带大家重温栈这个数据结构。
什么是栈
栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
栈也是数据结构中比较基础的结构,上期实现了双链表,那么今天就用链表实现栈
后进先出
后进先出就是栈的性质,就像一个桶,先放进去的在最下面,后面放进去的在上面,先出来的也是后面放进去的。
栈结构
定义栈的结构,有很多种方式,可以用数组实现一个栈,也可以用链表,本文采用链表的方式实现一个栈结构。
下面定义该栈结构:
typedef struct Node{ int elements; struct Node *next; }T_Node,*P_Node; typedef struct Stack{ int size; P_Node list_head; }T_Stack,*P_Stack;
第一个结构体为单链表结构体,是不是很熟悉的样子,第二个为栈的结构体,size表示栈里数据多少,list_head是栈的头结点,只是头结点。
创建初始化栈
首先创建一个空栈,初始化变量与指针
//初始化栈 P_Stack Create_Stack(void) { P_Stack stack = NULL; stack = malloc(sizeof(T_Stack)); stack->list_head = malloc(sizeof(T_Node)); stack->list_head->next = NULL; stack->size = 0; return stack; }
压栈操作
要很容易的实现栈,我们采用头插法,上期双链表采用尾插法,接下来用图展示压栈的操作:
下图所示的为当前栈元素
下图所示的为压栈操作:
可以把此处看为是单链表的头插法。
//用链表实现指针,采用头插法 void Stack_Push(P_Stack stack,int element){ T_Node *pTmp = malloc(sizeof(T_Node)); pTmp->elements = element; pTmp->next = stack->list_head->next; stack->list_head->next = pTmp; ++stack->size; printf("push %d success!\n",element); }
判断是否为空栈
判断是否为空栈,其实很简单,如果栈中的size为0或者list_head->next为空,就可以判断是否为空。
//判断是否为空栈,空栈返回1 int Is_Empty(P_Stack stack){ if(!stack->list_head->next) return (1); else return (0); }
获取栈顶元素
获取栈顶元素也很简单,首先判断是否为空栈,不为空,返回头指针指向的第一个元素
//栈顶元素 int Get_Top(P_Stack stack){ if(Is_Empty(stack)) { return (-1); }else{ return stack->list_head->next->elements; } //return (-1); }
出栈操作
关于出栈,首先判断是否为空栈,不为空栈,就删除链表中的第一个元素,相当于入栈操作反过来。
//出栈操作 int Stack_Pop(P_Stack stack){ if(Is_Empty(stack)) return (-1); --stack->size; P_Node pTmp = NULL; pTmp = stack->list_head->next; stack->list_head->next = pTmp->next; printf("Pop %d success \n",pTmp->elements); free(pTmp); return (0); }
遍历栈元素
该函数用来显示栈中所有元素,自顶向下遍历
//自栈顶向下遍历栈元素 int Print_Stack(P_Stack stack){ if(Is_Empty(stack)) { printf("stack NULL \n"); return (-1); } P_Node pTmp = stack->list_head->next; printf("Stack: "); while(pTmp) { if(!pTmp->next){ printf("%d\n",pTmp->elements); }else{ printf("%d->",pTmp->elements); } pTmp = pTmp->next; } return (0); }
运行结果
完整代码
#include "stdio.h" #include "stdlib.h" typedef struct Node{ int elements; struct Node *next; }T_Node,*P_Node; typedef struct Stack{ int size; P_Node list_head; }T_Stack,*P_Stack; //初始化栈 P_Stack Create_Stack(void) { P_Stack stack = NULL; stack = malloc(sizeof(T_Stack)); stack->list_head = malloc(sizeof(T_Node)); stack->list_head->next = NULL; stack->size = 0; return stack; } //用链表实现指针,采用头插法 void Stack_Push(P_Stack stack,int element){ T_Node *pTmp = malloc(sizeof(T_Node)); pTmp->elements = element; pTmp->next = stack->list_head->next; stack->list_head->next = pTmp; ++stack->size; printf("push %d success!\n",element); } //判断是否为空栈,空栈返回1 int Is_Empty(P_Stack stack){ if(!stack->list_head->next) return (1); else return (0); } //栈顶元素 int Get_Top(P_Stack stack){ if(Is_Empty(stack)) { return (-1); }else{ return stack->list_head->next->elements; } //return (-1); } //出栈操作 int Stack_Pop(P_Stack stack){ if(Is_Empty(stack)) return (-1); --stack->size; P_Node pTmp = NULL; pTmp = stack->list_head->next; stack->list_head->next = pTmp->next; printf("Pop %d success \n",pTmp->elements); free(pTmp); return (0); } //自栈顶向下遍历栈元素 int Print_Stack(P_Stack stack){ if(Is_Empty(stack)) { printf("stack NULL \n"); return (-1); } P_Node pTmp = stack->list_head->next; printf("Stack: "); while(pTmp) { if(!pTmp->next){ printf("%d\n",pTmp->elements); }else{ printf("%d->",pTmp->elements); } pTmp = pTmp->next; } return (0); } int main(int argc,char* argv[]){ P_Stack stack = Create_Stack(); Stack_Push(stack,1); Stack_Push(stack,2); Stack_Push(stack,3); Stack_Push(stack,4); Stack_Push(stack,5); printf("Top element is %d (-1 is NULL)\n",Get_Top(stack)); Print_Stack(stack); Stack_Pop(stack); Stack_Pop(stack); Print_Stack(stack); Stack_Push(stack,6); Stack_Push(stack,7); Print_Stack(stack); return 0; }
小结
闲着的日子里,上期手撕双链表,今天手撕栈,还有一个与栈相似的队列,队列实现与栈相似,不在多谈。
代码相比双链表更简单,如果是面向对象的小伙伴,常年不看C,这代码看的一定吃力,学编程一定要从C开始,C会了,面向对象的语言迎刃而解。对于搞嵌入式的来说,基础中的基础,如果搞应用,手撕链表和栈应该是必会的。
以上代码已测试,如有错误欢迎指正。
添加「微信 」,一起交流!
欢迎关注 #公众号:技术乱舞 一起交流
灵魂碰撞
啊,你这个是个链栈
不会