数据结构10分钟入门–栈

一、栈是什么

栈是一种后进先出（Last In First Out, LIFO）的线性表，限定只能在表尾进行插入或者删除操作，表尾又称为栈顶。栈可分为顺序栈（使用数组实现）和链式栈（使用链表实现）两种类型，本章主要介绍链式栈。

栈常用的操作有入栈和出栈两种，在表尾插入元素称为入栈（push），在表尾删除元素称为出栈（pop）

二、栈的结构体定义

typedef struct node {
    int data;     /**数据域*/
    struct stack_node *next;    /**指向下一个节点*/
}stack_node;

可以看到，栈的结构体定义与上篇文章单链表完全一致，因为链式栈就是以链表为基础进行实现的。

三、创建栈

stack_node *stack_init()
{
    /**从内存动态申请*/
    stack_node *head = (stack_node *)malloc(sizeof(stack_node));
    if(head == NULL) {
        return NULL;
    }

    /**初始化头指针 #2*/
    head->data = 0; /**头指针的数据域用于存储栈的大小*/
    head->next = NULL;
   
    return head;
}

1、创建栈的函数与创建单链表一致，动态从内存申请空间，作为栈的头指针，然后对malloc的返回值进行判断；

2、特别注意的是我们将头指针的数据域data用来存储栈的元素总数；

三、入栈

int stack_push(stack_node *head, int data)
{
    /**动态申请一个节点*/
    stack_node *node = (stack_node *)malloc(sizeof(stack_node));
    if (node == NULL) {
        return -1;
    }

    /**插入节点 */
    node->data = data;
    node->next = head->next;

    head->next = node;

    /**栈大小加1*/
    head->data++;
    return 0;
}

入栈操作就是单链表插入节点的特殊形式，即只能将节点插入在表尾，所以入栈函数的传参没有节点插入位置（固定插入在第一个节点），省略了遍历链表寻找插入位置节点的操作。

四、出栈

int stack_pop(stack_node *head)
{
    /* 临时保存栈顶元素 */
    stack_node *p = head->next;
    if (p == NULL) {
        return -1;
    }

    int data = p->data;
    /**跳过被删除的节点，释放内存，完成出栈*/
    head->next = head->next->next;
    free(p);

    /**栈大小减1*/
    head->data++--;
    return data;
}

出栈操作同样为单链表删除节点的特殊形式，即只能将表尾的第一个节点删除，最后返回被删除节点的值，即为弹出的的意思。

五、释放栈

int stack_release(stack_node *head)
{
    stack_node *current, *next;
    int size = head->data;
    if (size <= 0 ) {
        return -1;
    }

    current = head->next;
    while (size--)
    {
        next = current->next;
        free(current);
        current = next;
    }

    /**释放头指针*/
    head->data = 0;
    head->next =NULL;
    free(head);
    return 0;
}

六、测试

目录结构
./
├── build               //编译目录
├── CMakeLists.txt      //cmake 配置文件
├── stack.c             //源码
├── stack.h
└── test.c              //测试文件

工程采用cmake构建，文件均经过测试，编译步骤如下：

1、mkdir build && cd build

2、cmake ../ && make

3、./stack_test

源码地址在公众号同标题文章底部，公众号：Linux杂货铺

系列文章

[数据结构10分钟入门] 面向初学者从零实现 — 单链表