栈的实现详解

目录

• 1. 栈
• • 1.1 栈的概念及结构
  • 1.2 栈的实现方式
  • 1.3 栈的应用场景
• 2. 栈的实现
• • 2.1 结构体
  • 2.2 初始化
  • 2.3 销毁
  • 2.4 入栈
  • 2.5 出栈
  • 2.6 获取栈顶元素
  • 2.7 判空
  • 2.8 获取个数
• 3. test主函数
• 4. Stack.c文件
• 5. Stack.h文件
• 6. 运行展示

1. 栈

1.1 栈的概念及结构

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

1.2 栈的实现方式

栈可以通过多种方式实现，包括数组和链表等。使用数组实现的栈具有连续的内存空间，操作效率较高；而使用链表实现的栈则更加灵活，可以在动态环境中调整栈的大小。

实现用的是数据栈。

1.3 栈的应用场景

函数调用：在计算机程序中，函数调用和返回的过程可以用栈来实现。当调用一个函数时，会将函数的返回地址和参数压入栈中；当函数返回时，会从栈中弹出这些信息，并返回到调用点继续执行。
浏览器的前进与后退：在浏览器中，可以使用两个栈来实现前进和后退功能。一个栈记录新访问的页面，另一个栈记录后退弹出的页面。当用户点击前进按钮时，从记录新访问页面的栈中弹出页面；当用户点击后退按钮时，从记录后退页面的栈中弹出页面。
表达式求值：在编译器中，可以使用栈来进行表达式的求值。将运算符和操作数压入栈中，并根据运算符的优先级和结合性进行出栈和计算操作，最终得到表达式的值。

2. 栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

2.1 结构体

首先要先把结构体定义出来，一个是数组栈，一个是指向栈顶元素的下一个，还有一个是增容。

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//指向栈顶元素的下一个
	int capaicty;
}ST;

2.2 初始化

top等于0指向栈顶元素的下一个位置，top等于-1指向栈顶元素

//初始化
void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	//pst->top = -1;//指向栈顶元素
	pst->top = 0;//指向栈顶元素的下一个位置
	pst->capaicty = 0;
}

2.3 销毁

防止造成野指针的错误

//销毁
void STDestroy(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	pst->top = 0;
	pst->capaicty = 0;
	free(pst->a);
}

2.4 入栈

先判断容量是否够，再实现动态增容。

//入栈
void STPush(ST* pst, STDataType x)
{
	//扩容
	if (pst->top == pst->capaicty)
	{
		int newCapaicty = pst->capaicty = 0 ? 4 : pst->capaicty * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newCapaicty * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("STPush");
			return;
		}

		pst->a = tmp;
		pst->capaicty = newCapaicty;
	}

	pst->a[pst->top] = x;
	pst->top++;
}

2.5 出栈

看栈是否空，不是空就不能删，再top减减就行

//出栈
void STPpo(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));

	pst->top--;
}

2.6 获取栈顶元素

因为top指向栈顶元素的下一个，所以top要减1，当然空的时候也要判断一下

//获取栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));

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

2.7 判空

//判空
bool STEmpty(ST* pst)
{
	assert(pst);

	return pst->top == 0;
}

2.8 获取个数

打印之前可以看还有多少个在栈中

//获取个数
int STsize(ST* pst)
{
	assert(pst);

	return pst->top;
}

3. test主函数

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "Stack.h"

void TestStack1()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	printf("%d ", STTop(&st));
	STPpo(&st);
	STPush(&st, 3);
	STPush(&st, 4);
	printf("size: %d
", STsize(&st));
	
	//打印
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPpo(&st);
	}

	STDestroy(&st);
}

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

4. Stack.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
//初始化
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
//pst->top = -1;//指向栈顶元素
pst->top = 0;//指向栈顶元素的下一个位置
pst->capaicty = 0;
}
//销毁
void STDestroy(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0;
pst->capaicty = 0;
free(pst->a);
}
//入栈
void STPush(ST* pst, STDataType x)
{
//扩容
if (pst->top == pst->capaicty)
{
int newCapaicty = pst->capaicty = 0 ? 4 : pst->capaicty * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, newCapaicty * sizeof(STDataType));
if (tmp == NULL)
{
perror("STPush");
return;
}
pst->a = tmp;
pst->capaicty = newCapaicty;
}
pst->a[pst->top] = x;
pst->top++;
}
//出栈
void STPpo(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}
//获取栈顶元素
STDataType STTop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->a[pst->top - 1];
}
//判空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
//获取个数
int STsize(ST* pst)
{
assert(pst);
return pst->top;
}

5. Stack.h文件

#pragma once
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;//指向栈顶元素的下一个
int capaicty;
}ST;
//初始化
void STInit(ST* pst);
//销毁
void STDestroy(ST* pst);
//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPpo(ST* pst);
//获取栈顶元素
STDataType STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//获取个数
int STsize(ST* pst);

6. 运行展示