【数据结构】栈

再睡一下就好

发布于 2025-06-10 18:32:12

11000

代码可运行

文章被收录于专栏：深究算法深究算法

运行总次数：0

代码可运行

前言

什么是栈？

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

栈顶栈底是什么，线性表又是什么？

栈顶与栈底是不固定的，取决于你想在哪边操作。

拿顺序表举例，若只在表尾增删，那表尾就是栈顶，相对的表头就是栈底。

如下图：

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

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

因为栈一般是存储在堆上的，故栈的大小可以看作无穷大（取决于你的机器）。

如果不清楚顺序表是什么，或想进一步了解线性表的概念，我们在之前的部分已经详细描述，这里就不再赘述，有兴趣的读者可移步：【数据结构】初阶——顺序表①

为什么说栈是受限制的，这源于栈的特性：后进先出（Last In First Out，LIFT)，即出数据时后进去的数据先出来。

一、栈的结构

栈一般使用数组或者链表，相对而言数组更优一些。因为数组在尾上插入数据的代价比较小。若是在头上插入数据，链表需要额外设一个头节点而数组也需要挪动数据，这些操作都会有所损耗。

在前言中我们曾拿顺序表举列以讲解栈，其实栈可以看作仅在表尾进行操作的顺序表以方便理解

下面是栈的结构体实现：

typedef int DateType;

typedef struct stack
{
	DateType* _a;
	size_t _top;//有效数据个数
	size_t _capacity;//空间大小
}stack;

感觉与顺序表的结构体几乎一样：

二、实现

1.初始化

//初始化
void InitStack(stack* ps)
{
	assert(ps);
	DateType* tmp = (DateType*)malloc(sizeof(DateType) * 2);
	if (tmp)
	{
		ps->_a = tmp;
		ps->_top = 0;
		ps->_capacity = 2;
	}
	else
	{
		printf("error:InitSatck");
	}
}

2.基本接口

1)Push

说明：将数据入栈。

//入栈
void Push(stack* ps, DateType x)
{
	assert(ps);
	//空间不够增容
	if (ps->_capacity == ps->_top)
	{
		ps->_capacity=ps->_capacity * 2;
		DateType* tmp = (DateType*)realloc(ps->_a, sizeof(DateType) * ps->_capacity);
		if (tmp)
		{
			ps->_a = tmp;
		}
		else
		{
			printf("error:realloc");
			exit(-1);
		}
	}

	//压栈
	ps->_a[ps->_top] = x;
	ps->_top++;
}

2)Pop

说明：将数据出栈。

//出栈
void Pop(stack* ps)
{
	assert(ps);
	//不能删完了还删
	if (ps->_top > 0)
		ps->_top--;
}

3)Empty

说明：检测栈是否为空，为空则返回true，否则返回false。

//检测栈是否为空
bool StackEmpty(stack* ps)
{
	assert(ps);
	return ps->_top <= 0;
}

4)Top

说明：返回栈顶数据。

//获取栈顶数据
DateType StackTop(stack* ps)
{
	assert(ps);
	if (ps->_top > 0)
		return ps->_a[ps->_top - 1];
	else
		exit(-1);
}

5)Size

说明：返回栈中有效数据个数。

//返回栈中数据个数
size_t StackSize(stack* ps)
{
	assert(ps);
	return ps->_top;
}

3.销毁栈

//销毁栈
void Destory(stack* ps)
{
	assert(ps);

	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = ps->_top = 0;
}

三、完整代码

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

typedef int DateType;

typedef struct stack
{
	DateType* _a;
	size_t _top;//有效数据个数
	size_t _capacity;//空间大小
}stack;

//初始化
void InitStack(stack* ps)
{
	assert(ps);
	DateType* tmp = (DateType*)malloc(sizeof(DateType) * 2);
	if (tmp)
	{
		ps->_a = tmp;
		ps->_top = 0;
		ps->_capacity = 2;
	}
	else
	{
		printf("error:InitSatck");
	}
}

//入栈
void Push(stack* ps, DateType x)
{
	assert(ps);
	//空间不够增容
	if (ps->_capacity == ps->_top)
	{
		ps->_capacity=ps->_capacity * 2;
		DateType* tmp = (DateType*)realloc(ps->_a, sizeof(DateType) * ps->_capacity);
		if (tmp)
		{
			ps->_a = tmp;
		}
		else
		{
			printf("error:realloc");
			exit(-1);
		}
	}

	//压栈
	ps->_a[ps->_top] = x;
	ps->_top++;
}

//出栈
void Pop(stack* ps)
{
	assert(ps);
	//不能删完了还删
	if (ps->_top > 0)
		ps->_top--;
}

//检测栈是否为空
bool StackEmpty(stack* ps)
{
	assert(ps);
	return ps->_top <= 0;
}

//返回栈中数据个数
size_t StackSize(stack* ps)
{
	assert(ps);
	return ps->_top;
}

//获取栈顶数据
DateType StackTop(stack* ps)
{
	assert(ps);
	if (ps->_top > 0)
		return ps->_a[ps->_top - 1];
	else
		exit(-1);
}

//销毁栈
void Destory(stack* ps)
{
	assert(ps);

	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = ps->_top = 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-06-10，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构