常用的栈，你会自己实现吗
本来来自 微信公众号 ：技术乱舞
原文链接
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会了，面向对象的语言迎刃而解。对于搞嵌入式的来说，基础中的基础，如果搞应用，手撕链表和栈应该是必会的。
以上代码已测试，如有错误欢迎指正。
添加「微信 」，一起交流！
欢迎关注 #公众号：技术乱舞 一起交流
灵魂碰撞
啊，你这个是个链栈
不会