【数据结构】千字深入浅出讲解栈（附原码 | 超详解）

🚀write in front🚀
📝个人主页：认真写博客的夏目浅石.
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
📣系列专栏：C语言实现数据结构
💬总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🖊
✉️如果无聊的话，就来逛逛我的博客栈吧stack-frame.cn

---

前言

这几天看了数据结构的栈这一节，真的收获很大，第一次看没有动手敲代码就是感觉学了和没学一样，今天也是从新又看了一遍，并且边学边敲代码，终于算是非常理解栈这个东西了，今天就把我所学到的知识给大家分享一下。

---

一、栈的概念

栈 是一个特殊的 线性表

栈只允许在固定的一段进行插入和删除元素的操作。进行数据插入和删除操作的一端称为栈顶，不进行操作的一端称为栈底

栈中的元素遵守 后进先出 (LIFO - Last In First Out) 的原则。也就是先进的后出，后进的先出

栈对于数据的管理主要有两种操作：

1. 压栈：栈的插入操作叫做进栈 / 压栈 / 入栈，从栈顶进行压栈。
2. 出栈：栈的删除操作叫做 出栈，从栈顶进行出栈。
   

二、栈的结构

栈一般可以使用 数组或链表 实现。让我们分析一下使用这两种方法实现，栈的结构分别是什么样的。

在分析之前，我们要明确的一点是，栈只对 栈顶 的元素进行操作。

那么对于 顺序栈 和 链式栈 ，那个更加好呢？那必定是 顺序栈，因为使用顺序栈的 尾插尾删非常方便， 且 cpu缓存利用率也更高。而且对于顺序栈实现起来相对简单，所以我们接下来就实现 顺序栈 。

三、栈的实现

3.1 结构设计

我们既然是实现 顺序栈，那么它的结构肯定就和 顺序表 差不多：

typedef struct Stack
{STDatatype* a; // 指向动态开辟的数组int capacity; // 栈的容量int top; // 标识 栈顶的下一个位置的下标 或 栈顶的下标
}ST;

这里的 top 我们需要好好理解一下。当top的初始值不同时，top可以表示 栈顶的下一个位置的下标 或 栈顶下标。

1. 当 top = 0，top 表示栈顶的下一个位置的下标：

2. 当 top = -1，top 表示栈顶的下标：

top 初始值为 -1，那么需要先 ++top，再压栈。否则会越界。当 最后一次压栈时，为先 ++top 再压栈，top 最后的位置就是栈顶的下标处。

3.2 接口总览

void StackInit(ST* ps); // 初始化
void StackDestroy(ST* ps); // 销毁
void StackPush(ST* ps, STDatatype x); // 压栈
void StackPop(ST* ps); // 出栈
STDatatype StackTop(ST* ps); // 取栈顶元素
bool StackEmpty(ST* ps); // 判空
int StackSize(ST* ps); // 计算栈的大小

3.3 初始化

我们实现的是顺序栈，那么就和顺序表一样，需要创建结构体变量，传结构体的地址，进行初始化。

在初始化的时候就给栈开上四个单位的空间，并且将起始容量设定为4。

注意了我们这里设定的 top = 0，那么表示 top 为栈顶的下一个位置的下标。

void StackInit(ST* ps)
{// 结构体一定不为空，所以需要断言assert(ps);ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);if (ps->a == NULL){perror("malloc fail");exit(-1);}ps->capacity = 4;ps->top = 0;
}

3.4 销毁

对于栈的销毁，那么我们就只需要释放动态开辟的空间，将指针置空。并将 capacity 和 top 两个变量置 0即可。

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

3.5 判断栈是否为空

我们起初设定 top = 0，所以判断栈是否为空，那么只需要看 top 是否为0就可以了。如果为0，返回真 ；不为0，返回假。

bool StackEmpty(ST* ps)
{assert(ps);// 如果 ps->top == 0，返回真// 如果 ps->top !=0，返回假return ps->top == 0;
}

3.6 入栈

void StackPush(ST* ps, STDatatype x)
{assert(ps);// 检查容量if (ps->top == ps->capacity){STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity *= 2;}// 插入元素// top 为栈顶的下一个元素// 先插入再 ++ ps->a[ps->top] = x;ps->top++;
}

3.7 出栈

void StackPop(ST* ps)
{assert(ps);// 如果栈空，则不能删除assert(!StackEmpty(ps));ps->top--;
}

3.8 取栈顶元素

STDatatype StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}

3.9 计算栈的大小

int StackSize(ST* ps)
{assert(ps);return ps->top;
}

四、 完整代码

Stack.h

#pragma once#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int STDatatype;typedef struct Stack
{STDatatype* a;int capacity;int top;   // 初始为0，表示栈顶位置下一个位置下标// 初始为-1，表示栈顶位置的下标
}ST;void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDatatype x);
void StackPop(ST* ps);
STDatatype StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1 #include "Stack.h"// top 为栈顶 初识值为 -1void StackInit(ST* ps)
{// 结构体一定不为空assert(ps);ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);if (ps->a == NULL){perror("malloc fail");exit(-1);}ps->capacity = 4;ps->top = -1;
}void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}void StackPush(ST* ps, STDatatype x)
{assert(ps);// 检查容量// 此时 top 一开始为 -1，不能表示栈中元素的数目// top + 1 才是正确的if (ps->top + 1 == ps->capacity){STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity *= 2;}// 插入元素// top 为栈顶元素// 先 ++ 再插入ps->a[++ps->top] = x;
}void StackPop(ST* ps)
{assert(ps);// 如果栈空，则不能删除assert(!StackEmpty(ps));ps->top--;
}STDatatype StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top];
}bool StackEmpty(ST* ps)
{assert(ps);return ps->top == -1;
}int StackSize(ST* ps)
{assert(ps);return ps->top + 1;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1 #include "Stack.h"void TestST1()
{ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);StackPush(&st, 5);StackPop(&st);StackPop(&st);printf("%d\n", StackTop(&st));
}int main()
{TestST1();
}

总结

  今天学习了栈的知识，初次写数据结构的知识，给我的感觉就是，学三遍不如手敲代码一遍来的实在，所以数据结构的学习我将多画图，多敲代码来学习，希望大家吸取经验和我一起学习数据结构，为后面打比赛刷题打下坚实基础。

  我是夏目浅石，希望和你一起学习进步，刷题无数！！！希望各位大佬能一键三连支持一下博主，hhhh~我们下期见喽

如果无聊的话，就来逛逛我的博客栈吧stack-frame.cn

✨$原创不易，还希望各位大佬支持一下$

👍 $点赞，你的认可是我创作的动力！$

⭐️ $收藏，你的青睐是我努力的方向！$

✏️ $评论，你的意见是我进步的财富！$