什么是栈
栈是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。一句话描述栈的特性就是先进后出
如何实现栈
实现一个栈我们一般有两种方法：
顺序结构
顾名思义，就是使用数组来实现栈的特性。数组实现简单，我们只需要预先定义好数组的大小、在数组的末尾进行元素的入栈操作或者出栈操作即可。时间复杂度为 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，学习更多的知识！我们下期再见！
