网站首页 > 博客 > 正文

c语言开发语言【数据结构】栈（C代码实现）

西瓜皮博客 2023-11-11 1 0

栈

一、栈的概念及结构二、栈的实现三、栈的代码实现（一）创建文件(二)Stack.h1. 头文件声明2. 栈的结构体类型声明

（三）Stack.c1. 栈的初始化2. 入栈/压栈3. 出栈4. Top的值5. 栈的大小6. 判断Stack是否为空7. 栈的数据打印8. 栈的销毁

四、栈的代码实现【完整代码】(一) Stack.h(二) Stack.c(三) test.c

一、栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守**后进先出LIFO（Last In First Out）**的原则。

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

二、栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

通过数组实现栈

数组实现与链表实现对比小结

顺序栈：

尾插尾删效率还是很高的通过下标访问数据缓存利用率也很高单链表入栈扩容可能会造成空间上的浪费

链表栈：

栈顶的位置在链表头 => 头插头删单链表的插入、删除数据，还得找前一节点（除非双链表，但双链表所占内存空间还是比较大的）入栈时不需要扩容

通过链表实现栈

三、栈的代码实现

（一）创建文件

Stack.h （栈的类型定义、接口函数声明、引用的头文件)Stack.c （栈接口函数的实现）test.c （主函数、测试顺序表各个接口功能）

(二)Stack.h

1. 头文件声明

#pragma once //防止头文件重复包含

//头文件

#include

#include //使用bool

2. 栈的结构体类型声明

//类型声明

typedef int STDataType; //数据类型重命名

typedef struct Stack{ //结构体类型声明

STDataType* a; //动态数组实现栈

int top; //栈顶

int capacity;

}ST;

（三）Stack.c

1. 栈的初始化

//栈的初始化

void StackInit(ST* ps) {

assert(ps);

ps->a = NULL;

ps->top = ps->capacity = 0;

}

2. 入栈/压栈

//入栈/压栈

void StackPush(ST* ps,STDataType x) {

assert(ps);

//因为只有栈顶是需要尾插尾删，所以不需要额外创建一个函数checkcapacity

if (ps->top==ps->capacity) {

//判断capacity是否为0，若为0，让capacity=4

//否则capacity=capacity*2

ps->capacity == 0?4: ps->capacity * 2; //判断用==

STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity);

//温柔检查

if (tmp == NULL) {

perror("realloc fail");

exit(-1);

}

//暴力检查

//assert(tmp); 需添加头文件

//先用tmp创建避免realloc失败返回NULL值再传给ps->a

ps->a = tmp;

}

//StackPush

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

ps->top++;

}

3. 出栈

//出栈

void StackPop(ST* ps) {

assert(ps);

assert(ps->top > 0); //要确保栈里还有东西可以删

--ps->top;

}

4. Top的值

STDataType StackTop(ST* ps) {

assert(ps);

assert(ps->top > 0);

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

}

5. 栈的大小

int StackSize(ST* ps) {

return ps->top; //一开始top=0，入栈后

}

6. 判断Stack是否为空

bool StackEmpty(ST* ps) {

assert(ps);

return ps->top == 0; //判断top是否为0，是return 1值，不是return 0值

}

7. 栈的数据打印

void StackPrint(ST* ps) {

printf("[Stack Bottom] ");

for (int i = 0; i < ps->top; i++) {

printf("%d ", ps->a[i]);

}

printf("[Stack Top] ");

printf("\n");

}

8. 栈的销毁

void StackDestroy(ST* ps) {

assert(ps);

free(ps->a); //每创建栈realloc申请了内存记得要free掉否则会出现内存泄露的问题

ps->a = NULL;

ps->top = ps->capacity = 0;

}

四、栈的代码实现【完整代码】

(一) Stack.h

#pragma once

#define _CRT_SECURE_NO_WARNINGS 1

#include

#include //使用bool

//类型声明

typedef int STDataType; //数据类型重命名

typedef struct Stack{ //结构体类型声明

STDataType* a; //动态数组实现栈

int top; //栈顶

int capacity;

}ST;

//栈的初始化

void StackInit(ST* ps);

//入栈/压栈

void StackPush(ST* ps, STDataType x);

//出栈

void StackPop(ST* ps);

//Top的值

STDataType StackTop(ST* ps);

//栈的大小

int StackSize(ST* ps);

//检测Stack是否为空

bool StackEmpty(ST* ps);

//栈的数据打印

void StackPrint(ST* ps);

//栈的销毁

void StackDestroy(ST* ps);

(二) Stack.c

#include"Stack.h"

//栈的初始化

void StackInit(ST* ps) {

assert(ps);

ps->a = NULL;

ps->top = ps->capacity = 0;

}

//入栈/压栈

void StackPush(ST* ps,STDataType x) {

assert(ps);

//因为只有栈顶是需要尾插尾删，所以不需要额外创建一个函数checkcapacity

if (ps->top==ps->capacity) {

//判断capacity是否为0，若为0，让capacity=4

//否则capacity=capacity*2

ps->capacity == 0?4: ps->capacity * 2; //判断用==

STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity);

//温柔检查

if (tmp == NULL) {

perror("realloc fail");

exit(-1);

}

//暴力检查

//assert(tmp); 需添加头文件

//先用tmp创建避免realloc失败返回NULL值再传给ps->a

ps->a = tmp;

}

//StackPush

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

ps->top++;

}

//出栈

void StackPop(ST* ps) {

assert(ps);

assert(ps->top > 0); //要确保栈里还有东西可以删

--ps->top;

}

//Top的值

STDataType StackTop(ST* ps) {

assert(ps);

assert(ps->top > 0);

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

}

//栈的大小

int StackSize(ST* ps) {

return ps->top; //一开始top=0，入栈后

}

//判断Stack是否为空

bool StackEmpty(ST* ps) {

assert(ps);

return ps->top == 0; //判断top是否为0，是return 1值，不是return 0值

}

//栈的数据打印

void StackPrint(ST* ps) {

printf("[Stack Bottom] ");

for (int i = 0; i < ps->top; i++) {

printf("%d ", ps->a[i]);

}

printf("[Stack Top] ");

printf("\n");

}

//栈的销毁

void StackDestroy(ST* ps) {

assert(ps);

free(ps->a); //每创建栈realloc申请了内存记得要free掉否则会出现内存泄露的问题

ps->a = NULL;

ps->top = ps->capacity = 0;

}

(三) test.c

#include"Stack.h"

//检测StackPush

void test1() {

ST st;

StackInit(&st);

StackPush(&st, 1);

StackPush(&st, 2);

StackPrint(&st);

StackDestroy(&st); //realloc申请了空间以后一点要记得free掉避免内存泄露的情况

}

//测试StackPop

void test2() {

ST st;

StackInit(&st);

StackPush(&st, 1);

StackPush(&st, 2);

StackPush(&st, 3);

StackPop(&st);

StackPrint(&st);

StackDestroy(&st);

}

//测试StackSize,StackEmpty

void test3() {

ST st;

StackInit(&st);

StackPush(&st, 1);

StackPush(&st, 2);

StackPush(&st, 3);

StackPrint(&st);

int Top = StackTop(&st);

printf("%d ", Top);

StackPop(&st);

int Stacksize =StackSize(&st);

printf("%d ", Stacksize);

int n=StackEmpty(&st);

printf("%d ",n);

StackDestroy(&st);

}

int main() {

//test1(); //检测StackPush的功能

//test2();//测试StackPop的功能

test3();测试StackSize的功能

return 0;

}```

参考阅读

评论可见，请评论后查看内容，谢谢！！！评论后请刷新页面。

本文由用户于 2023-11-11 发布在夸智网，如有疑问，请联系我们。
本文链接：https://www.kuazhi.com/post/712779145.html

夸智网

c语言开发语言【数据结构】栈（C代码实现）

Java 数据结构篇-实现单链表核心API

数据结构与算法之美总结（数组、链表、栈、队列、递归、排序及二分）

发表评论取消回复

夸智网

c语言 开发语言 【数据结构】栈（C代码实现）

Java 数据结构篇-实现单链表核心API

数据结构与算法之美总结（数组、链表、栈、队列、递归、排序及二分）

相关文章

发表评论取消回复

c语言开发语言【数据结构】栈（C代码实现）