数据结构——栈
🐨文章目录
- ⛺0. 前言
- 🏡1. 栈的概念及结构
- 🎈1.1 概念
- 🎈1.2 结构
- 🏫2. 接口声明
- 💒3. 接口实现
- 🎇3.1 初始化和销毁
- 🎇3.2 判空
- 🎇3.3 入栈和出栈
- 🎇3.4 获取栈顶元素
- 🎇3.5 获取有效元素个数
- 🕍4. 接口测试
⛺0. 前言
相信大部分的小伙伴,在小时候都玩过玩具枪,弹夹里面的"子弹",最先放进去,最后才打出来;最后放进去的"子弹",最先打出来。
其实在数据结构里面,也有一种这样的结构——栈,数据先进后出。
🏡1. 栈的概念及结构
🎈1.1 概念
- 栈是限定仅在尾处进行插入和删除的线性表。因此对于栈来说,尾处有特殊含义,称为栈顶,头部称为栈底,不含元素的称为空栈。
- 压栈:栈的插入操作叫做压栈 / 进栈 / 入栈,入的数据在栈顶。
- 出栈:栈的删除操作叫出栈,出的数据也在栈顶。
- 栈中元素遵守后进先出LIFO(Last In First Out),的原则。
进栈、出栈示例:
🎈1.2 结构
栈可以用顺序表或者链表的方式实现。那么哪一种实现方式会好一点呢?
- 数据结构都是在内存中管理我们的数据,当我们要对数据进行操作时,都是cpu来执行这些指令。
- 因为内存的访问速度较慢,所以cup不会去直接访问内存,数据会先存储到cpu的缓存中。如果数据在缓存中,就叫命中;如果未命中,缓存的控制器就会将一定数量的数据块从内存读取到缓存中。这些数据的地址往往是相邻的。
- 那么顺序表相比于链表,因为顺序表的内存地址是连续的,所以顺序表的缓存命中率是高于链表的,这是顺序表的一个优势。
所以我们这里用顺序表的结构是相对好一点的,本篇文章也是用顺序表结构实现栈。
🏫2. 接口声明
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#define STACK_SIZE_INIT 4
typedef int STDataType;
typedef struct Stack
{
STDataType* base;
int top; //栈顶元素下一个
int capacity; //栈容量
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType e);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//判空
bool STEmpty(ST* ps);
//获取有效元素个数
int STSize(ST* ps);
💒3. 接口实现
🎇3.1 初始化和销毁
//初始化
void STInit(ST* ps)
{
assert(ps);
ps->base = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps->base == NULL)
{
perror("malloc fail");
exit(-1);
}
ps->capacity = STACK_SIZE_INIT;
ps->top = 0;//top为0表示空栈
}
//销毁
void STDestroy(ST* ps)
{
assert(ps);
free(ps->base);
ps->base = NULL;
ps->capacity = 0;
ps->top = 0;
}
🎇3.2 判空
//判空
bool STEmpty(ST* ps)
{
return ps->top == 0;
}
tips:
虽然这里判断栈是否为空只有一条语句,但是对于我们写程序的来说,肯定是知道的,但是使用者可能不知道,top是指向栈顶元素下一个还是指向栈顶元素。所以我们封装起来,可读性会更高一点。
🎇3.3 入栈和出栈
//入栈
void STPush(ST* ps,STDataType e)
{
assert(ps);
//判断容量是否已满
if (ps->top == ps->capacity)
{
STDataType* tmp = realloc(ps->base, sizeof(STDataType) * ps->capacity * 2);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->base = tmp;
ps->capacity *= 2;
}
ps->base[ps->top] = e;
ps->top++;
}
//出栈
void STPop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
ps->top--;
}
🎇3.4 获取栈顶元素
//获取栈顶元素
STDataType STTop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
return ps->base[ps->top - 1];
}
🎇3.5 获取有效元素个数
//获取有效元素个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
🕍4. 接口测试
#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:6031)
#include"Stack.h"
void TestStack1()
{
ST s;
//初始化
STInit(&s);
//压栈
STPush(&s, 1);
STPush(&s, 2);
STPush(&s, 3);
STPush(&s, 4);
int size = STSize(&s);
while (size--)
{
//获取栈顶元素
printf("%d ", STTop(&s));
//出栈
STPop(&s);
}
//销毁
STDestroy(&s);
}
int main()
{
TestStack1();
return 0;
}