「数据结构」栈

前言

目录

前言

栈的概念

栈的实现

1.实现方式选择

2.所需实现的函数列举(头文件)

3.实现栈的函数

初始化和销毁

入栈和出栈

获取栈顶元素、元素个数、栈判空

栈的OJ练习题讲解：

完整数据结构栈的代码：

后记

---

欢迎各位小伙伴来到小鸥的博客！让我们继续一起学习成长吧！

本篇专栏：数据结构_海盗猫鸥的博客-CSDN博客

欢迎大家到访，有任何意见想法店都可以评论或者私聊喔！

本期我们将继续数据结构的学习，有请本次“嘉宾”——栈！

栈的概念

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

入栈出栈图示：

栈的实现

1.实现方式选择

栈可以基于数组或者链表来实现，一般而言用用数组来实现更优，因为数组在尾部插入数据时的代价小一些

如果使用单链表结构来实现栈的话，就要将头节点作为栈顶，因为单链表的头插和头删的消耗更小，尾删和尾插都需要遍历链表才能进行。双链表则不需要在意这点。

（即便使用双链表来实现栈，节点至少也需要三个成员，耗费依然大于数组）

所以我们本篇采取使用动态顺序表的方式来实现栈。

2.所需实现的函数列举(头文件)

类比之前我们已经学习过的顺序表和链表

我们可以先得出一些需要的函数（接口）：

入栈（插入数据）、出栈（删除数据）、初始化、销毁；

此外栈还需要：获取栈顶元素的函数、有效元素个数的函数、检测栈是否为空的函数。

所以我们可以先在头文件中声明所有的函数：

Stack.h

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

typedef int STDATATYPE;
typedef struct Stakc
{
	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);

//获取栈顶元素
STDATATYPE STTop(ST* pst);
//获取栈中的有效元素个数
int STSize(ST* pst);
//检测是否为空
bool STEmpty(ST* pst);

注意：

上文代码中结构体虽然和实现顺序表时的结构体十分相似，但也要注意区分，这里的top初始赋值为0时，代表的是栈顶元素的下一个位置，而不是栈顶元素的位置；而在顺序表中size代表的就是有效的元素个数，两者意义不同。

3.实现栈的函数

初始化和销毁

代码实现：

//初始化销毁
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}
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;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

注意：

1.入栈的原理和顺序表的插入数据十分相似，动态扩容时，先判断内存是否够用，不够用时再以二倍的方式开辟空间，若空间一开始为0，则以4个元素的大小空间为起始。

2.出栈操作只需要将top往前移动即可，访问不到就是删除。

获取栈顶元素、元素个数、栈判空

代码实现：

//获取栈顶元素
STDATATYPE STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top - 1];
}
//获取栈中的有效元素个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}
//检测是否为空
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}

注意：

1.返回栈顶元素需要判断栈是否为空；

2.计算元素个数的函数中，top虽然代表的是栈顶元素的下一个位置的下标，但其数值和顺序表中表示元素有效个数的size相等，所以直接返回top的数值即可；

3.判空函数，为空时返回true，不为空返回false。

栈的OJ练习题讲解：

有效的括号 - 力扣（LeetCode）

栈解题的思路：

使用栈来匹配括号：

1. 如果为左括号就进栈；
2. 如果为右括号，取出栈顶元素与其匹配
   1. 若匹配成功就将该栈顶元素出栈，继续比较下一个；
   2. 若匹配不成功就直接返回false。
3. 字符串循环匹配处理结束后进行判空：
   1. 若栈为空，则说明括全部匹配成功，返回true；
   2. 若栈不为空，则说明有未匹配的括号，返回false。

代码中附有注释，结合注释理解方法；

代码实现：

bool isValid(char* s) {
    ST stack;
    STInit(&stack);
    while(*s)// \0 时跳出循环
    {
        //判断括号类型
        //左括号
        if(*s == '(' || *s == '[' || *s == '{')
        {
            STPush(&stack,*s);
        }
        //右括号
        else
        {
            //第一个括号就是右括号，直接返回false
            if(STEmpty(&stack))
            {
                STDestroy(&stack);
                return false;
            }
            //获取栈顶元素
            STDATATYPE top = STTop(&stack);
            //栈顶元素出栈
            STPop(&stack);
            //配对取出的栈顶元素和当前括号
            if((top == '(' && *s != ')')
            || (top == '[' && *s != ']')
            || (top == '{' && *s != '}'))
            {
                //配对不成功，返回false
                STDestroy(&stack);
                return false;
            }
        }
        s++;
    }
    //判断循环结束后栈是否为空格
    //为空说明所有口括号都配对成功，反之说明有括号没有匹配成功
    bool ret = STEmpty(&stack);
    STDestroy(&stack);
    return ret;
}

注意：

由于该题本次我们是使用C语言实现的，栈这个数据结构需要我们自己准备，所以在使用C语言解答本题时，要在前面加入我们上文写的实现栈的代码。

完整数据结构栈的代码：

头文件：上文已经给出；

.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);
	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;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

//获取栈顶元素
STDATATYPE STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top - 1];
}
//获取栈中的有效元素个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}
//检测是否为空
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}

后记

本次我们又一起认识了栈这个数据结构，看完的小伙伴一定发现了，其实栈的实现在我们有了顺序表和链表的学习经验后，实现起来是比较简单的。

那么本篇就到这里，我们下期再见~