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

【数据结构—栈的实现（数组栈）】

news 2025/8/3 2:29:29

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言

一、栈

1.1栈的概念及结构

二、栈的实现

2.1头文件的实现—Stack.h

2.2源文件的实现—Stack.c

2.3源文件的测试—test.c

三、栈的实际测试数据展示

3.1正常的出入栈展示：

3.2进栈同时也在出栈的展示：

前言

世上有两种耀眼的光芒，一种是正在升起的太阳，一种是正在努力学习编程的你!一个爱学编程的人。各位看官，我衷心的希望这篇博客能对你们有所帮助，同时也希望各位看官能对我的文章给与点评，希望我们能够携手共同促进进步，在编程的道路上越走越远！

提示：以下是本篇文章正文内容，下面案例可供参考

一、栈

1.1栈的概念及结构

数组：数组一般适合尾插和尾删，所以一般栈顶在尾部。
双向链表实现：尾插、尾删和头插、头删都一样，都符合后进先出的原则，所以栈顶可以是头，也可以是尾。
单链表实现：适合头插和头删，栈顶只能是头。

栈的规则：后进去的要先出来（后进先出）联想弹夹

top：两种设计方案
1、如果top指向栈顶元素，设空栈时，给top == 0,那么当空栈中插入一个元素时，由于top指向的是栈顶元素，top还是0，此时没法区分到底是空栈还是有一个元素的栈，那就设空栈时，给top == -1，当在栈中插入一个元素时，top == 0；
2、如果top指向栈顶元素的下一个位置，设空栈时，给top == 0，当在栈中插入一个元素时，top指向栈顶元素的下一个位置，所以top == 1（也可以看成top就是栈中的数据个数）

二、栈的实现

2.1头文件的实现—Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int STDataType;
typedef struct stack
{STDataType* a;int top;//标识栈顶的位置int capacity;
}ST;//初始化
void STInit(ST* pst);
//销毁
void STDestory(ST* pst);//压栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);//获取栈顶元素
STDataType STTop(ST* pst);//判空
bool STEmpty(ST* pst);//统计栈内元素个数
int STSize(ST* pst);

2.2源文件的实现—Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"//初始化
void STInit(ST* pst)
{assert(pst);pst->a = NULL;//表示top指向栈顶元素的下一个位置pst->top = 0;//表示top指向栈顶元素//pst->top = -1;pst->capacity = 0;
}
//销毁
void STDestory(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->capacity = pst->top = 0;
}//压栈
void STPush(ST* pst, STDataType x)
{assert(pst);//判断数组栈空间是否足够if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}
//出栈
void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}//获取栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}//判空
bool STEmpty(ST* pst)
{assert(pst);//判断数组栈为空//1、如果top是指向栈顶元素的下一个位置，那当top == 0时，栈为空//2、如果top时指向栈顶元素，那当top == -1时，栈为空/*if (pst->top == 0){return true;}else{return false;}*/return pst->top == 0;
}//统计栈内元素个数
int STSize(ST* pst)
{assert(pst);//1、如果top指向栈顶元素的话，栈内元素的个数为top+1；//2、如果top指向栈顶元素的下一个位置的话，栈内元素的个数为top；return pst->top;
}

2.3源文件的测试—test.c

#include "Stack.h"int main()
{ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);printf("%d ", STTop(&s));STPop(&s);STPush(&s, 4);STPush(&s, 5);//入栈顺序（一种）  --  出栈顺序（多种）//是一对多的关系while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}printf("\n");return 0;
}