文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >【数据结构与算法】数据结构初阶：详解栈和队列（上）——栈

【数据结构与算法】数据结构初阶：详解栈和队列（上）——栈

作者头像
艾莉丝努力练剑
发布于 2025-11-13 10:13:41
发布于 2025-11-13 10:13:41
2120
举报
文章被收录于专栏：C / C++C / C++

🔥个人主页：艾莉丝努力练剑 ❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题 🍉学习方向：C/C++方向 ⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平

​

前言：本篇文章，我们继续来看顺序表和链表相关的知识点，在初阶的数据结构与算法阶段，我们把知识点分成三部分，复杂度作为第一部分，顺序表和链表、栈和队列、二叉树为第二部分，排序为第二部分，我们之前已经介绍完了第一部分：算法复杂度，本文我们继续学习第二部分中的栈和队列部分内容啦。

再次提醒：为什么我们要学那么多的数据结构？这是因为没有一种数据结构能够去应对所有场景。我们在不同的场景需要选择不同的数据结构，所以数据结构没有谁好谁坏之分，而评估数据结构的好坏要针对场景，如果在一种场景下我们需要频繁地对头部进行插入删除操作，那么这个时候我们用链表；但是如果对尾部进行插入删除操作比较频繁，那我们用顺序表比较好。 因此，不同的场景我们选择不同的数据结构。

目录

正文

一、栈

（一）栈的概念与结构

1、栈的概念

2、栈的结构

（二）栈结构的实现（用数组实现）

1、初始化

2、销毁

3、入栈——栈顶

4、判断栈是否为空

5、出栈——栈顶

6、取栈顶元素

7、栈结构实现（数组）的完整代码

（1）List.h：

（2）List.c：

（3）test.c：

（三）栈的应用

结尾

正文

一、栈

（一）栈的概念与结构
1、栈的概念

概念：栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

栈有点类似于水杯，杯口进水喝水，杯底即栈底。

我们在栈顶插入删除数据，数据的插入删除都只在一端——栈顶——完成。

即：

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

LIFO：Last In First Out，“后进先出”或者说“先进后出”。

理解：当我们往收纳箱里面放东西，先放进去的东西会在箱底，会放进去的东西会在箱顶，我们之后取出来的时候是先取出上面的东西，最后再取出最先放进去的东西。

​

2、栈的结构

逻辑结构：是线性的； 物理结构：不一定，取决于你是用数组实现的还是用链表实现的，如果是用数组实现的，数组是连续存放，元素地址都是连续的，此时是线性结构，用链表实现则不是线性结构。

对于栈我们是用数组实现还是用链表来实现？

​

（二）栈结构的实现（用数组实现）
1、初始化

（1）List.h：

代码语言：javascript
复制
#pragma once
#include<stdio.h>
#include<stdlib.h>

typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	STDataType size;//定义栈中有效的数据个数
	STDataType capacity;//栈的空间大小
}ST;

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

（2）List.c：

代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS  1

#include"Stack.h"

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

（3）test.c：

代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS  1

#include"Stack.h"

void test01()
{
	ST st;
	STInit(&st);
}

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

​

现在初始化完了，我们就有了一个空栈，有了空栈我们就可以去实现栈相关的一系列操作。

2、销毁

我们先来实现一下销毁，和初始化类似。

List.c：

代码语言：javascript
复制
//销毁
void STDestory(ST* ps)
{
	if (ps->arr)
		free(ps->arr);

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

test.c：

代码语言：javascript
复制
#include"Stack.h"

void test01()
{
	ST st;
	STInit(&st);

	STDestory(&st);
}

int main()
{
	test01();
	return 0;
}
3、入栈——栈顶

栈顶插入数据，栈顶对于数组来说就是数组的尾部，栈顶插入数据即在数组尾部插入数据。

List.c：

代码语言：javascript
复制
//入栈——栈顶
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	//判断空间是否足够
	if (ps->top == ps->capacity)
	{
		//增容
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		int* 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;
}

test.c：

代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS  1

#include"Stack.h"

void test01()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);

	STDestory(&st);
}

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

如果再加一个数据，我们来观察一下【监视】中capacity的值有什么变化——

代码语言：javascript
复制
    STPush(&st, 5);

【监视】栏capacity的值发生了变化——

4、判断栈是否为空

List.c：

代码语言：javascript
复制
//栈是否为空
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
5、出栈——栈顶

List.c：

代码语言：javascript
复制
//出栈——栈顶
void STPop(ST* ps)
{
	assert(!STEmpty(ps));
	ps->top--;
}

test.c：

代码语言：javascript
复制
#include"Stack.h"

void test01()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);

	STPop(&st);
	STDestory(&st);
}

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

运行一下——

6、取栈顶元素

我们要取top-1的位置，不能取top，top指向的是一个无效的数据。

List.c：

代码语言：javascript
复制
//获取栈中有效元素个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

test.c：

代码语言：javascript
复制
#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");
	STDestory(&st);
}

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

运行一下——

7、栈结构实现（数组）的完整代码

到这里，栈相关的结构我们都实现完了，是不是比前面的顺序表和链表都要简单？

（1）List.h：
代码语言：javascript
复制
#pragma once
#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);

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

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

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

//获取栈中有效元素个数
int STSize(ST* ps);
（2）List.c：
代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS  1

#include"Stack.h"

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

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

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

//入栈——栈顶
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	//判断空间是否足够
	if (ps->top == ps->capacity)
	{
		//增容
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		int* 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;
}
（3）test.c：
代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS  1

#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");
	STDestory(&st);
}

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

注意：ps不能传空！

（三）栈的应用

链接：20.有效的括号

博主的题解： 借助数据结构——栈——解决经典例题【有效的括号】

题目描述：

这道题博主会放到博主的专栏【LeetCode代码强化刷题】 里面，本文不会详解。

题目链接和力扣题解博主放在大标题下面了，大家可以去浏览一下，做一做。

代码演示：

代码语言：javascript
复制
//定义栈的结构
typedef char STDataType;
typedef struct Stack
{
	STDataType* arr;
	int top;//定义栈中有效的数据个数
	int capacity;//栈的空间大小
}ST;

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

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

	ps->arr = NULL;
	ps->top = ps->capacity = 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;
}
//-----------------------以上是栈结构定义和常见方法-------------------------
bool isValid(char* s) 
{
    //借助数据结构——栈
    ST st;
    STInit(&st);
    char* pi = s;
    while(*pi != '\0')
    {
        //左括号入栈
        if(*pi == '(' || *pi == '[' || *pi == '{')
        {
            STPush(&st,*pi);
        }
        else
        {
            //右括号——取栈顶，比较，匹配则出栈，不匹配直接返回false
            //栈不为空才能取栈项
            if(STEmpty(&st))
            {
                STDestory(&st);
                return false;
            }
            char top = STTop(&st);
            if((top == '(' && *pi != ')')
            ||(top == '[' && *pi != ']')
            ||(top == '{' && *pi != '}'))
            {
                STDestory(&st);
                return false;
            }
            //本次是匹配的——出栈
            STPop(&st);
        }
        pi++;
    }
    //判断栈是否为空，为空有效，非空无效
    // if(STEmpty(&st))
    // {
    //     STDestory(&st);
    //     return true;
    // }
    // STDestory(&st);
    // return false;
    //写成三目表达式
    bool ret = STEmpty(&st) ? true : false;
    STDestory(&st);
    return ret;
}

复杂度：时间复杂度：O(N) ，空间复杂度：O(1)。

结尾

往期回顾：

【数据结构与算法】数据结构初阶：详解顺序表和链表（五）——双向链表

【数据结构与算法】数据结构初阶：详解顺序表和链表（四）——单链表（下）

【数据结构与算法】数据结构初阶：详解顺序表和链表（三）——单链表（上）

本期内容需要回顾的C语言知识如下面的截图中所示（指针博主写了6篇，列出来有水字数嫌疑了，就只放指针第六篇的网址，博主在指针（六）把指针部分的前五篇的网址都放在【往期回顾】了，点击【传送门】就可以看了）。 大家如果对前面部分的知识点印象不深，可以去上一篇文章的结尾部分看看，博主把需要回顾的知识点相关的博客的链接都放在上一篇文章了，上一篇文章的链接博主放在下面了：

【数据结构与算法】数据结构初阶：详解顺序表和链表（三）——单链表（上）

结语：本篇文章到这里就结束了，对数据结构的单链表知识感兴趣的友友们可以在评论区留言，博主创作时可能存在笔误，或者知识点不严谨的地方，大家多担待，如果大家在阅读的时候发现了行文有什么错误欢迎在评论区斧正，再次感谢友友们的关注和支持！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-11-12，如有侵权请联系 cloudcommunity@tencent.com 删除
队列
链表
数据
数据结构与算法
数据结构

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

队列
链表
数据
数据结构与算法
数据结构
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 目录
  • 正文
  • 一、栈
    • （一）栈的概念与结构
    • （二）栈结构的实现（用数组实现）
    • （三）栈的应用
  • 结尾
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2025 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论