【数据结构—栈的实现(数组栈)】

2023-12-13 16:32:38

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

文章目录

前言

一、栈

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;
}

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

1.栈的出栈和入栈的关系是:一对多的关系
2.元素出入栈的规则:
后进先出

3.1正常的出入栈展示:

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

总结

好了,本篇博客到这里就结束了,如果有更好的观点,请及时留言,我会认真观看并学习。
不积硅步,无以至千里;不积小流,无以成江海。

文章来源:https://blog.csdn.net/2301_79585944/article/details/134973474
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。