数据结构之栈

什么是栈

栈是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。一句话描述栈的特性就是先进后出

如何实现栈

实现一个栈我们一般有两种方法：

顺序结构

顾名思义，就是使用数组来实现栈的特性。数组实现简单，我们只需要预先定义好数组的大小、在数组的末尾进行元素的入栈操作或者出栈操作即可。时间复杂度为 O(1)。但是我们栈的大小有限，动态调整栈大小的代价较高，且要求有连续的地址空间。

链式结构

我们可以使用链表来实现。我们在进行出栈操作和入栈操作的时间复杂度都是 O(1)。同时可以动态的管理栈的大小。

栈的实现

元素节点定义（这是展示的是链表实现的方式）：

#include <stdio.h>
#include <stdlib.h>

// 栈节点元素
typedef struct Node
{
    /* data */
    int val;

    struct Node *next;
    struct Node *prev;
} Node;

// 头节点元素
Node *head = NULL;
// 记录栈元素的数量
int size = 0;

栈的初始化操作

void init()
{
    head = NULL;
    size = 0;
}

入栈操作

void push(int val)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->val = val;
    node->prev = node->next = NULL;
    if (head == NULL)
    {
        head = node;
    }
    else
    {
        head->next = node;
        node->prev = head;
        head = node;
    }
    size++;
}

出栈操作

int pop()
{
    if (head == NULL)
    {
        return 0xFFFFFF;
    }
    Node *old = head;
    head = head->prev;
    if (head != NULL)
    {
        head->next = NULL;
    }

    old->prev = NULL;
    int val = old->val;
    size--;
    free(old);
    return val;
}

获取栈容量

int stackSize()
{
    return size;
}

启动函数

int main()
{
    init();
    push(1);
    push(2);
    printf("%d\n", pop());
    printf("%d\n", pop());
    printf("%d", stackSize());
    return 0;
}
/*
2
1
0
*/

栈的应用

栈在计算机中十分常见。比如我们写代码的递归就会使用到栈。浏览器页面的前进后退都会使用到栈。可见栈的的重要性还是比较高的，需要我们好好掌握。后续有时间会结合栈和算法写一篇文章，欢迎阅读。

数据结构中相关的代码我已上传到 gitlab:
https://gitlab.com/BitLegend/c-data-structure.git

此后的数据结构代码我都会上传在这个仓库中，需要的同学可以自己下载

以上就是本期的全部内容。在这里给大家拜个早年，祝大家新的一年牛气冲天！

感谢你能看到这里，欢迎关注我的微信公众号：BitLegend，学习更多的知识！我们下期再见！