栈的实现及OJ练习（c语言）

前言

栈

栈的实现（数组栈）

初始化栈

前言

我们在之前已经学习了顺序表和链表的概念，它们有这样的优缺点：

链表的优势：

1、任意位置插入删除都是O（1）

2、按照申请释放、合理利用空间、不存在浪费

链表的劣势：

1、下标随机访问不方便，最坏时间复杂为O（n）

顺序表的优势：

1、支持下标随机访问，最坏时间复杂度为O（1）

顺序表的劣势：

1、头部或中间插入删除效率低，要挪动数据，最坏时间复杂度为O（n）

2、空间不够需要扩容，扩容有一定的消耗，且可能存在一定的空间浪费

3、只适合尾插尾删

我们之所以要学习各种各样的数据结构，是因为在实际应用中要选取最适合的一种数据结构去实现我们的需求，它们各有各存在的意义，今天我们来学习两种新的数据结构栈：

栈

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

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

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

栈的实现（数组栈）

概念：使用数组作为底层数据结构实现的栈

优势：

1. 简单高效：数组是一种连续的内存结构，可以直接通过索引访问元素。这使得在数组上进行栈操作（入栈和出栈）非常高效，时间复杂度为O(1)。相比于链表实现的栈，在插入和删除元素时不需要频繁地分配和释放内存。

2. 随机访问：由于数组具有随机访问的特性，我们可以通过索引快速地访问任意位置上的元素。这对于某些应用场景非常重要，例如需要查看或修改特定位置上的数据。

3. 存储连续性：由于数组是一段连续的内存空间，它能够更好地利用计算机硬件缓存系统带来的性能优势。相比之下，链表中每个节点可能分散在不同位置上，并且在遍历时会产生额外开销。

4. 空间效率：使用数组实现栈通常比使用链表实现占用更少的内存空间。链表节点除了保存数据本身外还需要额外空间来保存指向下一个节点地址等信息。

5. 实现简单：相对而言，在编写代码时使用基本类型（如整数、字符等）组成的简单静态数据结构（如数组）要比使用动态数据结构（如链表）更容易理解和实现。

注意事项：插入元素时需要提前确定存储空间的大小，并且如果栈满了，无法再添加新元素。这种情况下可能需要重新分配更大空间的数组并进行数据迁移操作。相比之下，链表可以动态地分配内存来适应不断变化的需求。

初始化栈


// 初始化栈
void StackInit(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
 
	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;    //令pop表示栈顶元素的下一个元素的下标
}

注意事项：

关于top的初始值有两种情况：

1、当top=0时，表示下一个要插入元素的位置，top等于多少栈里就有多少个元素

再详细的我也解释不出来了┭┮﹏┭┮

2、当top=-1时，表示栈顶元素的下标，下标等于-1时表示栈中没有有效元素

结论：相比于0，使用-1进行初始化可以更好地反映出该对象尚未包含任何有效数据项，同时还与我们学习的数组下标的概念契合（即下标为0表示数组第一个数字而当top=0时并没有这种说法）此外还可以更方便地判断堆叠是否为空，并与其他约定或标识符保持一致，从而提高代码的可读性和健壮性。

入栈


//入栈
void STPush(ST* pst, STDataType x)
{
    //首先要指向一个栈
	assert(pst);
    
    //判断栈是否已满，如果栈满则申请新的内存空间
	if (pst->top == pst->capacity)
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newCapacity;
	}
 
    //如果栈未满则进行入栈操作（若初始化时pop=-1，则下面两行代码交换执行顺序）
	pst->a[pst->top] = x;    //此时pop表示的是栈顶元素的下一个元素的下标 
	pst->top++;              //top表示的下标数++
}

出栈


//出栈
void STPop(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
	//top<0表示栈为空，top=0表示没有元素入栈，存在这两种情况就不能执行出栈操作（可以提供的图理解）
	assert(pst->top > 0);
 
    //直接对top执行减减操作以获取实际数组元素下标
    pst->top--;
}

获取栈顶元素


// 获取栈顶元素
STDataType STTop(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
	//top<0表示栈为空，top=0表示没有元素入栈，存在这两种情况就不能执行出栈操作（可以提供的图理解）
	assert(pst->top > 0);
	
    //当初始化top=0时，top的值与实际数组元素下标的值之间的关系是：实际下标 = top-1
    //所以这里要进行减一操作得到实际的数组元素下标后再输出
	return pst->a[pst->top - 1];
}

获取栈中有效元素个数


//获取栈中有效元素个数
int STSize(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
    
    //初始化top=0，则top等于多少栈中就有多少个元素
	return pst->top;
}

检测栈是否为空


//检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int STEmpty(ST* pst)
{
	//首先要指向一个栈
	assert(pst);
	
    //如果pst->top不为空则返回结果为真，为空则返回假
	return pst->top == NULL;
}

销毁栈


// 销毁栈
void STDestroy(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
	
    //正常操作不再过多复述
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

最终代码：

Stack.h文件：


#pragma once
#include 
#include 
#include 
 
//支持动态增长的栈
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 data);
 
// 出栈
void STPop(ST* ps);
 
// 获取栈顶元素
STDataType STTop(ST* ps);
 
// 获取栈中有效元素个数
int STSize(ST* ps);
 
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int STEmpty(ST* ps);

Stack.c文件


#include "Stack.h"
 
// 初始化栈
void STInit(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
 
	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;    //令pop表示栈顶元素的下一个元素的下标
}
 
// 销毁栈
void STDestroy(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
	
    //正常操作不再过多复述
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}
 
//入栈
void STPush(ST* pst, STDataType x)
{
    //首先要指向一个栈
	assert(pst);
    
    //判断栈是否已满，如果栈满则申请新的内存空间
	if (pst->top == pst->capacity)
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newCapacity;
	}
 
    //如果栈未满则进行入栈操作（若初始化时pop=-1，则下面两行代码交换执行顺序）
	pst->a[pst->top] = x;    //此时pop表示的是栈顶元素的下一个元素的下标 
	pst->top++;              //top表示的下标数++
}
 
//出栈
void STPop(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
	//top<0表示栈为空，top=0表示没有元素入栈，存在这两种情况就不能执行出栈操作（可以提供的图理解）
	assert(pst->top > 0);
 
    //直接对top执行减减操作以获取实际数组元素下标
    pst->top--;
}
 
// 获取栈顶元素
STDataType STTop(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
	//top<0表示栈为空，top=0表示没有元素入栈，存在这两种情况就不能执行出栈操作（可以提供的图理解）
	assert(pst->top > 0);
	
    //当初始化top=0时，top的值与实际数组元素下标的值之间的关系是：实际下标 = top-1
    //所以这里要进行减一操作得到实际的数组元素下标后再输出
	return pst->a[pst->top - 1];
}
 
//获取栈中有效元素个数
int STSize(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
    
    //初始化top=0，则top等于多少栈中就有多少个元素
	return pst->top;
}
 
//检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int STEmpty(ST* pst)
{
	//首先要指向一个栈
	assert(pst);
	
    //如果pst->top不为空则返回结果为真，为空则返回假
	return pst->top == NULL;
}

test.c文件：


#include "Stack.h"
 
int main()
{
	ST s;
    //初始化栈
	STInit(&s);
    //入栈
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
 
    //出栈
	while (!STEmpty(&s)) //只要栈不为空就一直出栈
	{
		printf("%d ", STTop(&s)); //打印每一个栈顶元素
		STPop(&s); //打印完成后就让该栈顶元素出栈
	}
 
	printf("\n");
	return 0;
}

选择练习

1. 一个栈的初始状态为空。现将元素 1 、 2 、 3 、 4 、 5 、 A 、 B 、 C 、 D 、 E 依次入栈，然后再依次出栈，则元素出栈的顺序是（）

A、 12345ABCDE

B、 EDCBA54321

C、 ABCDE12345

D、 54321EDCBA

答案：B

解析：栈中的元素遵循后进先出的原则

2. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

A、 1,4,3,2

B、 2,3,4,1

C、 3,1,4,2

D、 3,4,2,1

答案： C

解析：请自行演算🤡

栈的OJ题

20. 有效的括号 - 力扣（LeetCode）

具体解题思路如下图所示：

括号不仅仅是数量匹配，顺序也要匹配

文字解释：读取到左括号就放入栈中，读取到右括号就将其对应的左括号，如果转换后得到的的左括号与栈中存放的左括号相同（实际上比较的是ASCII码）则证明有一对儿匹配的内容括号，此时将原来栈中存放的左括号出栈，然后进行下一次的读取操作

字符串中如果第一个是右括号就直接返回假


//右括号转换为左括号
char pairs(char a) 
{
    if (a == '}') 
    {
        return '{';
    }
 
    if (a == ']')
    {
         return '[';
    }
 
    if (a == ')') 
    {
        return '(';
    }
        
    return 0;
}
 
bool isValid(char* s) 
{
    //获取数组长度
    int n = strlen(s);
 
    //如果数量不满足成对情况则直接返回flase
    if (n % 2 == 1) 
    {
        return false;
    }
 
    //stk数组用来表示存储左括号的栈（起始为空栈），top表示下一个要插入元素的位置
    int stk[n + 1], top = 0;
 
    //逐个读取原字符串中的字符并进行循环匹配
    for (int i = 0; i < n; i++) 
    {
        //读取源自符串中的内容，如果此时的字符为左括号则ch=0，为右括号则ch存储与之相对的左括号
        char ch = pairs(s[i]);
        if (ch) 
        {
            //一旦存在一对不匹配的情况则直接返回flase
            if (top == 0 || stk[top - 1] != ch) 
            {
                return false;
            }
            //如果匹配则将栈顶元素出栈（左括号出栈）
            top--;
        } 
        //如果ch为空证明此时读取的是左括号，将入栈以便下一次的判断
        else
        {
            stk[top++] = s[i];
        }
    }
 
    //如果源自符串中括号的顺序和数量均匹配，则栈中最后的结果为空，top==0的结果为真
    return top == 0;
}

~未完待续~

相关阅读:
损失函数概论（机器学习）
AspNetCore&云效Flow持续集成
 Java练习题2020-4
js-array数组-slice-splice
蓝牙数据包协议解析
 数据仓库之雪花模型
 MBps与Mbps区别
 数据分析实战│价格预测挑战【文末赠书】
浅谈JVM
CSRF 漏洞详解
原文地址：https://blog.csdn.net/m0_73975164/article/details/134464228