文章目录
- 栈
- 一. 栈的概念及结构
- 二. 栈的实现
- 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）原则。在一些递归深度非常深的时候，我们可以利用栈的知识去模拟内存中的栈，这样可以防止栈溢出。最后，本文是博主学完这章内容后的个人总结，要是文章里有什么错误还望各位大神指正。或者对我的文章排版和其他方面有什么建议，也可以在评论区告诉我。如果我的文章对你的学习有帮助，或者觉得写得不错的话记得分享给你的朋友，非常感谢。