数据结构与算法⑧(第三章_上)栈的概念和实现(力扣：20. 有效的括号)-阿里云开发者社区

数据结构与算法⑧(第三章_上)栈的概念和实现(力扣：20. 有效的括号)

2024-05-20 207

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构与算法⑧(第三章_上)栈的概念和实现(力扣：20. 有效的括号)

一、栈（stack）

栈的概念：

① 栈是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素的操作。

② 进行数据插入的删除和操作的一端，称为栈顶。另一端则称为栈底。

③ 栈中的元素遵守后进先出的原则，即 LIFO原则（Last In First Out）。

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

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

两道栈的选择题：

1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E 依次入栈，

然后再依次出栈，则元素出栈的顺序是（）。

A 12345ABCDE

B EDCBA54321

C ABCDE12345

D 54321EDCBA

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

答案:

1.A

2.c

栈的结构：

数组栈和链式栈

实现栈无非就两种结构：数组结构和链式结构，两种结构都可以实现。

数组栈和链式栈哪种结构更好？

相对而言数组的结构实现更优，尾插尾删的效率高，缓存利用率高，它的唯一缺点只是增容，

但是增容1次扩2倍对栈来说本身就比较合理，是无伤大雅的。而链式栈虽然不会空间浪费，

用一个 malloc 申请一个，但是链式栈存在一个致命的缺点：单链表不好出数据，

必须要实现双向链表，否则尾上删除数据将会异常麻烦。

如果硬要使用链式栈：

① 如果用尾做栈顶，尾插尾删，要设计成双向链表，否则删数据效率低。

② 如果用头做栈顶，头插头删，就可以设计成单链表。

本章栈的实现将采用数组结构

二、栈的定义

（数组栈和顺序表定义差不多）

静态栈

简单介绍下静态栈：

typedef char StackDataType;
#define N 10
 
typedef struct Stack
{
    StackDataType array[N];  //数组
    int top;                 //栈顶
} Stack;

解读：N 给多了浪费给少了又不够用，所以静态栈在实际中是不实用的。静态栈满了就不能扩大了，

而动态栈是 malloc 出来的，不够了可以 realloc 扩容。虽然不实用，但是我们也得认识它，

知道有这么一个东西。

动态栈

本章将采用动态栈实现

typedef int StackDataType;
 
typedef struct Stack 
{
    StackDataType* array;  //数组
    int top;               //栈顶
    int capacity;          //容量
} Stack;

三、栈的实现（完整代码）

实现了顺序表和链表，栈的实现很简单，直接放完整代码了

Stack.h

#pragma once
 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
 
typedef int StackDataType;
 
typedef struct Stack 
{
    StackDataType* array;  //数组
    int top;               //栈顶
    int capacity;          //容量
} Stack;
 
void StackInit(Stack* ps);//初始化
void StackDestroy(Stack* ps);//销毁
void StackPush(Stack* ps, StackDataType x);//进栈
bool StackEmpty(Stack* ps);//判断栈是否为空
void StackPop(Stack* ps);// 出栈
StackDataType StackTop(Stack* ps);//返回栈顶数据
int StackSize(Stack* ps);//返回栈的大小

Stack.c

#include "Stack.h"
 
void StackInit(Stack* ps)//初始化
{
    assert(ps);
    ps->array = NULL;
    ps->top = 0;  // ps->top = -1
    ps->capacity = 0;
}
 
void StackDestroy(Stack* ps)//销毁
{
    assert(ps);
 
    free(ps->array);
    ps->array = NULL;
    ps->capacity = ps->top = 0;
}
 
void StackPush(Stack* ps, StackDataType x)//进栈
{
    assert(ps);
    if (ps->top == ps->capacity) 
    {
        int new_capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        StackDataType* tmp_arr =(StackDataType *) realloc(ps->array, sizeof(StackDataType) * new_capacity);
        if (tmp_arr == NULL) 
        {
            printf("realloc failed!\n");
            exit(-1);
        }
        // 更新
        ps->array = tmp_arr;
        ps->capacity = new_capacity;
    }
 
    ps->array[ps->top] = x;// 填入数据
    ps->top++;
}
 
bool StackEmpty(Stack* ps)//判断栈是否为空
{
    assert(ps);
 
    return ps->top == 0; //等于0就是空，就是真
}
 
void StackPop(Stack* ps)// 出栈
{
    assert(ps);
    //assert(ps->top > 0);  //防止top为空
    assert(!StackEmpty(ps));
 
    ps->top--;//--不让访问数组最后一个元素就行
}
 
StackDataType StackTop(Stack* ps)//返回栈顶数据
{
    assert(ps);
    //assert(ps->top > 0);  //防止top为空
    assert(!StackEmpty(ps));
 
    return ps->array[ps->top - 1];
}
 
int StackSize(Stack* ps) //计算栈的大小
{
    assert(ps);
 
    return ps->top;// 因为我们设定top是指向栈顶的下一个，所以top就是size
}

Test.c

#include "Stack.h"
 
void TestStack1() 
{
    Stack st;
    StackInit(&st);
    StackPush(&st, 1);
    StackPush(&st, 2);
    StackPush(&st, 3);
    StackPush(&st, 4);
    StackPush(&st, 4);
 
    StackPop(&st);
    StackPop(&st);
    StackPop(&st);
    StackPop(&st);
    //StackPop(&st);
 
    printf("%d", StackTop(&st));
    StackDestroy(&st);
}
 
void TestStack2() 
{
    // 入栈：1 2 3 4
    Stack st;
    StackInit(&st);
    StackPush(&st, 1);
    StackPush(&st, 2);
    StackPush(&st, 3);
    StackPush(&st, 4);
 
    // 出栈：4 3 2 1
    while (!StackEmpty(&st))
    {
        printf("%d ", StackTop(&st));
        StackPop(&st);
    }
    StackDestroy(&st);
}
 
void TestStack3() 
{
    // 入栈：1 2 3 4
    Stack st;
    StackInit(&st);
    StackPush(&st, 1);
    StackPush(&st, 2);
    StackPush(&st, 3);
    StackPush(&st, 4);
 
    // 提前出栈：4 3
    printf("%d ", StackTop(&st));
    StackPop(&st);
    printf("%d ", StackTop(&st));
    StackPop(&st);
 
    // 入栈：5  6
    StackPush(&st, 5);
    StackPush(&st, 6);
 
    // 出栈：6 5 2 1
    while (!StackEmpty(&st))
    {
        printf("%d ", StackTop(&st));
        StackPop(&st);
    }
    StackDestroy(&st);
}
 
int main() 
{
    //TestStack1();
    //TestStack2();
    TestStack3();
    return 0;
}

四、一道栈的OJ题：

力扣链接：20. 有效的括号

难度简单

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

bool isValid(char * s){
 
}

解析代码：

这道题用C++写就很简单，用C语言写就需要创建一个栈。（可以用数组什么的，但不好）

我们刚写了一个栈，直接把Stack.h和Stack.c复制粘贴过去,把头文件删掉，

再把typedef int StackDataType; 改成typedef char StackDataType;

typedef char StackDataType;
 
typedef struct Stack 
{
    StackDataType* array;  //数组
    int top;               //栈顶
    int capacity;          //容量
} Stack;
 
void StackInit(Stack* ps);
void StackDestroy(Stack* ps);
void StackPush(Stack* ps, StackDataType x);
bool StackEmpty(Stack* ps);
void StackPop(Stack* ps);
StackDataType StackTop(Stack* ps);
int StackSize(Stack* ps);
 
void StackInit(Stack* ps)//初始化
{
    assert(ps);
    ps->array = NULL;
    ps->top = 0;  // ps->top = -1
    ps->capacity = 0;
}
 
void StackDestroy(Stack* ps)//销毁
{
    assert(ps);
 
    free(ps->array);
    ps->array = NULL;
    ps->capacity = ps->top = 0;
}
 
void StackPush(Stack* ps, StackDataType x)//进栈
{
    assert(ps);
    if (ps->top == ps->capacity) 
    {
        int new_capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        StackDataType* tmp_arr =(StackDataType *) realloc(ps->array, sizeof(StackDataType) * new_capacity);
        if (tmp_arr == NULL) 
        {
            printf("realloc failed!\n");
            exit(-1);
        }
        // 更新
        ps->array = tmp_arr;
        ps->capacity = new_capacity;
    }
 
    ps->array[ps->top] = x;// 填入数据
    ps->top++;
}
 
bool StackEmpty(Stack* ps)//判断栈是否为空
{
    assert(ps);
 
    return ps->top == 0; //等于0就是空，就是真
}
 
void StackPop(Stack* ps)// 出栈
{
    assert(ps);
    //assert(ps->top > 0);  //防止top为空
    assert(!StackEmpty(ps));
 
    ps->top--;
}
 
StackDataType StackTop(Stack* ps)//返回栈顶数据
{
    assert(ps);
    //assert(ps->top > 0);  //防止top为空
    assert(!StackEmpty(ps));
 
    return ps->array[ps->top - 1];
}
 
int StackSize(Stack* ps) //计算栈的大小
{
    assert(ps);
 
    return ps->top;// 因为我们设定top是指向栈顶的下一个，所以top就是size
}
 
bool isValid(char* s) {
    Stack st;
    StackInit(&st);
    while (*s)
    {
        if ((*s == '(') || (*s == '[') || (*s == '{'))
        {
            StackPush(&st, *s);
        }
        else
        {
            //栈是空，且遇到右括号了，栈里面没有左括号
            if (StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }
 
            StackDataType top = StackTop(&st);
            StackPop(&st);
 
            if ((top == '(' && *s != ')')
                || (top == '[' && *s != ']')
                || (top == '{' && *s != '}'))
            {
                StackDestroy(&st);
                return false;
            }
        }
        s++;
    }
    //如果栈不是空，说明还有左括号没出完，不合题意
    //此时StackEmpty返回false，相反，栈是空，返回true
    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}

本篇完。

下一篇：队列

数据结构与算法⑧(第三章_上)栈的概念和实现(力扣：20. 有效的括号)

一、栈（stack）

栈的概念：

两道栈的选择题：

栈的结构：

二、栈的定义

静态栈

动态栈

三、栈的实现（完整代码）

Stack.h

Stack.c

Test.c

四、一道栈的OJ题：

解析代码：

本篇完。

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

数据结构与算法⑧(第三章_上)栈的概念和实现(力扣：20. 有效的括号)

一、栈（stack）

栈的概念：

两道栈的选择题：

栈的结构：

二、栈的定义

静态栈

动态栈

三、栈的实现（完整代码）

Stack.h

Stack.c

Test.c

四、一道栈的OJ题：

解析代码：

本篇完。

热门文章

最新文章

相关课程

相关电子书