🚀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 为栈顶 初识值为 -1

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 = -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

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

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

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

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