数据结构——栈

一、栈的定义

栈的概念：

栈：栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

栈遵守一个规则：先进后出，后进先出

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

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

其实栈的结构就和弹夹的结构一样，后放入的子弹先打出来（后进栈的数据先出栈），最先放入的子弹最后打（先进栈的数据后出栈）。

如下是栈的流程图：

二、栈的结构

typedef int Type;//数据类型的重命名 typedef struct ST { Type* arr; //存储空间基址 int top; //栈顶下标 int capacity; //栈的容量 }ST;

三、栈的核心功能

1、栈的初始化和销毁

1.1、栈的初始化

栈顶top初始化时可以有两种方法

1、top初始化为0，指向下一个栈顶元素的存储地址

2、top初始化为-1，指向的是当前栈顶的位置

而此方法top初始化为0，因为当top初始化为0时也可以等价为size，可以知道栈里面有多少个元素

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

1.2、栈的销毁

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

2、入栈和出栈操作

2.1、入栈

我们在入栈时需要检查空间是否够用，如果空间满了就需要进行动态扩容

我们入栈之后需要把top++，让top指向下一个入栈元素的地址

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

2.2、出栈

出栈就直接使top--，因为top指向的是下一个入栈元素的地址，所以直接top--，当下一个入栈元素入栈之后就会直接覆盖

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

3、栈中元素个数、栈顶元素和栈是否为空

3.1、栈中元素个数

上面提到过当top初始化为0，就与size具有相同的效果，记录元素的个数，所以我们直接返回top

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

3.2、获取栈顶元素

因为top是指向下一个入栈元素的地址，所以当我们需要获取当前栈顶数据时，需要对top进行-1操作，使其指向当前栈顶

int STTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->arr[ps->top - 1]; }

3.3、判断栈是否为空

如果top = 0 说明栈里面没有元素返回true，top != 0 说明栈不为空返回false

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

四、栈的实现

ST.h

#pragma once #include<stdio.h> #include<assert.h> #include<string.h> #include<stdbool.h> typedef int Type; typedef struct ST { Type* arr; //存储空间基址 int top; //栈顶下标 int capacity; //栈的容量 }ST; //栈的初始化 void STInit(ST* ps); //栈的销毁 void STdestroy(ST* ps); //入栈 void STPush(ST* ps, Type x); //出栈 void STPop(ST* ps); //获取栈中元素个数 int STSize(ST* ps); //获取栈顶元素 int STTop(ST* ps); //判断栈是否为空 bool STEmpty(ST* ps);

ST.c

#define _CRT_SECURE_NO_WARNINGS #include "ST.h" //栈的初始化 void STInit(ST* ps) { assert(ps); ps->arr = NULL; ps->top = ps->capacity = 0; } //栈的销毁 void STdestroy(ST* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->top = ps->capacity = 0; } //入栈 void STPush(ST* ps, Type x) { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ((ps->top == 0) ? 4 : 2 * ps->top); Type* tmp = (Type*)realloc(ps->arr, sizeof(Type) * newcapacity); if (tmp == NULL) { perror("realloc fail"); return; } ps->arr = tmp; ps->capacity = newcapacity; ps->arr[ps->top++] = x; } else { ps->arr[ps->top++] = x; } } //出栈 void STPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; } //获取栈中元素个数 int STSize(ST* ps) { return ps->top; } //获取栈顶元素 int STTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->arr[ps->top - 1]; } //判断栈是否为空 bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; }

STtest.c

#include"ST.h" int main() { ST s; STInit(&s); STPush(&s,1); STPush(&s, 2); STPush(&s, 3); STPush(&s, 4); STPush(&s, 5); while (STEmpty(&s) != true) { printf("%d ", STTop(&s)); STPop(&s); } return 0; }