数据结构—栈（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;
1
2
3
4
5
6
7

所以我们依然是要实现可以支持动态增长的栈：

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
1
2
3
4
5
6
7
8

然后是头文件包含与栈的结构体声明（top指向栈顶元素）：

#pragma once

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

最后是栈的基本方法的声明：

//初始化、销毁栈
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);
1
2
3
4
5
6
7
8
9
10
11
12

Stack.c

接下来就是栈的增删查改的基本方法的实现了！
首先最为基本的当然是栈的头文件包含了：

#include "Stack.h"
1

然后是栈的初始化与销毁：

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

入栈，这里我们使用与之前顺序表相同的方法对栈进行扩容：

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++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

使用动画解释入栈操作：

出栈，这就非常简单了！只需要将栈的size–即可：

void STPop(ST* pst)
{
	assert(pst && pst->top);

	pst->top--;
}
1
2
3
4
5
6

动画解释出栈操作（由于只是将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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

三、使用栈解决有效的括号问题

讲完了栈的数据结构，接下来我们就可以使用栈的特性来巧妙地解决一道力扣上的算法题，附上题目链接：有效的括号。

由题意可知与我们日常学习可知：只有最近的两括号是同种（比如都是花括号：{}），并且前一个是左括号而后一个是右括号才能称之为有效的括号。

此时就是栈这一数据结构的回合了：我们可以先判断第一个字符是否为左括号，是就直接让该括号入栈；然后判断下一个字符，是左括号就入栈，不是则说明是右括号，这时就需要判断这个右括号与栈顶的括号是否匹配，匹配就让栈顶出栈，否则就直接返回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;
}
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

总结

以上就是有关栈这一数据结构的问题分享，如果觉得对你有帮助的话，希望小伙伴们可以点点“栈”（赞）！！
☆*: .｡. o(≧▽≦)o .｡.:*☆