深入解析数据结构之栈及其应用

云泽808

发布于 2025-12-30 17:44:14

450

一、栈

1.1 概念与结构

栈：一种特殊的线性表（逻辑结构一定是线性的，物理结构不一定），其只允许再固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶出栈：栈的删除操作叫做出栈，出数据也在栈顶

栈底层结构选型栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。原因如下：

使用数组来实现栈时，栈的核心操作（入栈，出栈）只需操作数组尾部元素，时间复杂度都是O（1）

struct Stack
{
   int* arr;
   int size;
   int capacity;
}

使用链表来实现栈时，栈的核心操作（入栈，出栈）都可以在链表的头部进行操作，时间复杂度都是O（1）

struct Stack
{
   int data;
   struct Stack* next;
}

这样看好像二者没有差别，但数组的优势不止如此：

数组的元素在内存中连续存储，所以其访问元素通过索引直接定位，无需像链表那样遍历查找
数组无需存储额外的指针/引用信息，内存利用率更高。链表每个节点需要额外空间存储指针，尤其在元素数量较多时，额外开销显著。（就比如说这里要存储3个整型数据，用链表来实现栈的空间更大，因为用链表实现要有3个节点大小的空间，一个节点差不多8个字节，消耗的空间更大。数组实现的话，就是向操作系统申请几个整型空间，也就是4个字节4个字节的增加，消耗空间更小）
数组实现只需要维护一个顶部指针，逻辑简单。链表实现需要处理节点的创建、删除和指针维护，容易出错。

可以发现栈的物理结构取决于底层实现，如果用数组实现，底层就是连续的（线性的），用链表实现（不连续的）

1.2 栈的实现

1.2.1 初始化

函数声明：

这里虽然栈的结构和顺序表几乎一摸一样，但是不同的数据结构，其提供的方法是不一样的。栈只有一端开口，栈只能在栈顶入数据和出数据

函数定义：

测试文件：

1.2.2 销毁

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

1.2.3 入栈

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

栈顶在数组的尾部，接下来把size改为top更符合栈的结构，top指向栈顶的位置，刚好就是栈中有效数据个数

这里和顺序表类似，空间足够，插入一个数据，size++

空间不够的话，就需要先额外增容了

补充：ps不能为空，否则对空指针进行解引用了

1.2.4 判断栈是否为空

出栈之前有个操作是判断栈是否为空，栈为空无数据可出了

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

栈顶为0的时候，说明栈中的有效数据个数为0

1.2.5 出栈

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

此时有5个空间，栈顶在下一个要插入数据的位置，栈顶对应的下标为4

出栈即少一个数据，栈顶要减减，此时栈中有4个有效的空间，只有3个有效的数据（3个有效的数据就是1，2，3，不包含4）

1.2.6 取栈顶元素

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

取栈顶并不是出栈，而是把栈顶这个元素返回

这个操作叫循环出栈，输出结果体现出栈后进先出的规则

1.2.7 获取栈中有效元素个数

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

二、完整源码

Stack.h

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

//定义栈的结构 - Stack是栈的名称
typedef int STDataType;
typedef struct Stack {
	STDataType* arr;//存储数据的数组
	int top;//top指向栈顶的位置，刚好就是栈中有效数据个数
	int capacity;//栈的空间大小
}ST;

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

//入栈---栈顶
void STPush(ST* ps, STDataType x);
//出栈---栈顶
void STPop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps);

//判断栈是否为空
bool STEmpty(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"

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

//销毁
void STDesTroy(ST* ps)
{
	//arr不能为空，为空的话都没有向操作系统中申请内存，就没有必要销毁了
	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;
		//如果capacity为0，就给4，realloc第二个参数的单位为字节，这里要申请4个整型空间，而不是4个字节
		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;
}

test.c

#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"

void test01()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	printf("size:%d\n", STSize(&st));
	//STPop(&st);
	while (!STEmpty(&st))
	{
		//取栈顶
		STDataType top = STTop(&st);
		printf("%d ", top);
		//出栈
		STPop(&st);
	}
	printf("\n");

	STDesTroy(&st);
}

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