栈的实现

一、栈

💦 栈的概念及结构

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

栈中的数据元素遵守后进先出LIFO (Last In First Out) 的原则；同时对于栈来说，一种入栈顺序对应多种出栈顺序

栈有两个经典的操作

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

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

💦 栈的实现

这里对于栈的实现我们既可以选择数组也可以和选择链表两者的效率都差不多，但是还是建议使用数组

1.初始化

函数原型

函数实现

void StackInit(ST* ps)

{

    assert(ps);

    //初始化

    ps->a = NULL;

    ps->top = 0;

    ps->capacicy = 0;

}

2.插入

函数原型

函数实现

void StackPush(ST* ps, STDatatype x)

{

    assert(ps);

    //检查空间，满了就增容

    if (ps->top == ps->capacicy)

    {

        //第一次开辟空间容量为4，其它次容量为当前容量*2

	int newcapacity = ps->capacicy == 0 ? 4 : ps->capacicy * 2;

	//第一次开辟空间，a指向空，realloc的效果同malloc

	STDatatype* tmp = realloc(ps->a, sizeof(STDatatype) * newcapacity);

	//检查realloc

	//realloc失败

	if (tmp == NULL)

	{

            printf("realloc fail\n");

            exit(-1);

	}

	//realloc成功

	ps->a = tmp;

	ps->capacicy = newcapacity;

    }

	//插入数据 

	ps->a[ps->top] = x;

	ps->top++;

}

3.判空

函数原型

函数实现

bool StackEmpty(ST* ps)

{

    assert(ps); 

    //等于0是真，否则为假

    return ps->top == 0;

}

4.删除

函数原型

函数实现

void StackPop(ST* ps)

{

    assert(ps);

    //删除的话得保证指向的空间不为空

    assert(!StackEmpty(ps));

    //删除

    --ps->top;

}

5.长度

函数原型

函数实现

int StackSize(ST* ps)

{

    assert(ps);

    //此时的top就是长度

    return ps->top;

}

6.栈顶

函数原型

函数实现

STDatatype StackTop(ST* ps)

{

    assert(ps);

    //找栈顶的话得保证指向的空间不为空

    assert(!StackEmpty(ps));

    //此时的top-1就是栈顶数据

    return ps->a[ps->top - 1];

}

7.销毁

函数原型

函数实现

void StackDestory(ST* ps)

{

    assert(ps);

    //a为真代表它指向动态开辟的空间

    if (ps->a)

    {

	free(ps->a);

    }

    ps->a = NULL;

    ps->top = 0;

    ps->capacicy = 0;

}

💦 完整代码

这里需要三个文件

1️⃣ Static.h，用于函数的声明

2️⃣ Static.c，用于函数的定义

3️⃣ Test.c，用于测试函数

🧿 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 capacicy; //容量

}ST;


//函数 

//注意链表和顺序表我们写Print，但是栈不写，因为如果栈可以Print的话，就不符合后进先出了

	//初始化

void StackInit(ST* ps);

	//插入

void StackPush(ST* ps, STDatatype x);

	//判空

bool StackEmpty(ST* ps);

	//删除

void StackPop(ST* ps);

	//长度

int StackSize(ST* ps);

	//栈顶

STDatatype StackTop(ST* ps);

	//销毁

void StackDestory(ST* ps);

🧿 Stack.c

#include"Stack.h"


void StackInit(ST* ps)

{

    assert(ps);

    //初始化

    ps->a = NULL;

    ps->top = 0;

    ps->capacicy = 0;

}

void StackPush(ST* ps, STDatatype x)

{

    assert(ps);

    //检查空间，满了就增容

    if (ps->top == ps->capacicy)

    {

	//第一次开辟空间容量为4，其它次容量为当前容量*2

	int newcapacity = ps->capacicy == 0 ? 4 : ps->capacicy * 2;

	//第一次开辟空间，a指向空，realloc的效果同malloc

	STDatatype* tmp = realloc(ps->a, sizeof(STDatatype) * newcapacity);

	//检查realloc

            //realloc失败

	if (tmp == NULL)

	{

            printf("realloc fail\n");

            exit(-1);

	}

            //realloc成功

	ps->a = tmp;

	ps->capacicy = newcapacity;

    }

	//插入数据 

	ps->a[ps->top] = x;

	ps->top++;

}

bool StackEmpty(ST* ps)

{

    assert(ps); 

    //等于0是真，否则为假

    return ps->top == 0;

}

void StackPop(ST* ps)

{

    assert(ps);

    //删除的话得保证指向的空间不为空

    assert(!StackEmpty(ps));

    //删除

    --ps->top;

}

int StackSize(ST* ps)

{

    assert(ps);

    //此时的top就是长度

    return ps->top;

}

STDatatype StackTop(ST* ps)

{

    assert(ps);

    //找栈顶的话得保证指向的空间不为空

    assert(!StackEmpty(ps));

    //此时的top-1就是栈顶数据

    return ps->a[ps->top - 1];

}

void StackDestory(ST* ps)

{

    assert(ps);

    //a为真代表它指向动态开辟的空间

    if (ps->a)

    {

        free(ps->a);

    }

    ps->a = NULL;

    ps->top = 0;

    ps->capacicy = 0;

}

🧿 Test.c

#include"Stack.h"


int main()

{

    ST st;

    //初始化

    StackInit(&st);

    //插入+删除

    StackPush(&st, 1);

    StackPush(&st, 2);

    StackPush(&st, 3);

    StackPush(&st, 4);

    StackPush(&st, 5);

    StackPop(&st);

    StackPop(&st);

    //长度

    StackSize(&st);

    //栈顶

    StackTop(&st);

    //销毁

    StackDestory(&st);

    return 0;

}