栈的基础细节(c语言)(全部代码，详细图解)：入栈，出栈，获取栈中数据个数，栈顶数据等.....

锻炼²

3731人浏览 · 2023-12-16 16:01:22

锻炼² · 2023-12-16 16:01:22 发布

前言

顺序存储(数组)(含详细图解)：（创建，初始化，入栈，出栈，获取栈中数据个数，获取栈顶数据，注销栈）

栈

一.栈的基本概念

1.1栈的基本概念

栈，也被称为堆栈，是一种特殊的线性表，其特点是只允许在一端（称为栈顶Top）进行插入和删除操作，而另一端（称为栈底Bottom）则是固定的，不允许进行插入和删除。这一特性使得栈具有"后进先出"（LIFO, Last In First Out）的操作原则，也就是说最后一个进入栈的元素会被首先删除。
栈的基本操作有两种：进栈（或压栈）和出栈（或退栈）。进栈是将新元素放到栈顶元素的上面，使之成为新的栈顶元素；而出栈则是将栈顶元素删除，使其相邻的元素成为新的栈顶元素。

1.2基本图

线性表和栈都是数据结构的种类，它们之间存在着一定的关联性。线性表是一种数据存储结构，它是一组元素的有限序列，这些元素在逻辑上是线性排列的。而栈则是一种受限的线性表，它只允许在表的一端（称为栈顶Top）进行插入和删除操作，另一端（称为栈底Bottom）则是固定的，不允许进行插入和删除。

尽管栈是一种特殊的线性表，但它们之间存在一些明显的区别。首先，线性表的插入和删除操作可以在任意位置进行(数组)，这不会改变元素之间的相对位置；而栈的插入和删除操作只能在栈顶进行，这会改变栈中元素的相对位置。其次，线性表支持全序操作，即可以通过比较元素的大小来确定其相对位置；而栈则不支持全序操作，因为栈的元素进出顺序是按照"后进先出"的原则进行的。

二.构建一个结构体

2.1创建结构体代码

typedef int STDataType;
typedef struct Stack {
	STDataType* a;
	int top;
	int capacity;
}ST;

2.2创建结构体图解

三.栈初始化

3.1初始化代码

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

3.2栈初始化图解

四. 入栈

4.1入栈代码

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

4.2入栈图解1

4.2入栈细节图解2

五.出栈

5.1出栈代码

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//判断是否非空
	ps->top--;
}

5.2出栈细节图解

六.获取栈内的个数

6.1获取栈内个数代码

//获取数据个数
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

6.2栈内个数图解

七.获取栈顶数据

7.1获取栈顶数据代码

//获取栈顶数据
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->a[ps->top - 1];
}

7.2获取栈顶数据图解

八.注销栈

8.1注销栈代码

//注销栈
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

8.2注销栈图解

九.检查栈是否为空

9.1检查栈是否为空代码

//返回1是空，返回0是非空
bool StackEmpty(ST* ps)
{
	return ps->top == 0;
}

9.2检查栈是否为空图解

十.全部代码

10.1全部代码

#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 StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);
int StackSize(ST* ps);
bool StackEmpty(ST* ps);



//初始化
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}


//注销栈
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

//入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//判断是否非空
	ps->top--;
}

//获取栈顶数据
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//判断是否非空

	return ps->a[ps->top - 1];
}

//获取数据个数
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}


//返回1是空，返回0是非空
bool StackEmpty(ST* ps)
{
	return ps->top == 0;
}




void PrintfStack(ST* ps)
{
	for (int i = 0; i < ps->top; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

TestStack()
{
	ST st;//创建结构体
	StackInit(&st);//初始化
	StackPush(&st, 3);//插入数据
	StackPush(&st, 8);
	StackPush(&st, 9);
	StackPush(&st, 11);
	StackPush(&st, 34);
	StackPush(&st, 67);

	printf("堆中的数据为：\n");
	PrintfStack(&st);
	printf("\n");

	printf("栈顶的数据为:%d \n", StackTop(&st));
	printf("\n");


	printf("出栈2次,现在的堆顶数据为：");
	StackPop(&st);
	StackPop(&st);
	printf("%d \n", StackTop(&st));
	printf("\n");

	printf("堆中的数据为：\n");
	PrintfStack(&st);
	printf("\n");


	printf("现在堆中的元素个数：%d \n", StackSize(&st));
	printf("\n");
	

	printf("全部出栈：");
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n");
	printf("\n");
	printf("现在堆中的元素个数：%d \n", StackSize(&st));

	//注销栈
	StackDestroy(&st);



}



int main()
{

	TestStack();
	return 0;
}