C语言数据结构——详细讲解《栈》

🕗 发布于 2024-11-27 10:55 c语言 数据结构 开发语言 链表算法

C语言数据结构——详细讲解《栈》

前言
一、栈的概念
二、栈的定义
三、栈的操作
四、栈的例题
五、本文的所有代码

前言

在 C 语言编程中，数据结构是非常重要的一部分，它能够帮助我们更高效地组织和处理数据。
今天，我们就来详细讲解一下其中的栈数据结构。

一、栈的概念

“栈” 在计算机中是一种数据结构，是一种特殊的线性表，
它只允许在固定的一端进行插入和删除元素操作
进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

在这里插入图片描述

栈中的数据元素遵守后进先出的原则

在这里插入图片描述

压栈（进栈、入栈）：栈的插入操作叫做进栈（压栈、入栈），入数据在栈顶
出栈：栈的删除操作叫做出栈，出数据也在栈顶

二、栈的定义

栈的结构通常由一个数组或链表来实现。
在数组实现中，栈顶通常由一个变量来指向，这个变量记录了栈顶元素的索引。每次入栈操作会增加这个索引，每次出栈操作会减小这个索引。
在链表实现中，栈顶是链表的头节点，入栈操作相当于在链表头部插入一个新节点，出栈操作相当于删除链表的头节点。

下面我们来详细讲一下栈的链式结构

首先，我们要定义栈的数据结构

typedef struct Stack 
{
    int* arr;
    int top;
    int capacity;
} Stack;

arr指栈中的元素
top指栈顶
capacity表示栈的容量

三、栈的操作

1.初始化栈

有了栈的结构体定义，我们需要对栈进行初始化

void initStack(Stack* ps) 
{
    ps->capacity = 4;
    ps->top = 0;
    ps->arr = (int*)malloc(ps->capacity * sizeof(int));
    assert(ps->arr!= NULL);
}

首先，把栈的初始容量设置为 4
然后，将栈顶top设置为 0，表示此时栈是空的
接着，使用malloc函数来动态分配内存，以便能够存储栈的元素

2. 入栈操作

栈初始化好了之后，接下来就往栈里放元素

void push(Stack* ps, int x) {
    if (ps->top == ps->capacity) 
    {
        // 栈满，扩容
        int newCapacity = ps->capacity == 0? 4 : 2 * ps->capacity;
        int* tmp = (int*)realloc(ps->arr, newCapacity * sizeof(int));
        if (tmp == NULL) {
            perror("realloc fail\n");
            exit(1);
        }
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
    ps->arr[ps->top++] = x;
}

这个函数就是用来把一个元素x压入栈中的

首先，检查一下栈是否已满了 ps->top == ps->capacity
如果栈满了，就得进行扩容操作

int newCapacity = ps->capacity == 0? 4 : 2 * ps->capacity;

如果当前栈的容量是 0 ，就把新容量设为 4；要是当前容量不为 0，就是当前容量的两倍

int* tmp = (int*)realloc(ps->arr, newCapacity * sizeof(int));

然后使用realloc函数来重新分配内存

最后，把元素x放到arr[top]这个位置上，然后再把top加 1，这样就表示栈顶元素的位置更新

3. 出栈操作

int pop(Stack* ps) 
{
    assert(ps->top > 0);
    return ps->arr[--ps->top];
}

把top减 1，再返回arr[top]的值，这个值就是栈顶元素

4. 获取栈顶元素

int top(Stack* ps) 
{
    assert(ps->top > 0);
    return ps->arr[ps->top - 1];
}

如果栈不为空，那就返回arr[top - 1]的值，这个值就是栈顶元素的值

5. 检查栈是否为空

int isEmpty(Stack* ps) 
{
    return ps->top == 0;
}

如果top等于 0，那就说明栈是空的，这时候函数就会返回 1；要是top不等于 0，那就说明栈里还有元素，函数就会返回 0

6.释放栈内存

void freeStack(Stack* ps) 
{
    free(ps->arr);
    ps->arr = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

以上便是栈的全部操作，下面给大家带来一道栈的例题，应用一下所学的知识

四、栈的例题

在这里插入图片描述
链接地址》》》》》》有效括号

大家先思考一下怎么做

题目讲解
思路，将左括号看为入栈，右括号看为出栈

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

// 定义栈的数据结构
typedef struct Stack {
    int* arr;
    int top;
    int capacity;
} Stack;

// 初始化栈
void initStack(Stack* ps) {
    ps->capacity = 4;
    ps->top = 0;
    ps->arr = (int*)malloc(ps->capacity * sizeof(int));
    assert(ps->arr!= NULL);
}

// 入栈操作
void push(Stack* ps, int x) {
    if (ps->top == ps->capacity) {
        // 栈满，扩容
        int newCapacity = ps->capacity == 0? 4 : 2 * ps->capacity;
        int* tmp = (int*)realloc(ps->arr, newCapacity * sizeof(int));
        if (tmp == NULL) {
            perror("realloc fail\n");
            exit(1);
        }
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
    ps->arr[ps->top++] = x;
}

// 出栈操作
int pop(Stack* ps) {
    assert(ps->top > 0);
    return ps->arr[--ps->top];
}

// 获取栈顶元素
int top(Stack* ps) {
    assert(ps->top > 0);
    return ps->arr[ps->top - 1];
}

// 检查栈是否为空
int isEmpty(Stack* ps) {
    return ps->top == 0;
}

// 释放栈内存
void freeStack(Stack* ps) {
    free(ps->arr);
    ps->arr = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

bool isValid(char* s) {
    Stack st;
    initStack(&st);
    char* pi = s;
    while (*pi!= '\0') {
        if (*pi == '(' || *pi == '{' || *pi == '[') {
            // 入栈
            push(&st, *pi);
        } else {
            // 判断，取栈
            if (isEmpty(&st)) {
                freeStack(&st);
                return false;
            }
            char top = (char)pop(&st);
            if ((top == '(' && *pi!= ')') || (top == '[' && *pi!= ']') || (top == '{' && *pi!= '}')) {
                freeStack(&st);
                return false;
            }
        }
        pi++;
    }
    bool ret = isEmpty(&st);
    freeStack(&st);
    return ret;
}

下面详细讲解一下，对比上面代码增加的部分

bool isValid(char* s) {
    Stack st;//定义了一个名为st的Stack类型的变量,用于辅助判断括号的有效性
    initStack(&st);//调用initStack函数对栈st进行初始化
    char* pi = s;
    while (*pi!= '\0') {
        if (*pi == '(' || *pi == '{' || *pi == '[') {
            // 入栈
            push(&st, *pi);
        } else {
            // 判断，取栈
            if (isEmpty(&st)) {
                freeStack(&st);
                return false;
            }
            char top = (char)pop(&st);
            if ((top == '(' && *pi!= ')') || (top == '[' && *pi!= ']') || (top == '{' && *pi!= '}')) {
                freeStack(&st);
                return false;
            }
        }
        pi++;
    }
    bool ret = isEmpty(&st);
    freeStack(&st);
    return ret;
}

首先定义了一个字符指针pi，并将其初始化为指向传入的字符串s的首地址。这个指针将用于遍历字符串s。
接着循环遍历栈中的元素
如果等于左括号则入栈
然后调用push函数将该左括号字符压入栈st中
如果pi所指向的字符不是左括号
首先检查栈st是否为空。
如果栈不为空，调用pop函数从栈st中弹出栈顶元素，并将其转换为char类型后赋值给变量top
如果不匹配，则调用freeStack函数释放栈的内存

bool ret = isEmpty(&st);
当遍历完整个字符串s后，检查栈st是否为空。如果栈为空，说明所有的左括号都找到了对应的右括号，将true赋值给ret；否则，将false赋值给ret

最后返回ret的值

五、本文的所有代码

Stack.c

#include "Stack.h"
int main() {
    Stack myStack;
    initStack(&myStack);

    // 入栈几个数据实例
    push(&myStack, 10);
    push(&myStack, 20);
    push(&myStack, 30);

    // 获取栈顶元素并打印
    printf("当前栈顶元素: %d\n", top(&myStack));

    // 出栈操作并打印出栈元素
    printf("出栈元素: %d\n", pop(&myStack));

    // 再次获取栈顶元素并打印
    printf("当前栈顶元素: %d\n", top(&myStack));

    // 检查栈是否为空并打印结果
    if (isEmpty(&myStack)) {
        printf("栈为空\n");
    }
    else {
        printf("栈不为空\n");
    }

    // 释放栈内存
    freeStack(&myStack);

    return 0;
}

Stack,h

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

// 定义栈的数据结构
typedef struct Stack {
    int* arr;
    int top;
    int capacity;
} Stack;

// 初始化栈
void initStack(Stack* ps) {
    ps->capacity = 4;
    ps->top = 0;
    ps->arr = (int*)malloc(ps->capacity * sizeof(int));
    assert(ps->arr != NULL);
}

// 入栈操作
void push(Stack* ps, int x) {
    if (ps->top == ps->capacity) {
        // 栈满，扩容
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        int* tmp = (int*)realloc(ps->arr, newCapacity * sizeof(int));
        if (tmp == NULL) {
            perror("realloc fail\n");
            exit(1);
        }
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
    ps->arr[ps->top++] = x;
}

// 出栈操作
int pop(Stack* ps) {
    assert(ps->top > 0);
    return ps->arr[--ps->top];
}

// 获取栈顶元素
int top(Stack* ps) {
    assert(ps->top > 0);
    return ps->arr[ps->top - 1];
}

// 检查栈是否为空
int isEmpty(Stack* ps) {
    return ps->top == 0;
}

// 释放栈内存
void freeStack(Stack* ps) {
    free(ps->arr);
    ps->arr = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

最后一题代码

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

// 定义栈的数据结构
typedef struct Stack {
    int* arr;
    int top;
    int capacity;
} Stack;

// 初始化栈
void initStack(Stack* ps) {
    ps->capacity = 4;
    ps->top = 0;
    ps->arr = (int*)malloc(ps->capacity * sizeof(int));
    assert(ps->arr!= NULL);
}

// 入栈操作
void push(Stack* ps, int x) {
    if (ps->top == ps->capacity) {
        // 栈满，扩容
        int newCapacity = ps->capacity == 0? 4 : 2 * ps->capacity;
        int* tmp = (int*)realloc(ps->arr, newCapacity * sizeof(int));
        if (tmp == NULL) {
            perror("realloc fail\n");
            exit(1);
        }
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
    ps->arr[ps->top++] = x;
}

// 出栈操作
int pop(Stack* ps) {
    assert(ps->top > 0);
    return ps->arr[--ps->top];
}

// 获取栈顶元素
int top(Stack* ps) {
    assert(ps->top > 0);
    return ps->arr[ps->top - 1];
}

// 检查栈是否为空
int isEmpty(Stack* ps) {
    return ps->top == 0;
}

// 释放栈内存
void freeStack(Stack* ps) {
    free(ps->arr);
    ps->arr = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

bool isValid(char* s) {
    Stack st;
    initStack(&st);
    char* pi = s;
    while (*pi!= '\0') {
        if (*pi == '(' || *pi == '{' || *pi == '[') {
            // 入栈
            push(&st, *pi);
        } else {
            // 判断，取栈
            if (isEmpty(&st)) {
                freeStack(&st);
                return false;
            }
            char top = (char)pop(&st);
            if ((top == '(' && *pi!= ')') || (top == '[' && *pi!= ']') || (top == '{' && *pi!= '}')) {
                freeStack(&st);
                return false;
            }
        }
        pi++;
    }
    bool ret = isEmpty(&st);
    freeStack(&st);
    return ret;
}

非常感谢您的阅读，喜欢的话记得三连哦

在这里插入图片描述

原文地址：https://blog.csdn.net/2402_83322742/article/details/144052060

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：PostgreSQL外键全解析：从概念到实践的进阶指南
下一篇：第八章 Spring Boot快速⼊⻔ —— Spring Boot整合thymeleaf模板引擎

彻底理解微服务配置中心的作用
如果我们把所有配置放在一个Nacos的配置中心里面统一进行管理，那么就可以非常方便的给它做一些配置，比如说双11大促开始，可以给Redis服务切换到性能高的Redis服务器上去，或者说切换到不同的Re
阅读更多2024-11-27
使用Python和Pybind11调用C++程序（CMake编译）
pybind11 是一个轻量级的头文件库，用于在 Python 和 C++ 之间互相暴露类型，主要用于为现有的 C++ 代码创建 Python 绑定。
阅读更多2024-11-27
解释 Python 中的列表推导式？
列表推导式（List Comprehensions）是 Python 中一种简洁而强大的语法，用于从一个或多个迭代器（如列表、元组、字典等）生成新的列表。列表推导式不仅提高了代码的可读性，还提升了代码
阅读更多2024-11-27
jenkins docker记录
Installing Jenkinsdocker run --name jenkins --restart always -p 8080:8080 -p 50000:50000 -e JAVA_OPT
阅读更多2024-11-27
网络安全概述
不同的用户应从不同的方面对其网络作详尽的分析，选择安全性尽可能高的操作系统。应用的安全涉及方面很多，以Internet上应用最为广泛的 E-mail系统来说，其解决方案有sendmail、Netsca
阅读更多2024-11-27
【docker集群应用】Docker网络与资源控制
Docker 网桥是虚拟的，不是真实存在的网络设备，因此外部网络无法直接寻址到它，这意味着外部网络无法直接通过 Container-IP 访问容器。由于同一宿主机内的容器都连接到同一个网桥，因此容器之
阅读更多2024-11-27
Git——本地仓库链接并推送到多个远程仓库
在gitee、github等托管平台创建仓库，获取到对应的https。
阅读更多2024-11-27
学习日记_20241126_聚类方法（聚合聚类Agglomerative Clustering）
学习日记，聚合聚类
阅读更多2024-11-27
「qt交叉编译arm64」支持xcb、X11
通过指定-sysroot，configure的功能检测测试使用的包含文件和库以及Qt本身都是从指定位置取代，而不是主机PC的标准位置。若已经成功编译并安装相关库，检查安装目录下是否有对应的头文件、库文
阅读更多2024-11-27
Ubuntu 20.04安装VMware Tool和Docker
执行apt-get update及安装依赖遇到download.docker.com无法访问的问题。
阅读更多2024-11-27

C语言数据结构——详细讲解《栈》

C语言数据结构——详细讲解《栈》

前言

一、栈的概念

二、栈的定义

三、栈的操作

1.初始化栈

2. 入栈操作

3. 出栈操作

4. 获取栈顶元素

5. 检查栈是否为空

6.释放栈内存

四、栈的例题

五、本文的所有代码

Stack.c

Stack,h

最后一题代码

相关文章