当前位置：首页 > article >正文

数据结构初阶之栈的介绍与栈的实现

article 2025/1/26 14:26:05

一、概念与结构

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

二、栈的实现

项目创建的时候，要创建一个头文件（.h）Stack.h ，两个源文件（.c）Stack.c ，test.c 。Stack.h 用于定义结构体和声明函数；Stack.c 用于实现函数；test.c 用于测试函数，每实现一个函数要进行相应的测试。编写代码过程中要勤测试，避免写出大量代码后再测试，如果出现问题，问题无从定位。

1、Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

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

//初始化栈
void Init_Stack(Stack* st);

//销毁栈
void Destory_Stack(Stack* st);

//判断栈是否为空
bool Empty_Stack(Stack* st);

//入栈
void Push_Stack(Stack* st, DataType x);

//出栈
void Pop_Stack(Stack* st);

//取栈顶数据
DataType Get_Top_Stack(Stack* st);

//获取栈中的有效元素的个数
int Count_Stack(Stack* st);

2、Stack.c

#include"Stack.h"

//初始化栈
void Init_Stack(Stack* st)
{
st->arr = NULL;
st->top = st->capacity = 0;
}

//销毁栈
void Destory_Stack(Stack* st)
{
   if (st->arr)
       free(st->arr);
   st->arr = NULL;
   st->top = st->capacity = 0;
}

//判断栈是否为空
bool Empty_Stack(Stack* st)
{
   assert(st);
   return st->top != 0;
}
//入栈
void Push_Stack(Stack* st, DataType x)
{
   assert(st);
   if (st->top == st->capacity)
   {
       int newcapacity = st->capacity ? 2 * st->capacity : 4;
       DataType* tmp = (DataType*)realloc(st->arr, newcapacity * sizeof(DataType));
       if (!tmp)
       {
           perror("realloc fail!");
           exit(1);
       }
       st->arr = tmp;
       st->capacity = newcapacity;
   }
   st->arr[st->top++] = x;
}