常用的栈，你会自己实现吗

本来来自 微信公众号 ：技术乱舞

原文链接

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会了，面向对象的语言迎刃而解。对于搞嵌入式的来说，基础中的基础，如果搞应用，手撕链表和栈应该是必会的。

以上代码已测试，如有错误欢迎指正。

添加「微信 」，一起交流！

欢迎关注 #公众号：技术乱舞 一起交流

灵魂碰撞

   
大连 位置
3 点赞
0 关注
0 收藏
作者勋章


2 感谢 


5 回帖 
885