当前位置:首页 » 《随便一记》 » 正文

数据结构:栈-C语言实现(有图详讲带注解,适合入门学习)_柿子__

20 人参与  2022年05月31日 13:59  分类 : 《随便一记》  评论

点击全文阅读


文章目录

    • 一. 栈的概念及结构
    • 二. 栈的实现
      • 2.1 前言
      • 2.2 定义栈的结构体
      • 2.3 函数接口
        • 2.3.1 栈的初始化
        • 2.3.2 打印栈元素
        • 2.3.3 判断栈是否为空
        • 2.3.4 入栈
        • 2.3.5 出栈
        • 2.3.6 取栈顶元素
        • 2.3.7 获取栈的有效元素个数
        • 2.3.8 栈的销毁
      • 2.4 Stack.h文件代码
      • 2.5 Stack.c文件代码
      • 2.6 main.c文件代码
    • 三. 结语

  • 之前的文章
    1.数据结构:顺序表-C语言实现
    2.数据结构:链表-C语言实现

一. 栈的概念及结构

  • 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。**进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。**栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
  • 压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶
  • 出栈:栈的删除操作叫做出栈。出数据也在栈顶
    在这里插入图片描述

二. 栈的实现

2.1 前言

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。如下图所示,我们用arr数组来实现栈,top指向的是栈顶元素下一个位置下标,所以这里的top可以表示栈内有几个元素。capacity指向的是数组最后一个元素的下一个位置下标,表示当前栈最大可容纳多少个元素。像顺序表一样,数组结构的栈可分为静态和动态的,我们实现的是动态的,capacity后期通过扩容而改变它的值。本次栈的实现共创建了三个文件,分别是Stack.h,Stack.c,和main.c文件。下面我们先把栈的结构体定义和各个函数接口实现,最后再把三个文件的代码分享出来。

在这里插入图片描述

2.2 定义栈的结构体

// 重新定义数据类型名
typedef int STDataType;


// 定义栈的结构体
typedef struct Stack
{
	STDataType* arr;
	int top;
	int capacity;
};

2.3 函数接口

2.3.1 栈的初始化

// 初始化
void StackInit(Stack* stack)
{
	assert(stack);  // assert(stack != NULL)
	stack->arr = NULL;
	stack->top = 0;
	stack->capacity = 0;
}
  • assert是一个断言函数,程序运行的时候,当括号里面的结果为假时,就会停止运行并且报错。报错显示的信息包括断言语句括号的内容和断言的位置(在哪个文件,哪一行),还有一个错误框,如下图所示。断言能够快速地帮我们定位程序的错误,在实际开发中可以减少很多不必要的麻烦,所以建议大家在写代码的时候也尽量在需要的时候加上断言。
    在这里插入图片描述
    在这里插入图片描述

2.3.2 打印栈元素

// 打印
void StackPrint(Stack* stack)
{
	assert(stack);
	int i  = 0;

	// 从最后一个元素开始往前打印
	for (i = stack->top - 1; i >= 0; i--)
	{
		printf("%d\n", stack->arr[i]);
	}
	printf("\n");
}

2.3.3 判断栈是否为空

// 判空
bool StackEmpty(Stack* stack)
{
	assert(stack);
	return stack->top == 0;
}

2.3.4 入栈

// 入栈
void StackPush(Stack* stack, STDataType x)
{
	assert(stack);

	// 检查容量,看是否需要扩容
	if (stack->capacity == stack->top)
	{
		// 首次扩容就扩到4个空间,否则扩到原来的两倍
		int newcapacity = stack->capacity == 0 ? 4 : stack->capacity * 2;

		// 向内存申请空间
		STDataType* newarr = (STDataType*)realloc(stack->arr, sizeof(STDataType) * newcapacity);

		// 增容失败的处理
		assert(newarr);

		// 让arr指向新的空间地址
		stack->arr = newarr;

		// 把新的空间大小赋值给capacity
		stack->capacity = newcapacity;
	}

	//  进栈
	stack->arr[stack->top] = x;
	stack->top++;
}

在这里插入图片描述

2.3.5 出栈

// 出栈
void StackPop(Stack* stack)
{
	assert(stack);

	// 判空
	assert(!StackEmpty(stack));
	stack->top--;
}

2.3.6 取栈顶元素

// 取栈顶元素
STDataType StackTop(Stack* stack)
{
	assert(stack);
	return stack->arr[stack->top - 1];
}

2.3.7 获取栈的有效元素个数

// 获取栈的有效元素个数
int StackSize(Stack* stack)
{
	assert(stack);
	return stack->top;
}

2.3.8 栈的销毁

// 栈的销毁
void StackDestroy(Stack* stack)
{
	assert(stack);

	// 释放空间
	free(stack->arr);  // 这里arr是一次性申请的连续空间,所以可以一次性释放

	stack->arr = NULL;
	stack->capacity = 0;
	stack->top = 0;
}

2.4 Stack.h文件代码

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


// 包含头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>


// 重新定义数据类型名
typedef int STDataType;


// 定义栈的结构体
typedef struct Stack
{
	STDataType* arr;
	int top;
	int capacity;
}Stack;


// 函数的声明

// 初始化
void StackInit(Stack* stack);

// 打印
void StackPrint(Stack* stack);

// 判空
bool StackEmpty(Stack* stack);

// 入栈
void StackPush(Stack* stack, STDataType x);

// 出栈
void StackPop(Stack* stack);

// 取栈顶元素
STDataType StackTop(Stack* stack);

// 获取栈的有效元素个数
int StackSize(Stack* stack);

// 栈的销毁
void StackDestroy(Stack* stack);

2.5 Stack.c文件代码

#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"

// 初始化
void StackInit(Stack* stack)
{
	assert(stack);  // assert(stack != NULL)
	stack->arr = NULL;
	stack->top = 0;
	stack->capacity = 0;
}

// 打印
void StackPrint(Stack* stack)
{
	assert(stack);
	int i  = 0;

	// 从最后一个元素开始往前打印
	for (i = stack->top - 1; i >= 0; i--)
	{
		printf("%d\n", stack->arr[i]);
	}
	printf("\n");
}

// 判空
bool StackEmpty(Stack* stack)
{
	assert(stack);
	return stack->top == 0;
}


// 入栈
void StackPush(Stack* stack, STDataType x)
{
	assert(stack);

	// 检查容量,看是否需要扩容
	if (stack->capacity == stack->top)
	{
		// 首次扩容就扩到4个空间,否则扩到原来的两倍
		int newcapacity = stack->capacity == 0 ? 4 : stack->capacity * 2;

		// 向内存申请空间
		STDataType* newarr = (STDataType*)realloc(stack->arr, sizeof(STDataType) * newcapacity);

		// 增容失败的处理
		assert(newarr);

		// 让arr指向新的空间地址
		stack->arr = newarr;

		// 把新的空间大小赋值给capacity
		stack->capacity = newcapacity;
	}

	//  进栈
	stack->arr[stack->top] = x;
	stack->top++;
}

// 出栈
void StackPop(Stack* stack)
{
	assert(stack);

	// 判空
	assert(!StackEmpty(stack));
	stack->top--;
}


// 取栈顶元素
STDataType StackTop(Stack* stack)
{
	assert(stack);
	return stack->arr[stack->top - 1];
}

// 获取栈的有效元素个数
int StackSize(Stack* stack)
{
	assert(stack);
	return stack->top;
}

// 栈的销毁
void StackDestroy(Stack* stack)
{
	assert(stack);

	// 释放空间
	free(stack->arr);  // 这里arr是一次性申请的连续空间,所以可以一次性释放

	stack->arr = NULL;
	stack->capacity = 0;
	stack->top = 0;
}

2.6 main.c文件代码

#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"

int main()
{
	// 创建一个栈变量
	Stack stack;

	// 初始化
	StackInit(&stack);

	// 入栈
	StackPush(&stack, 1);
	StackPush(&stack, 2);
	StackPush(&stack, 3);

	// 出栈
	//StackPop(&stack);
	//StackPop(&stack);
	//StackPop(&stack);
	//StackPop(&stack);
	
	int size = StackSize(&stack);
	while (size--)
	{
		printf("%d ", StackTop(&stack));
		StackPop(&stack);
	}

	// 打印栈
	//StackPrint(&stack);

	// 销毁栈
	StackDestroy(&stack);
	return 0;
}

三. 结语

相对于前面的顺序表和链表,栈的实现上比较容易一点,看我在这篇文章画的图就知道了,比我之前顺序表和链表的文章少画了不少。很多人学到栈之后会跟内存的栈混淆在一起,其实他们的含义是不同的,就是他们是不同的两个东西,但是他们的结构是差不多的,都是遵循先进后出(Last In First Out)原则。在一些递归深度非常深的时候,我们可以利用栈的知识去模拟内存中的栈,这样可以防止栈溢出。最后,本文是博主学完这章内容后的个人总结,要是文章里有什么错误还望各位大神指正。或者对我的文章排版和其他方面有什么建议,也可以在评论区告诉我。如果我的文章对你的学习有帮助,或者觉得写得不错的话记得分享给你的朋友,非常感谢。


点击全文阅读


本文链接:http://zhangshiyu.com/post/41099.html

元素  结构  文件  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1