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

栈的基本操作

article 2024/11/15 8:48:13

𝙉𝙞𝙘𝙚!!👏🏻‧✧̣̥̇‧✦👏🏻‧✧̣̥̇‧✦ 👏🏻‧✧̣̥̇:Solitary-walk

⸝⋆ ━━━┓
- 个性标签 - ：来于“云”的“羽球人”。 Talk is cheap. Show me the code
┗━━━━━━━ ➴ ⷯ

本人座右铭：欲达高峰,必忍其痛;欲戴王冠,必承其重。

👑💎💎👑💎💎👑
💎💎💎自💎💎💎
💎💎💎信💎💎💎
👑💎💎　💎💎👑 希望在看完我的此篇博客后可以对你有帮助哟

👑👑💎💎💎👑👑 此外，希望各位大佬们在看完后，可以支持一下。
👑👑👑💎👑👑👑

一：初始化

二：销毁

三：进栈（入栈 / 压栈）

四：出栈

五：获取栈顶元素

六：求栈中元素个数

七：判空

八：练习

栈的基本了解：栈的概念和结构：

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。

栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

1：初始化

在对栈进行初始化之前需要先对栈这个结构进行定义一下

这里暂且就以数组栈为例

typedef int STDataType;
typedef struct Stack {
	STDataType* a;//动态的
	int capacity;//容量
	int top;//记录栈顶位置
}ST;

初始化：让 capacity = 0,至于 top 是为0 还是为 1，自行决定

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;//表示 top  指向栈顶元素下一个位置
	//pst->top = -1;//表示 top  指向栈顶元素的位置
}

2：销毁

这个就很简单了，直接对数组进行销毁即可

3：进栈（入栈 / 压栈）

注意：初始化 top 的值对进栈的操作很重要

top = 0 ：top 指向栈顶元素下一个的位置

top = 0 ，此时进栈需要先把数据插到 top 对应的位置，之后top++

top = 0 ：刚好也可以表示栈中数据元素个数为 0

top = -1 :top 指向栈顶元素位置

top = -1：

进栈的操作：先让top++；再对top 所在地位置进行插入数据

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)
			return;
		//成功
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;//指向栈顶元素下一个位置
}

4：出栈

直接一步到位即可；让top - -

注意不是 top -1

void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));//判空
	pst->top--;
}

5：获取栈顶元素

STDataType STTop(ST* pst)//获取栈顶元素
{
	assert(pst);
	return pst->a[pst->top-1];// 注意top 永远指向栈顶元素下一个位置
}

6：求栈中元素个数

int STSize(ST* pst)//求栈中元素个数
{
	assert(pst);
	return pst->top;
}

7：判空

bool STEmpty(ST* pst)
{
	assert(pst);
	/*if (pst->top == 0)
	{
		return true;
	}
	else
		return false;*/
	return pst->top == 0;//不用三目操作符
}

完整代码：

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"

void test()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	//STPrint(&st);//注意没有这种写法
	//对于栈的访问都是边访问边出栈
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);
	STPush(&st, 6);
	int size = STSize(&st);
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));//获取栈顶元素
		STPop(&st);//出栈
	}
	STDestroy(&st);


}
int main()
{
	test();
	return  0;
}

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;//表示 top  指向栈顶元素下一个位置
	//pst->top = -1;//表示 top  指向栈顶元素的位置
}
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
}

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)
			return;
		//成功
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;//指向栈顶元素下一个位置
}
void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));//判空
	pst->top--;
}

STDataType STTop(ST* pst)//获取栈顶元素
{
	assert(pst);
	return pst->a[pst->top-1];// 注意top 永远指向栈顶元素下一个位置
}

int STSize(ST* pst)//求栈中元素个数
{
	assert(pst);
	return pst->top;
}

bool STEmpty(ST* pst)
{
	assert(pst);
	/*if (pst->top == 0)
	{
		return true;
	}
	else
		return false;*/
	return pst->top == 0;//不用三目操作符
}

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 capacity;//容量
	int top;//记录栈顶位置
}ST;

void STInit(ST* pst);
void STDestroy(ST* pst);

void STPush(ST* pst, STDataType x);
void STPop(ST* pst);

STDataType STTop(ST* pst);//获取栈顶元素

int STSize(ST* pst);//求栈中元素个数

bool STEmpty(ST* pst);