一文了解栈

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。在数据结构中，栈是比较简单的一种结构。

---

一、栈是什么？

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

二、栈的实现思路

1.顺序表实现

代码如下（示例）：

typedef struct StackList
{STDataType* a; //指向动态开辟的空间int top; //栈顶所在下标的下一位（也可以指向栈顶）int capacity;//栈容量
}ST;

2.单链表实现

代码如下（示例）：

typedef struct StackNode
{STDataType x;//数据StackNode* next;//指针域，指向下一结点
}ST;
struct Stack
{ST* phead;//指向第一个结点ST* ptail;//指向尾结点
}

3.双向链表实现

typedef struct StackNode
{STDataType x;//数据StackNode* next;//指向下一结点StackNode* prev;//指向上一结点
}ST;
struct Stack
{ST* phead;//指向第一个结点ST* ptail;//指向尾结点
}

在这里我们推荐采用顺序表来实现对栈的操作，原因如下：

1. 栈的特性利用了顺序表尾插尾删效率高的特性，虽然有时需要扩容，但是链表创建结点也同样需要成本，而顺序表扩容频率不像链表一样如此频繁。链表频繁开辟节点也是很耗时的。
2. 我们知道CPU与主存速度上存在巨大差距，为了提高效率，CPU和主存之间还存在着高速缓存。 CPU访问缓存的速度是快于主存。每次CPU取数据时会访问缓存看看存不存在所需的数据，如果不存在才会访问主存，然后将数据所在的内存块加载到缓存中。由于顺序表空间是连续的，根据缓存的空间局部性原理，采用顺序表命中率会高于链表，所以效率高。

三、接口函数的实现

1.栈的定义

typedef int STDataType;
typedef struct Stack 
{STDataType* a;//动态开辟内存int top;//栈顶的下一位int capacity;栈的容量
}ST;

这里top定义为栈顶下一位是为了下面下表访问方便，也可以定义为指向栈顶的top可以根据个人需要决定。

2.栈的初始化

void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = 0;
}

初始化时，空间a先置空指针，capacity和top置零，这是栈没有数据，top指向0，也确实是栈顶的下一位。

3.栈的销毁

void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->capacity = pst->top = 0;
}

先对pst进行assert断言，再对开辟的空间进行释放，将指针置零，capacity和top置零即可。

4.入栈

void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->capacity == pst->top){int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;STDataType*tmp=(STDataType*)realloc(pst->a, newcapacity*sizeof(STDataType));if (tmp == NULL){perror("realloc");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}

入栈需要注意的点是判断是否容量够用，当capacity和top相等时存满，需要扩充。在扩充时需要判断原容量是不是0，这里进行一个三目操作符判断。之后就是realloc扩容，最后将相应的capacity和top修改就行。

5.出栈

void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}

出栈时应判断栈是否为空，所以这里除了判断pst的有效性，还要判断top的位置。最后让top向前移一位就进行了出栈。

6.返回栈顶元素

STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top-1];
}

判断pst有效性和栈是否为空，再将栈顶的元素返回即可。

7.判空

bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}

这里需要返回bool类型，需要加<stdbool.h>头文件。当top为零时栈为空，返回true，否则返回false。

8.返回栈中数据个数

int STSize(ST* pst)
{assert(pst);return pst->top;
}

这里因为我们的top指向栈顶数据的下一位，所以top即为数据个数。返回即可。

四、文件总览

1.头文件

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>typedef int STDataType;
typedef struct Stack 
{STDataType* a;int top;int capacity;
}ST;// 初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);// 入栈  出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);// 取栈顶数据
STDataType STTop(ST* pst);// 判空
bool STEmpty(ST* pst);
// 获取数据个数
int STSize(ST* pst);

2.功能函数

#include"Stack.h"void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = 0;
}void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->capacity = pst->top = 0;
}void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->capacity == pst->top){int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;STDataType*tmp=(STDataType*)realloc(pst->a, newcapacity*sizeof(STDataType));if (tmp == NULL){perror("realloc");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top-1];
}bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}int STSize(ST* pst)
{assert(pst);return pst->top;
}

3.测试文件

int main()
{// 入栈：1 2 3 4// 出栈：4 3 2 1  /  2 4 3 1ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);printf("%d ", STTop(&s));STPop(&s);STPush(&s, 3);STPush(&s, 4);while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}STDestroy(&s);
}

---

总结

这就是本期文章的全部内容，期待你的一键三连和评论。