• 数据结构——栈

    我们接着链表来讲，今天来聊聊栈和队列

    文章目录

    栈的概念以及结构

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

    注意：我们这里讲的栈是数据结构的栈，与操作系统中函数栈帧的栈是两个完全不同的概念

    下面引用一张图片：
    在这里插入图片描述
    这张图片很好的向我们诠释了栈的基本流程
    入栈数据可以一次入一个，也可以一次入多个，一定要具体分析，大家不要踩坑了

    栈的实现

    Stack.h头文件

    1、需要包含的头文件

    值得一提的是布尔值是c99中新加的C语言语法，使用布尔值要引用头文件stdbool.h

    #include
#include
#include
#include//C语言使用布尔值要引用该头文件

    • 1
    • 2
    • 3
    • 4

    2、结构体的定义

    老规矩，还是将int类型重定义，这样在进行其他数据类型操作的时候只需要修改int即可
    与顺序表一样，栈也有静态和动态的区别，这里我们采用动态实现

    //#define max 100
//typedef struct Stack
//{
//	TDataType data[max];
//	int top;//有效数据个数
//}ST;   静态栈
typedef int TDataType;

typedef struct Stack
{
	TDataType* data;
	int top;//有效数据个数
	int capacity;//容量
}ST;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    3、函数的声明

    void StackInit(ST* ps);//初始化
void StackDestory(ST* ps);//释放空间
void StackPush(ST* ps, TDataType x);//入栈
void StackPop(ST* ps);//出栈
TDataType StackTop(ST* ps);//栈顶元素
bool StacEmpty(ST* ps);//判断栈是否为空
size_t StackSize(ST* ps);//查看栈里面有剩多少个元素

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    这里小编就实现了这么些接口，大家可以试着写一些新接口

    Stack.c源文件

    接下来就是每个函数的定义了

    1、初始化

    void StackInit(ST* ps)//初始化
{
	assert(ps);
	ps->data = NULL;//将data置空
	ps->top = ps->capacity = 0;//让有效数据个数和容量都为0，让top从0开始
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    这里top初始化为0是有讲究的，具体有什么作用我们等下就知道了

    2、释放空间

    void StackDestory(ST* ps)//释放空间
{
	assert(ps);
	free(ps->data);//数组是连续开辟的，释放应该一次性释放完
	ps->data = NULL;
	ps->top = ps->capacity = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    3、入栈数据

    这里就要提到为什么上面要初始化top为0了
    在这里插入图片描述
    所以我们需要考虑是初始化为0还是-1了
    各有各的好，这里小编初始化的是0，大家可以试一试初始化为-1的情况

    同时，入栈是需要判断空间是否扩容的，栈也只有入栈数据要不要考虑扩容，其他地方不需要。
    所以扩容不用像前面的链表，顺序表写一个单独函数出来

    void StackPush(ST* ps, TDataType x)//入栈
{
	assert(ps);
	if (ps->top == ps->capacity)//如果入栈数据个数等于容量就扩容
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//第一次直接扩容出4个数据空间，往后每次扩容原来容量的2倍
		TDataType* newnode = (TDataType*)realloc(ps->data, newcapacity*sizeof(TDataType));//进行扩容
		if (newnode == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->data = newnode;//将扩容地址交给原来内存指针维护
		ps->capacity = newcapacity;//将新容量赋值给capacity
	}
	ps->data[ps->top] = x;//入栈我们需要的数据
	ps->top++;//top的位置向后面移动一步
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    4、出栈数据（删除）

    直接弹出栈顶的数据，因为栈是后进先出的

    void StackPop(ST* ps)//出栈
{
	assert(ps);
	assert(!StacEmpty(ps));//如果栈为空，断言生效
	ps->top--;//直接减减，弹出栈顶的数据
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    5、取出栈顶数据

    TDataType StackTop(ST* ps)//栈顶数据
{
	assert(ps);
	return ps->data[ps->top - 1];//因为初始化为0，所以top处于栈顶位置的下一个位置，减1才是栈顶数据
}

    • 1
    • 2
    • 3
    • 4
    • 5

    6、判断栈是否为空

    bool StacEmpty(ST* ps)//判断栈是否为空
{
	assert(ps);
	return ps->top == 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5

    7、查看栈有多少个数据

    

size_t StackSize(ST* ps)//栈还剩下多少元素
{
	assert(ps);
	return ps->top;//top是多少就有多少个数据
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    完整代码

    Stack.h

    #pragma once
#include
#include
#include
#include//C语言使用布尔值要引用该头文件

//#define max 100
//typedef struct Stack
//{
//	TDataType data[max];
//	int top;//有效数据个数
//}ST;   静态栈

typedef int TDataType;

typedef struct Stack
{
	TDataType* data;
	int top;//有效数据个数
	int capacity;//容量
}ST;

void StackInit(ST* ps);//初始化
void StackDestory(ST* ps);//释放空间
void StackPush(ST* ps, TDataType x);//入栈
void StackPop(ST* ps);//出栈
TDataType StackTop(ST* ps);//栈顶元素
bool StacEmpty(ST* ps);//判断栈是否为空
size_t StackSize(ST* ps);//查看栈里面有剩多少个元素

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    Stack.c

    #define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"
void StackInit(ST* ps)//初始化
{
	assert(ps);
	ps->data = NULL;//将data置空
	ps->top = ps->capacity = 0;//让有效数据个数和容量都为0，让top从0开始
}


void StackDestory(ST* ps)//释放空间
{
	assert(ps);
	free(ps->data);//数组是连续开辟的，释放应该一次性释放完
	ps->data = NULL;
	ps->top = ps->capacity = 0;
}


void StackPush(ST* ps, TDataType x)//入栈
{
	assert(ps);
	if (ps->top == ps->capacity)//如果入栈数据个数等于容量就扩容
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//第一次直接扩容出4个数据空间，往后每次扩容原来容量的2倍
		TDataType* newnode = (TDataType*)realloc(ps->data, newcapacity*sizeof(TDataType));//进行扩容
		if (newnode == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->data = newnode;//将扩容地址交给原来内存指针维护
		ps->capacity = newcapacity;//将新容量赋值给capacity
	}
	ps->data[ps->top] = x;//入栈我们需要的数据
	ps->top++;//top的位置向后面移动一步
}


void StackPop(ST* ps)//出栈
{
	assert(ps);
	assert(!StacEmpty(ps));//如果栈为空，断言生效
	ps->top--;//直接减减，弹出栈顶的数据
}


TDataType StackTop(ST* ps)//栈顶数据
{
	assert(ps);
	return ps->data[ps->top - 1];//因为初始化为0，所以top处于栈顶位置的下一个位置，减1才是栈顶数据
}


bool StacEmpty(ST* ps)//判断栈是否为空
{
	assert(ps);
	return ps->top == 0;
}


size_t StackSize(ST* ps)//栈还剩下多少元素
{
	assert(ps);
	return ps->top;//top是多少就有多少个数据
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66

    test.c

    #define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"
//void Test1()
//{
//	ST p;
//	StackInit(&p);
//
//	StackPush(&p, 1);
//	StackPush(&p, 2);
//	StackPush(&p, 3);
//	StackPush(&p, 4);
//	StackPush(&p, 5);
//	while (!StacEmpty(&p))
//	{
//		printf("%d ", StackTop(&p));
//		StackPop(&p);
//	}
//	printf("\n");
//	printf("%zd\n", StackSize(&p));
//	StackDestory(&p);
//}
void menu()
{
	printf("-------------------------------\n");
	printf("***1、入栈数据   2、出栈数据***\n");
	printf("*******3、查看栈数据个数*******\n");
	printf("*******4、判断栈是否为空*******\n");
	printf("*******5、打印栈顶处数据*******\n");
	printf("******6、出栈打印所有数据******\n");
	printf("*******************************\n");
	printf("-------------------------------\n");
}
int main()
{
	//Test1();
	ST p;
	StackInit(&p);
	int n = 0;
	int x = 0;
	int y = 0;
	do
	{
		menu();
		printf("请选择操作:");
		scanf("%d", &n);
		switch (n)
		{
		case 1:
			printf("请输入入栈数据，以-1截止\n");
			do
			{
				scanf("%d", &x);
				//StackPush(&p, x);//入栈函数接口在上面会将-1一起入栈
				if (x == -1)
				{
					break;
				}
				StackPush(&p, x);//入栈函数接口在下面不会将-1一起入栈
			} while (x != -1);
			break;
		case 2:
			StackPop(&p);
			break;
		case 3:
			printf("%zd\n", StackSize(&p));
			break;
		case 4:
			if (StacEmpty(&p))
				printf("没有数据，栈为空\n");
			else
				printf("有数据，栈不为空\n");
			break;
		case 5:
			printf("%d\n", StackTop(&p));
			break;
		case 6:
			while (StackSize(&p))
			{
				printf("%d ", StackTop(&p));
				StackPop(&p);
			}
			printf("\n");
			break;
		case 0:
			StackDestory(&p);
			printf("退出程序\n");
			break;
		default :
			printf("选择错误，请重新选择\n");
			break;
		}
	} while (n);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94

    栈的OJ题

    OJ练习题

    给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

    有效字符串需满足：

    1、 左括号必须用相同类型的右括号闭合。
    2、左括号必须以正确的顺序闭合。

    在这里插入图片描述
    我已经将这个题注意点标出来了，括号就3种，括号顺序很重要，不能直接数括号

    接下来我们来解决：

    typedef int TDataType;
typedef struct Stack
{
	TDataType* data;
	int top;//有效数据个数
	int capacity;//容量
}ST;
void StackInit(ST* ps);//初始化
void StackDestory(ST* ps);//释放空间
void StackPush(ST* ps, TDataType x);//入栈
void StackPop(ST* ps);//出栈
TDataType StackTop(ST* ps);//栈顶元素
bool StacEmpty(ST* ps);//判断栈是否为空
size_t StackSize(ST* ps);//查看栈里面有剩多少个元素

void StackInit(ST* ps)//初始化
{
	assert(ps);
	ps->data = NULL;//将data置空
	ps->top = ps->capacity = 0;//让有效数据个数和容量都为0，让top从0开始
}
void StackDestory(ST* ps)//释放空间
{
	assert(ps);
	free(ps->data);//数组是连续开辟的，释放应该一次性释放完
	ps->data = NULL;
	ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, TDataType x)//入栈
{
	assert(ps);
	if (ps->top == ps->capacity)//如果入栈数据个数等于容量就扩容
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//第一次直接扩容出4个数据空间，往后每次扩容原来容量的2倍
		TDataType* newnode = (TDataType*)realloc(ps->data, newcapacity*sizeof(TDataType));//进行扩容
		if (newnode == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->data = newnode;//将扩容地址交给原来内存指针维护
		ps->capacity = newcapacity;//将新容量赋值给capacity
	}
	ps->data[ps->top] = x;//入栈我们需要的数据
	ps->top++;//top的位置向后面移动一步
}
void StackPop(ST* ps)//出栈
{
	assert(ps);
	assert(!StacEmpty(ps));//如果栈为空，断言生效
	ps->top--;//直接减减，弹出栈顶的数据
}
TDataType StackTop(ST* ps)//栈顶数据
{
	assert(ps);
	return ps->data[ps->top - 1];//因为初始化为0，所以top处于栈顶位置的下一个位置，减1才是栈顶数据
}
bool StacEmpty(ST* ps)//判断栈是否为空
{
	assert(ps);
	return ps->top == 0;
}
size_t StackSize(ST* ps)//栈还剩下多少元素
{
	assert(ps);
	return ps->top;//top是多少就有多少个数据
}

bool isValid(char * s){
    ST p;
    StackInit(&p);//初始化
    while(*s!='\0')
    {
        if(*s=='(' || *s=='[' || *s=='{')
        {
            StackPush(&p,*s);//如果是左括号都入栈
        }
        else
        {
            if(StacEmpty(&p))//如果全是右括号，那么没有数据入栈，栈就为空，直接返回false即可
            {
                StackDestory(&p);//返回记得释放动态内存
                return false;
            }
            char ch=StackTop(&p);//拿到栈顶数据
            StackPop(&p);//删除/弹出栈顶数据
            if((*s==')' && ch!='(')
             ||(*s==']' && ch!='[')
             ||(*s=='}' && ch!='{'))//当来到这里时，指针s已经走到第一个右括号了，此时栈里面放的都是左括号，ch就是栈顶的符号（也就是最后最后一个左括号），这里拿到之后弹出了栈顶符号（就是下一次的ch变成了倒数第二个左括号，以此类推）。然后进行匹配，如果左右括号对应上了就进行下一步++s，如果不对应就说明字符串左右括号不匹配，直接false
             {
                 StackDestory(&p);//返回记得释放动态内存
                 return false;
             }
        }
        ++s;//指针向后移动一位
    }
    bool flag=StacEmpty(&p);//这里之所以用一个布尔型的flag是因为如果入的都是左括号，直接会跳出循环来到这里，那么就直接打印结果了。这里判断一下如果都是左括号那么栈不为空，就是一个假值，flag的值就为就是false
    StackDestory(&p);//返回记得释放动态内存
    return flag;//返回flag，不能直接返回true，因为都是左括号直接跳出循环来这返回了
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100

    在这里插入图片描述

  • 相关阅读:
    【老生谈算法】matlab实现数字图像复原算法源码——数字图像复原算法
    浏览器标签上添加icon图标；html引用ico文件
    【Java 快速复习】垃圾回收算法 & 垃圾回收器
    计算机基础 操作系统1
    对比两个数组中 每个对应位置的元素大小 返回每个对比结果组成的列表 numpy.fmin()
    小样本相关论文复现—2-全局印象
    LeetCode 周赛笔记 —— 2022年8月 第一周
    SpringBoot+Vue项目在线学习网站
    LeetCode 0304. 二维区域和检索 - 矩阵不可变
    从B-21轰炸机看美空军作战战略趋势
  • 原文地址：https://blog.csdn.net/kdjjdjdjjejje128/article/details/126161409