【数据结构】栈“0”基础知识讲解 + 实战演练

小年糕是糕手

发布于 2026-01-14 17:16:57

1030

文章被收录于专栏：C++学习C++学习

一、概念与结构

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

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

栈底层结构选型

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

我们选择数组而不是链表有如下的几点优势：

1. 访问效率更高

随机访问：数组在内存中是连续存储的，通过下标可以直接访问数组中的任意元素，时间复杂度为 O(1) 。对于栈操作中的获取栈顶元素操作，数组可以快速定位。例如在 C 语言中，定义一个整型数组 int stack[100]; ，要获取栈顶元素（假设栈顶元素下标为 top ），直接使用 stack[top] 就能获取到。
链表的顺序访问：链表由一个个节点组成，节点在内存中的位置不一定连续，访问某个节点时，需要从表头开始，逐个遍历节点，直到找到目标节点，时间复杂度为 O(n) ，其中 n 是链表的长度。如果用链表实现栈，获取栈顶元素需要从链表头开始遍历，效率较低。

2. 空间利用率更优

数组的紧凑空间：数组的内存分配是一次性的，只要在定义数组时预留合适的空间，就不会存在额外的内存开销。例如定义一个大小为 100 的整型数组 int stack[100]; ，它会连续占用 100 个 int 类型大小的内存空间，不会有其他额外空间。
链表的额外指针空间：链表的每个节点除了存储数据外，还需要额外存储指向下一个节点的指针（对于双向链表还需要存储指向前一个节点的指针），这会增加内存开销。比如一个存储整型数据的单向链表节点，除了存储 int 类型的数据外，还需要一个指针来指向下一个节点，这就导致同样存储 n 个整数，链表占用的内存空间比数组更多。

3. 实现简单

数组的操作简洁：使用数组实现栈，入栈操作只需要将元素放入指定下标位置，并更新栈顶指针；出栈操作只需更新栈顶指针，然后获取相应下标的元素，代码逻辑简单明了。例如入栈操作代码可以是 stack[++top] = element; ，出栈操作代码可以是 int popped = stack[top--]; 。
链表的复杂操作：链表实现栈，入栈时需要创建新节点，并调整指针指向；出栈时不仅要获取节点数据，还要处理节点释放以及指针调整等操作，代码相对复杂，容易出错。

4. 缓存友好

数组的局部性原理：由于数组在内存中连续存储，当访问数组中的一个元素时，根据计算机的缓存机制，与该元素相邻的其他元素也会被预加载到缓存中。当连续进行栈操作（如多次入栈、出栈）时，后续操作访问的数据大概率已经在缓存中，能够大大提高访问速度。
链表的缓存不友好：链表节点在内存中分布不连续，每次访问一个节点时，都可能需要重新从内存中读取，无法充分利用缓存，导致操作速度相对较慢。

二、栈的实现（重点）

2.1、Stack.h

#define _CRT_SECURE_NO_WARNINGS
#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 STDesTroy(ST* ps);

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

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

//出栈 -- 栈顶
//栈不能为空
void STPop(ST* ps);

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

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

2.2、Stack.c

#include"Stack.h"

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

//栈的销毁
void STDesTroy(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;
	ps->top++;
}

//判断栈是否为空
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;
}

2.3、test.c

#include"Stack.h"

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

	//STPop(&st);
	//循环出栈并且打印出栈元素
	while (!STEmpty(&st))
	{
		//取栈顶
		STDataType top = STTop(&st);
		printf("%d ", top);
		//出栈
		STPop(&st);
	}
	printf("\n");

	printf("size:%d\n", STSize(&st));

	STDesTroy(&st);
}

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

三、栈算法题（难点）

3.1、有效的括号

https://leetcode.cn/problems/valid-parentheses/description/

思路：借助数据结构--栈，遍历字符串，左括号入栈，是右括号就取栈顶元素比较，是否匹配

先将左括号全部入栈然后用指针pi去遍历右括号与栈顶元素比较，看看是否匹配，匹配成功就出栈，如果最后栈为空就返回true，否则就返回false

时间复杂度：O(N)

//定义栈的结构
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 STDesTroy(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;
	ps->top++;
}

//判断栈是否为空
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;//s就是指向字符串的第一个字符
    while(*pi != '\0')
    {
        //左括号入栈
        if(*pi == '(' || *pi == '[' || *pi =='{')
        {
            STPush(&st,*pi);
        }
        else
        {
            //右括号 -- 取栈顶，比较，匹配则出栈，不匹配直接返回false
            //栈不为空才能取栈顶
            if(STEmpty(&st))
            {
                STDesTroy(&st);
                return false;
            }
            char top = STTop(&st);
            if((top == '(' && *pi != ')')
            ||(top == '[' && *pi != ']')
            ||(top == '{' && *pi != '}'))
            {
                STDesTroy(&st);
                return false;
            }
            //本次是匹配的 -- 出栈
            STPop(&st);
        }
        pi++;
    }
    //判断栈是否为空，为空有效，非空无效
    if(STEmpty(&st))
    {
        STDesTroy(&st);
        return true;
    }
    STDesTroy(&st);
    return false;

    //也可以简写成如下：
    //bool ret = STEmpty(&st) ? true :false
    //STDesTroy(&st);
    //return ret;
}

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

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

数据