【初阶数据结构篇】栈的实现（附源码）

栈

1 代码位置

[gitee](Stack/Stack · petrichor/2024-summer-c-language - 码云 - 开源中国 (gitee.com))

2 概念与结构

1.1概念

​ 栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out的原则。

​ 压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，入数据在栈顶。

​ 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

1.2结构

栈的实现⼀般可以使⽤数组或者链表实现，相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插⼊数据的代价⽐较⼩。 数组尾插时间复杂度：O(1) 链表尾插时间复杂度：O(N)

2 栈的实现

因为栈的底层是数组，所以栈的实现方法和动态顺序表大致相同，且因为栈只能在栈顶出和入数据，所以栈还要更简单一些

Stack.h

代码语言：javascript复制

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	STDataType capacity;
	STDataType top;
}ST;

//初始化和销毁
void STInit(ST*);
void STDestroy(ST*);


//栈顶---入数据,出数据
void StackPush(ST*, STDataType);
void StackPop(ST*);

//判空
bool StackEmpty(ST*);

//取栈顶元素
STDataType StackTop(ST*);


//获取栈中有效元素个数
int STSize(ST*);

---

test.c

• 用来测试我们写的函数(函数的调用)
• 这一部分就是自己写的时候用的测试用例，随便什么都行

最好是写一个方法测试一次，不然找错误的时候会很痛苦