栈的概念以及实现

目录:

一、栈的概念

二、栈的实现

1.栈的初始化

2.栈的销毁

3.入栈

4.出栈

5.获取栈顶数据

6.判断栈是否为空

7.获取栈的个数

三、代码

一、栈的概念

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

进行数据插入和删除操作的一端

称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

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

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

例：比如手枪弹夹，先压进去的子弹往往是后发射出去，也就是遵循后进先出的原则。

typedef int stacktype;
typedef struct Stack
{stacktype* a;//动态数组int top;    //个数int capacity;//空间
}ST;

二、栈的实现

1.栈的初始化

一开始，数组为空，并且top和capacity都为0，这里的top有两种初始化方法，如果我们想让他指向栈中的最后一个数据，那么它的值就不能是数组的起始下标0，而应该给一个无关的数，比如-1；第二种就是top表示栈顶数据的下一个位置，那我们就可以给他赋值0，这里我们使用第二种方法：

void STInit(ST* pst)//初始化
{assert(pst);pst->a = NULL;pst->top = 0;//基于size指向的是栈顶数据的下一个位置pst->capacity = 0;
}

2.栈的销毁

删除也是很简单，原理和顺序表都差不多：

void STDestroy(ST* pst)//销毁
{assert(pst);free(pst->a);//free掉pst->a = NULL;//置为空，防止变成野指针pst->top = 0;pst->capacity = 0;
}

3.入栈

首先要明白，栈是栈顶入，栈顶出，所以所有数据都从栈顶进入，也就是top的位置，随后top++就可以，扩容和顺序表一样，详情可以参考：https://blog.csdn.net/xpcxpt/article/details/147466492?spm=1001.2014.3001.5501

总体代码如下：

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

4.出栈

出栈也就是删除一个栈顶的数据，那只需要让top--就可以了：

void STPop(ST* pst)//删除 出栈
{assert(pst);assert(pst->top > 0);//top是非负数pst->top--;//删除一个
}

5.获取栈顶数据

top的位置的栈顶数据的下一个位置，所以要想获取栈顶元素，就要获取top-1位置的元素:

stacktype STTop(ST* pst)//获取栈顶数据
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}

6.判断栈是否为空

直接判断栈中数据数量top是否为空，这里可以使用bool类型，不为空返回true，为空返回fulse：
 

bool STEmpty(ST* pst)//判断栈是否为空
{assert(pst);return pst->top == 0;
}

7.获取栈的个数

这里也是非常简单，就是获取top的大小，几行代码就搞定了：

int STSize(ST* pst)//判断栈的数据个数
{assert(pst);return pst->top;//从0开始的，所以返回size的大小-1,也就是下表从0-top-1，一共top个
}

三、代码

总体代码如下:

test.c:

#include "stack.h"int main()
{ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);//printf("%d ", STTop(&s));STPush(&s, 3);STPush(&s, 4);while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}STDestroy(&s);
}

stack.h:
 

#pragma once#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int stacktype;
typedef struct Stack
{stacktype* a;//动态数组int top;    //个数int capacity;//空间
}ST;void STInit(ST* pst);//初始化
void STDestroy(ST* pst);//销毁
void STPush(ST* pst, stacktype x);//插入 入栈
void STPop(ST* pst);//删除 出栈
stacktype STTop(ST* pst);//获取栈顶数据
bool STEmpty(ST* pst);//判断栈是否为空
int STSize(ST* pst);//判断栈的数据个数

stack.c:
 

#include "stack.h"void STInit(ST* pst)//初始化
{assert(pst);pst->a = NULL;pst->top = 0;//基于size指向的是栈顶数据的下一个位置pst->capacity = 0;
}void STDestroy(ST* pst)//销毁
{assert(pst);free(pst->a);//free掉pst->a = NULL;//置为空，防止变成野指针pst->top = 0;pst->capacity = 0;
}void STPush(ST* pst, stacktype x)//插入 入栈
{assert(pst);//扩容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;stacktype* tmp = (stacktype*)realloc(pst->a, newcapacity * sizeof(stacktype));if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}
void STPop(ST* pst)//删除 出栈
{assert(pst);assert(pst->top > 0);//top是非负数pst->top--;//删除一个
}
stacktype 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;//从0开始的，所以返回size的大小-1,也就是下表从0-top-1，一共top个
}