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

简介: 数据结构与算法⑧(第三章_上)栈的概念和实现(力扣: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. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 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;
}


本篇完。

下一篇:队列


目录
相关文章
|
22小时前
|
算法
【C/数据结构和算法】:栈和队列
【C/数据结构和算法】:栈和队列
6 1
|
3天前
|
缓存 调度
栈和队列的区别
栈和队列的区别
6 0
|
4天前
|
算法 Java 编译器
Java数据结构与算法:线性数据结构之栈
Java数据结构与算法:线性数据结构之栈
|
4天前
|
存储 程序员 编译器
堆和栈的区别
堆和栈的区别
|
5天前
|
C++
【洛谷 P1739】表达式括号匹配 题解(栈)
该编程题目要求检查给定的包含字母、运算符和括号的表达式是否括号匹配。输入为一行表达式,以`@`结束。如果括号匹配,输出`YES`,否则输出`NO`。样例包括一个匹配和一个不匹配的表达式。解决方案是使用栈,遇到左括号入栈,遇到右括号时判断栈是否为空,栈空则输出`NO`,否则出栈。当读到`@`时,栈空则输出`YES`,否则输出`NO`。提供的AC代码使用C++实现,通过`stack`处理括号匹配。
7 0
|
10天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
10天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
11天前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
11天前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
11天前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词