ps: 本文所有图均为博主亲手所画,本文所有代码基于vs2022实现

系列文章目录

数据结构初探: 顺序表
数据结构初探:链表之单链表篇
数据结构初探:链表之双向链表篇
链表特别篇:链表经典算法问题

---

---

前言

• 在计算机科学的浩瀚宇宙中，数据结构是构建各类程序大厦的基石，而栈，无疑是其中一颗独特且闪耀的明星。或许你在日常编程时常常与它打交道，却未曾深入探究其背后的奥秘；又或许你对它只是略有耳闻，好奇它究竟为何能在算法世界中占据重要地位。今天，就让我们一同踏上探索栈的奇妙之旅，从它独特的后进先出概念，到数组与链表实现下的精妙结构，再到广泛应用场景，全方位剖析栈的魅力与价值，带你解锁栈的全新认知，感受数据结构的迷人之处 。

---

一.栈的概念及其结构

1.1概念

• 栈是一种运算受限的线性表,只允许在固定的一段进行数据的操作，它按照后进先出（Last In First Out，LIFO）的原则存储数据。形象地说，栈就像一个只有一端开口的容器，比如羽毛球筒。最后放入筒中的羽毛球会最先被取出，而最先放入的羽毛球则最后被取出。
  

• 在计算机领域，栈有着广泛应用。例如，在编程语言中，函数调用时会使用栈来管理局部变量和返回地址。当一个函数被调用时，其相关的信息（如参数、局部变量等）会被压入栈中，函数执行完毕后，这些信息会从栈中弹出。此外，表达式求值、括号匹配等问题也常借助栈来解决。

1.2结构

栈主要由以下几个部分构成：

• 栈顶指针：栈顶指针用于指示栈顶元素的位置，它是栈操作的关键。通过栈顶指针，我们可以快速访问栈顶元素，执行压栈（将元素放入栈中）和弹栈（从栈中取出元素）操作。当栈为空时，栈顶指针通常指向一个特定的位置（如 -1 或者 NULL，这取决于具体的实现方式）。每次压入新元素，栈顶指针会相应移动以指向新的栈顶元素；每次弹出元素，栈顶指针也会反向移动。

• 栈元素存储区：这是实际存储栈中元素的地方。可以使用数组或者链表来实现这个存储区。

• 数组实现：使用数组实现栈时，数组的一端被视为栈底，另一端为栈顶。这种实现方式简单直观，访问效率高，因为数组的内存地址是连续的，可以通过索引快速定位元素。例如，定义一个整型数组 stack[100] 来存储栈元素，栈顶指针 top 用于指示栈顶元素的下标。当 top 为 -1 时，表示栈为空；当要压入元素 x 时，先将 top 加 1，然后 stack[top] = x ；弹出元素时，先取出 stack[top] ，然后将 top 减 1。不过，静态数组实现的栈存在一个缺点，即数组大小在初始化时就已确定，如果栈中元素数量超过数组大小，就会发生栈溢出错误。

//静态数组实现栈
//静态栈
#define N 10
struct Stack
{int a[N];//存在与静态数组一样的问题int top;//开小了不够,开大浪费;
};

以下是动态栈的结构:

typedef int STDataType;typedef struct Stack
{STDataType* a;//动态数组int top;//存储栈顶位置int capacity;//空间容量
}ST;

• 链表实现：链表实现栈则更加灵活，它可以动态分配内存。链表的头节点作为栈顶，每次压栈操作就是在链表头部插入一个新节点，每次弹栈操作就是删除链表头部节点。这种实现方式不会出现栈溢出问题（只要系统内存足够），但由于链表节点的内存地址不连续，访问效率相对数组实现会低一些。我们一般使用动态数组实现,本文将围绕动态栈来展开;

二.准备工作

创建对应的三个文件夹:

1.Stack.h:

用于存储顺序表的结构和增删查改函数声明,以及对应的库函数;

2.Stack.c:

用于函数的实现;

3.test.c:

用于测试和修改;
ps:2和3,均要包含头文件1,即(#include"Stack.h").

三.栈的增删查改的实现

1.Stack.h:

栈结构和函数声明:

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//静态栈
//#define N 10
//struct Stack
//{
//	int a[N];
//	int top;
//};typedef int STDataType;
//动态栈
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;
//打印
void STInit(ST* ps);
销毁
void STDestroy(ST* ps);
//插入
void STPush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//有效数据个数
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//返回栈顶元素
STDataType STTop(ST* ps);

老规矩,熟悉熟悉,我们开始函数接口的实现!

2.Stack.c:

我们单刀直入,其实相较于顺序表和链表,我们的栈算是简单的了

2.1栈的初始化

//首先我们先传我们的栈的结构体指针,从而找到我们创建的顺序表
//因为我们这样找到的是地址,所以就不存在形参无法影响实参的问题了
void STInit(ST* ps)
{assert(ps);//断言,防止传空;//动态开辟初始化空间ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL)//老规矩,判断是否开辟失败{perror("malloc fail");//返回错误行return;//直接结束}ps->capacity = 4;//更新空间容量ps->top = 0; //top是栈顶元素的下一个;//ps->top = -1; //top是栈顶元素位置;
}

2.2栈的销毁

void STDestroy(ST* ps)
{assert(ps);free(ps->a);//释放ps->a = NULL;//置空,我们修改的是结构体内部数组,ps->top = 0;//所以只要传一级指针就可以ps->capacity = 0;//全部清空
}

2.3栈的内存检查并扩容

void CapacityCheck(ST* ps)
{assert(ps);
//如果有效数据个数与空间容量相等,说明此时数组已经满了,需要进行扩容;if (ps->top == ps->capacity){//与顺序表没什么两样STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;//更新空间容量}
}

2.4栈的压入(压栈)/栈的插入

void STPush(ST* ps, STDataType x)
{assert(ps);CapacityCheck(ps);//检查ps->a[ps->top] = x;//压入ps->top++;//计量有效数据个数
}

2.5栈的删除(出栈)

void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));
//我们只需要top--,将其排除在外即可,因为本来我们插入前,
//这个位置就是随机值,排除在外后,它是什么数值都与我无关了,
//所以置不置为0都没关系ps->top--;
}

2.6返回栈的元素数量

int STSize(ST* ps)
{//top是栈顶元素的下一个;assert(ps);
//直接返回就是元素数量return ps->top;
}

2.7检查栈是否为空

bool STEmpty(ST* ps)
{assert(ps);
//我们初始化是就为0,此时空只要判断即可return ps->top == 0;
}

2.8返回栈顶元素

STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];//top是栈顶元素的下一个,所以得减1;
}

2.9完整代码

#define _CRT_SECURE_NO_WARNINGS 1#include"Stack.h"//栈的初始化;
void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->capacity = 4;ps->top = 0; //top是栈顶元素的下一个;//ps->top = -1; //top是栈顶元素位置;
}//栈的销毁;
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}//栈的内存检查并扩容;
void CapacityCheck(ST* ps)
{assert(ps);if (ps->top == ps->capacity){STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}//栈的压入(压栈)/栈的插入;
void STPush(ST* ps, STDataType x)
{assert(ps);CapacityCheck(ps);ps->a[ps->top] = x;ps->top++;
}//栈的删除(出栈);
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}//返回栈的元素数量;
int STSize(ST* ps)
{assert(ps);return ps->top;
}//检查栈是否为空;
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//返回栈顶元素;
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];//top是栈顶元素的下一个,所以得减1;
}

怎么样,我们来测试一下;

3.test.c

代码:

#define _CRT_SECURE_NO_WARNINGS 1#include"Stack.h"int main()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);//printf("%d ", STTop(&st));//STPop(&st);STPush(&st, 3);STPush(&st, 4);//printf("%d ", STTop(&st));//STPop(&st);STPush(&st, 5);while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}STDestroy(&st);return 0;
}

怎么样,学会了吗?

四.栈的优缺点

优点

• 操作简单高效：栈的基本操作，如压栈和弹栈，时间复杂度通常为$O(1)$，实现起来逻辑清晰，执行速度快，能快速地在栈顶进行数据的插入和删除操作，在需要频繁进行此类操作的场景中效率很高。
• 数据管理有序：遵循后进先出的原则，使得数据的存储和访问具有明确的顺序，对于处理具有层次结构或嵌套关系的任务，如表达式求值、函数调用等，能很好地维护数据的逻辑关系，方便进行数据的管理和处理。
• 空间利用灵活：用链表实现栈时，可以根据实际需求动态分配内存空间，理论上只要系统内存足够，就不会出现空间不足的问题，能有效利用系统资源，避免了数组实现可能出现的固定大小限制导致的空间浪费或溢出问题。
• 辅助复杂算法：是许多复杂算法和数据结构的基础组成部分，例如在深度优先搜索算法中，栈可以用来保存搜索路径和状态，帮助算法实现回溯和遍历，为解决更复杂的问题提供了有力支持。

缺点

• 访问限制严格：只允许在栈顶进行操作，要访问栈中的其他元素，必须先将栈顶元素及它与目标元素之间的所有元素弹出，操作不便，缺乏像数组那样可以随机访问元素的灵活性，在需要频繁随机访问数据的场景中效率低下。
• 可能导致栈溢出：使用数组实现栈时，如果事先分配的数组空间过小，当栈中的元素数量超过数组容量时，就会发生栈溢出错误，导致程序异常，而链表实现虽然不容易出现栈溢出，但在系统内存紧张时也可能出现问题。
• 数据组织形式单一：主要适用于满足后进先出需求的场景，对于需要其他数据组织形式，如先进先出（队列）、按照特定顺序排序等情况，栈就无法直接满足需求，需要额外的操作或数据结构来辅助实现。

---

五.总结

• 栈，这个看似简单的数据结构，实则蕴含着巨大能量。它以独特的后进先出原则，在计算机科学领域中占据着无可替代的地位。从函数调用时对栈帧的精准管理，到表达式求值、括号匹配时的高效运作，栈的身影无处不在。

• 其结构由栈顶指针和栈元素存储区构成，无论是数组实现带来的简单直观与高效访问，还是链表实现提供的动态灵活与无限扩展，都让栈在不同场景下发挥优势。当然，它也存在访问受限、可能溢出等不足，但这些并不影响它成为算法世界的得力助手。

• 深入理解栈，不仅能让我们洞悉程序运行的底层逻辑，更能在算法设计与问题解决中，为我们提供全新的思路和方法。希望大家通过对栈的探索，在编程之路上不断精进，挖掘出更多数据结构的奥秘 。