数据结构—栈（C语言实现）

文章目录

前言
一、栈的概念
二、栈的代码实现
- Stack.h
- Stack.c
- 三、使用栈解决有效的括号问题
- 总结
  
  前言
  
  小伙伴们，大家好哇！！欢迎来到我的博客！
  今天来分享一下另外一种数据结构—栈。主要包括栈的基本概念与其代码实现，最后使用该数据结构巧妙地解决一道算法题。
  
  一、栈的概念
  
  栈（stack）是一种特殊的线性表，它只允许从一段插入删除数据，进行插入删除操作的一端称为栈顶，另一端则称之为栈底。所以栈中的数据始终遵从先进后出 LINO（Last In First Out）的原则。
  
  看到这小伙伴们可能会联想到一些日常生活中的例子，比如一包抽纸，我们每次抽出的纸肯定是最顶部一张，逐渐往下抽，直到抽到底，这里的顶部便相当于栈顶，而底部则相当于栈底。而且在纸巾实际放入包装袋中也是从底部开始放进去的。
  又比如一个装了东西的箱子，我们要取出其中的物品，肯定是要从最上面的东西开始拿出（当然也不排除有些人将箱子里的东西全部暴力地倒出），直到找到自己要找的。
  而像前面的插入数据的操作就叫压栈，也可以叫入栈或进栈，删除数据的操作则是出栈，在栈中插入与删除数据的位置都是栈顶。
  
  二、栈的代码实现
  
  讲完了栈的基本概念与思想，那么就又到了紧张刺激手撕代码的时间了。
  但在实现栈之前，我们应思考一下应使用数组还是链表实现：
  其实，栈一般既可以使用数组也可以使用链表实现。但相对而言，使用数组结构实现更优。因为数组在尾部插入数据的代价更小。
  
  那么接下来就让我们使用数组来手搓一个栈吧！！
  
  Stack.h
  
  首先是栈的结构体声明，与之前的顺序表【数据结构—顺序表（C语言实现）】类似的是，我们当然可以使用静态栈的结构，即在声明是确定数组的长度，但这种栈在实际中并不实用：
```
typedef int STDataType;
#define N 10
typedef struct Stack
{ STDataType _a[N];
 int _top; // 栈顶
}Stack;
```
  所以我们依然是要实现可以支持动态增长的栈：
```
typedef int STDataType;
typedef struct Stack
{STDataType* a;
	int top;
	int capacity;
}ST;
```
  然后是头文件包含与栈的结构体声明（top指向栈顶元素）：
```
#pragma once
#include #include 
#include #include typedef int STDataType;
typedef struct Stack
{STDataType* a;
	int top;
	int capacity;
}ST;
```
  最后是栈的基本方法的声明：
```
//初始化、销毁栈
void STInit(ST* pst);
void STDestroy(ST* pst);
//入栈、出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
//判空
bool STEmpty(ST* pst);
//获取栈顶元素
STDataType STTop(ST* pst);
//获取栈有效元素个数
int STSize(ST* pst);
```
  Stack.c
  
  接下来就是栈的增删查改的基本方法的实现了！
  首先最为基本的当然是栈的头文件包含了：
```
#include "Stack.h"
```
  然后是栈的初始化与销毁：
```
void STInit(ST* pst)
{assert(pst);
	
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}
void STDestroy(ST* pst)
{assert(pst && pst->capacity);
	
	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, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{perror("realloc fail!");
			exit(1);
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
```
  使用动画解释入栈操作：
  出栈，这就非常简单了！只需要将栈的size–即可：
```
void STPop(ST* pst)
{assert(pst && pst->top);
	pst->top--;
}
```
  动画解释出栈操作（由于只是将size–，实际上栈中的数据并没有消失）：
  最后就是栈的判空，获取栈顶数据，获取栈的数据大小（这里就很简单了，基本一行代码即可解决）：
```
bool STEmpty(ST* pst)
{assert(pst);
	return pst->top == 0;
}
STDataType STTop(ST* pst)
{assert(pst && pst->top);
	return pst->a[pst->top - 1];
}
int STSize(ST* pst)
{assert(pst);
	
	return pst->top;
}
```
  三、使用栈解决有效的括号问题
  
  讲完了栈的数据结构，接下来我们就可以使用栈的特性来巧妙地解决一道力扣上的算法题，附上题目链接：有效的括号。
  由题意可知与我们日常学习可知：只有最近的两括号是同种（比如都是花括号：{}），并且前一个是左括号而后一个是右括号才能称之为有效的括号。
  
  此时就是栈这一数据结构的回合了：我们可以先判断第一个字符是否为左括号，是就直接让该括号入栈；然后判断下一个字符，是左括号就入栈，不是则说明是右括号，这时就需要判断这个右括号与栈顶的括号是否匹配，匹配就让栈顶出栈，否则就直接返回false。但在判断第一个字符时是可能就为右括号的，此时我们就需要在判断括号是否匹配之前对栈进行判空操作，并返回false。而这些出栈与入栈的操作肯定是需要放到一个循环中的。
  然后在出了循环我们就只需要判断此时栈中是否为空即可，为空就说明所有的括号都匹配。
  
  接下来就是关于这道题的代码实现了。由于我们使用的是C语言解决，我们肯定需要在首先主逻辑之前手搓一个栈。但是如果我们已经在编译器中实现了一个栈，那我们就可以直接使用CV大法，10秒内完成！！（当然没有实现过栈的小伙伴最好在做这题前手撕一个栈，有助于对栈的理解）
  
  以下是题中的主要逻辑部分的代码（当然在这之前肯定得包含栈的实现代码）：
```
bool isValid(char* s) { ST st;
    STInit(&st);
    while (*s)
    { if (*s == '(' || *s == '[' || *s == '{') 
            STPush(&st, *s);
        else
        { if (STEmpty(&st))
            { STDestroy(&st);
                return false;
            }
            if (STTop(&st) == '(' && *s != ')' ||
                STTop(&st) == '[' && *s != ']' ||
                STTop(&st) == '{' && *s != '}')
            { STDestroy(&st);
                return false;
            }
            STPop(&st);
        }
        s++;
    }
    bool ret = STEmpty(&st);
    STDestroy(&st);
    return ret;
}
```
  总结
  
  以上就是有关栈这一数据结构的问题分享，如果觉得对你有帮助的话，希望小伙伴们可以点点“栈”（赞）！！
  ☆*: .｡. o(≧▽≦)o .｡.:*☆

括号 在这里

相关推荐

【数据结构】考点十五：广义表的表头和表尾2024.06.29
clang-format最全配置注释2024.06.26
Educational Codeforces Round 166 (Rated for Div. 2) (C、D）2024.06.25
数据结构之探索“栈”的奥秘2024.06.21
前端Prettier 插件的使用配置(详细)2024.06.21

