目录
栈的概念及其结构
栈的实现
数组栈
链式栈
栈的常见接口实现
主函数Test.c
头文件&函数声明Stack.h
头文件
函数声明
函数实现Stack.c
初始化SLInit
扩容Createcapacity
压栈STPush
出栈STPop
栈顶元素STTop
判断栈是否为空STempty
栈内元素个数STSzie
数组栈空间释放STDestroy
数组栈总代码
我们已经学习过了【线性表】中的顺序表和链表。今天开始进入栈和队列。栈和队列是顺序表和链表的延续,也是一种线性表(线性表在逻辑上也是连续的)。大体结构上都很相似,所以大家学习起来也会很容易的。但是栈和队列也有自己独特的性质,学习也需要特别注意哦。
栈的概念及其结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。
栈中的数据元素遵守 后进先出 / 后进先出 LIFO(Last In First Out)的原则
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
【先进后出/后进先出】可以类比【弹夹】
栈的实现
了解了栈的概念,如何实现栈呢?
根据前面博文我们可以【数组栈】和【链式栈】
数组栈
数组栈比较简单,也是快速容易实现,首先就是【数组栈】实现。
链式栈
链式栈分为【单链表】和【双向链表】去实现栈。毋庸置疑,【双向链表实现】栈顶可以是尾巴,也可以是头,因为双向链表的头插/头删和尾插/尾删都是很方便的。
但是为了节省资源,我们用【单链表】该怎样去设计呢?
单链表实现栈:栈顶只能是单链表头(头插/头删易),栈底只能是单链表尾(头删很复杂)
栈的常见接口实现
- 断言NULL/Pop==0情况
- 改变结构体用指针
- top的指向
- 单个数据直接用,多个数据用结构体包含起来
- 数组的数据访问用数组下标即可访问
- pst和pst->a搞清楚!
- 入栈顺序是只有一种,但是出栈顺序有多种!!
主函数Test.c
#include"Stack.h"
int main()
{
ST pst;//创建结构体
STInit(&pst);//传地址是修改结构体内部
STPush(&pst, 1);
STPush(&pst, 2);
STPush(&pst, 3);
STPush(&pst, 4);
STPush(&pst, 5);
while (!STempty(&pst))
{
printf("%d ", STTop(&pst));
STPop(&pst);
}
STDestroy(&pst);
}
由于栈是其只允许在固定的一端进行插入和删除元素操作。所以栈的访问是必须先Pop弹出元素才能访问下一个元素。
while (!STempty(&pst))
{
printf("%d ", STTop(&pst));
STPop(&pst);
}
头文件&函数声明Stack.h
头文件
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
函数声明
- 创建结构体
typedef int STDatatype;
typedef struct Stack
{
STDatatype* a;
int top;
int capacity;
}ST;
- 初始化
void STInit(ST* pst);
- 释放销毁
void STDestroy(ST* pst);
- 压栈
void STPush(ST* pst, STDatatype x);
- 出栈
void STPop(ST* pst);
- 栈顶元素
STDatatype STTop(ST* pst);
- 判断栈是否为NULL
bool STempty(ST* pst);
- 栈内的元素个数
int STSize(ST* pst);
函数实现Stack.c
初始化SLInit
如果初始化 top=0:表示栈内元素的个数。作为a[top]指针指向栈顶元素的下一个。
如果初始化 top=-1:表示数组元素的下标。作为a[top]指针指向栈顶元素。
#include"Stack.h"
void STInit(ST* pst)
{
assert(pst);
pst->a = 0;
//表示top指向栈顶元素的下一个位置
pst->top = 0;
//表示top指向栈顶元素
//pst->top = -1;
pst->capacity = 0;
}
扩容Createcapacity
void Createcapacity(ST* pst)
{
//扩容
if (pst->top == pst->capacity)
{
int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
ST* tmp = (ST*)realloc(pst->a, sizeof(ST) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
}
压栈STPush
void STPush(ST* pst, STDatatype x)
{
assert(pst);
Createcapacity(pst);
pst->a[pst->top] = x;
pst->top++;
}
出栈STPop
void STPop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
栈顶元素STTop
STDatatype STTop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
return pst->a[pst->top-1];
}
判断栈是否为空STempty
bool STempty(ST* pst)
{
assert(pst);
return pst->top == 0;//为0就是true 为!=0就是为flase
}
栈内元素个数STSzie
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
数组栈空间释放STDestroy
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
数组栈总代码
//Test.c
#include"Stack.h"
int main()
{
ST pst;
STInit(&pst);
STPush(&pst, 1);
STPush(&pst, 2);
STPush(&pst, 3);
STPush(&pst, 4);
STPush(&pst, 5);
while (!STempty(&pst))
{
printf("%d ", STTop(&pst));
STPop(&pst);
}
STDestroy(&pst);
}
//Stack.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int STDatatype;
typedef struct Stack
{
STDatatype* a;
int top;
int capacity;
}ST;
void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDatatype x);
void STPop(ST* pst);
STDatatype STTop(ST* pst);
bool STempty(ST* pst);
int STSize(ST* pst);
//Stack.c
#include"Stack.h"
void STInit(ST* pst)
{
assert(pst);
pst->a = 0;
pst->top = 0;
pst->capacity = 0;
}
void Createcapacity(ST* pst)
{
//扩容
if (pst->top == pst->capacity)
{
int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
ST* tmp = (ST*)realloc(pst->a, sizeof(ST) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
}
void STPush(ST* pst, STDatatype x)
{
assert(pst);
Createcapacity(pst);
pst->a[pst->top] = x;
pst->top++;
}
void STPop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
STDatatype 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;//为0就是true 为!=0就是为flase
}
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
✔✔✔✔✔最后,感谢大家的阅读,若有错误和不足,欢迎指正!各位小伙伴乖乖敲代码哦。
代码---------→【唐棣棣 (TSQXG) - Gitee.com】
联系---------→【邮箱:2784139418@qq.com】