数据结构——栈

用户11861691

发布于 2025-10-13 15:12:25

1000

代码可运行

运行总次数：0

代码可运行

在数据结构中，栈是一种基础且重要的线性结构，它遵循“先进后出”的基本原则，本文将从栈的基本概念出发，详细讲解其核心操作、实现方式、典型应用场景，并结合代码示例帮助大家深入理解。

一. 概念与结构

栈是一种特殊的数据结构，它只能从固定的一端进行插入或删除操作，我们将允许进行这些操作的一端称为栈顶（Top），另一端则称为栈底（Bottom），当栈中没有任何元素时，被称为空栈。在进行插入或删除数据时，遵循“先进后出”的基本准则（LIFO）

举个生活中的例子：叠放的碗，新洗好的碗会叠在最上面（栈顶插入），取碗时也只能从最上面拿（栈顶删除）；再比如浏览器的 “后退” 功能，最新打开的网页会优先被后退关闭，这也是栈的典型应用。

压栈：栈的插入操作被称为压栈/进栈/入栈，入数据栈顶

出栈：栈的删除操作称为出栈，出数据也在栈顶

栈底层结构选型

栈可以用顺序表或链表实现，但是相对而言，使用数组要更优一些，因为尽心入栈和出栈时的时间复杂度更低

二. 栈的实现

Stack.h （定义栈的结构和函数声明）

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//定义栈的结构
typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	int top;//指向栈顶的位置--刚好就是栈中有效数据的个数
	int capacity;
}ST;

//初始化
void STInit(ST* ps);

//销毁
void STDesTory(ST* ps);

//入栈
void STPush(ST* ps, STDataType x);

//栈是否为空
bool STEmpty(ST* ps);

//出栈
void STPop(ST* ps);

//取栈顶
STDataType STTop(ST* ps); 

//获取栈中有效元素个数
int STSize(ST* ps);

Stack.c （函数实现）

#include"Stack.h"

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

//销毁
void STDesTory(ST* ps)
{
	if (ps->arr)
		free(ps->arr);

	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

//入栈
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	//判断空间是否足够
	if (ps->top == ps->capacity)
	{
		//增容
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
	//空间足够
	ps->arr[ps->top++] = x;
}

//栈是否为空
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

//出栈
void STPop(ST* ps)
{
	assert(!STEmpty(ps));
	ps->top--; 
}

//取栈顶
STDataType STTop(ST* ps)
{
	assert(!STEmpty(ps));
    return ps->arr[ps->top - 1];
}

//获取栈中有效元素个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

（注：可自行创建测试文件去测试并实现一下以上代码，加深理解）