首页 > 其他分享 >数据结构--栈的介绍

数据结构--栈的介绍

时间:2024-03-26 21:30:01浏览次数:27  
标签:-- top 栈顶 介绍 int StackNode 数据结构 data Stack

目录

一 简介

二 栈的抽象数据类型(C语言实现)

三 栈的顺序存储结构

三 栈的链式存储结构


一 简介

栈是一种线性数据结构,遵循“后进先出”(Last In First Out,简称LIFO)原则。在栈中,数据的插入和删除操作只允许在表的一端进行,这一端被称为栈顶。如同现实中的栈板,最后放入的元素最先被取出。主要操作包括压栈(Push,将元素添加到栈顶)、弹栈(Pop,移除并返回栈顶元素)以及查看栈顶元素(Top)。栈常用于函数调用、表达式求值、括号匹配等计算机科学领域的多种问题解决中。

二 栈的抽象数据类型(C语言实现)

在C语言中,因为没有内置的栈数据结构,所以我们需要通过定义结构体来模拟栈的行为,并通过函数来实现栈的各种操作。以下是一个简单的栈抽象数据类型的C语言定义示例:

#include <stdio.h>

// 定义栈元素类型
typedef int ElementType;

// 定义栈节点结构体(如果采用链式栈)
typedef struct StackNode {
    ElementType data;
    struct StackNode* next;
} StackNode;

// 定义栈结构体(此处使用顺序栈的结构)
typedef struct {
    ElementType* elements; // 存储元素的数组
    int capacity; // 栈的容量
    int top; // 栈顶指针,指向栈顶元素的位置
} Stack;

// 初始化栈
void initStack(Stack* s, int initialCapacity);

// 销毁栈(释放内存)
void destroyStack(Stack* s);

// 入栈操作
bool push(Stack* s, ElementType item);

// 出栈操作,同时返回栈顶元素
ElementType pop(Stack* s);

// 查看栈顶元素而不移除
ElementType peek(Stack* s);

// 判断栈是否为空
bool isEmpty(Stack* s);

// 获取栈的大小
int size(Stack* s);

// 实现上述函数的具体内容
// ...

#endif // STACK_H

/* 示例实现部分(通常在单独的.c文件中)

void initStack(Stack* s, int initialCapacity) {
    s->elements = (ElementType*)malloc(initialCapacity * sizeof(ElementType));
    if (!s->elements) {
        // 处理内存分配失败情况...
    }
    s->capacity = initialCapacity;
    s->top = -1; // 初始化时栈为空
}

... // 其他函数的实现

*/

以上定义了栈的抽象数据类型,包括栈的结构体和相关的操作函数原型,但并未给出每个函数的具体实现。在实际项目中,你需要根据所使用的数据结构(顺序栈或链式栈)来完成相应的操作实现,比如扩容、缩容、元素的插入和删除等。

三 栈的顺序存储结构

在C语言中,栈作为一种线性数据结构,其顺序存储结构可以通过动态分配的数组或静态预先分配的数组来实现。以下是一个简单的顺序栈的结构定义及其基本操作实现示例:

// 定义顺序栈结构体
typedef struct {
    int *data; // 动态分配的数组,用于存储栈内元素
    int capacity; // 栈的容量
    int top; // 栈顶指针,指向栈顶元素的位置(数组索引),初始时为-1,表示栈为空
} SqStack;

// 初始化顺序栈
void InitStack(SqStack *s, int cap) {
    s->capacity = cap;
    s->data = (int *)malloc(cap * sizeof(int)); // 动态分配内存
    if (!s->data) {
        printf("Memory allocation failed!\n");
        exit(EXIT_FAILURE);
    }
    s->top = -1; // 初始化栈顶指针为-1,表示栈为空
}

// 判断栈是否为空
int IsEmpty(SqStack *s) {
    return s->top == -1;
}

// 入栈操作(压栈)
int Push(SqStack *s, int item) {
    if (s->top == s->capacity - 1) {
        printf("Stack is full!\n");
        return FAILURE; // 表示栈满无法入栈
    }
    s->data[++s->top] = item; // 栈顶指针加1,并将新元素存入
    return SUCCESS; // 表示入栈成功
}

// 出栈操作(弹栈)
int Pop(SqStack *s, int *item) {
    if (IsEmpty(s)) {
        printf("Stack is empty!\n");
        return FAILURE; // 表示栈空无法出栈
    }
    *item = s->data[s->top]; // 取出栈顶元素
    s->top--; // 更新栈顶指针
    return SUCCESS; // 表示出栈成功
}

// 销毁栈(释放内存)
void DestroyStack(SqStack *s) {
    free(s->data);
    s->data = NULL;
    s->top = -1;
    s->capacity = 0;
}

以上实现包括了创建栈、初始化、判断栈是否为空、入栈、出栈和销毁栈的功能。实际应用中,可能还需要其他辅助功能如获取栈顶元素但不移除等。请注意,上述代码没有包含错误处理的完整细节,实际编程时应当确保程序健壮性。同时,为了简化问题,这里假设栈只存储整数类型,若要存储不同类型的元素,可以改为泛型指针或其他灵活的数据结构设计。

三 栈的链式存储结构

在C语言中,栈的链式存储结构通常采用单链表来实现,链栈中的每个节点除了存储数据外,还包含一个指向下一个节点的指针。以下是链栈的基本结构定义以及相应的基本操作实现:

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

// 定义链栈节点结构体
typedef struct Node {
    int data; // 数据域,存储栈中的元素
    struct Node *next; // 指针域,指向下一个节点
} StackNode;

// 定义链栈结构体
typedef struct {
    StackNode *top; // 栈顶指针,指向栈顶元素
} LinkStack;

// 初始化链栈
void InitStack(LinkStack *s) {
    s->top = NULL; // 初始化时栈为空,栈顶指针为空
}

// 判断链栈是否为空
int IsEmpty(LinkStack *s) {
    return s->top == NULL;
}

// 创建新节点
StackNode* CreateNode(int data) {
    StackNode *node = (StackNode*)malloc(sizeof(StackNode));
    if (node == NULL) {
        printf("Memory allocation failed.\n");
        exit(EXIT_FAILURE);
    }
    node->data = data;
    node->next = NULL;
    return node;
}

// 入栈操作(压栈)
void Push(LinkStack *s, int item) {
    StackNode *newNode = CreateNode(item);
    
    newNode->next = s->top; // 新节点指向原栈顶
    s->top = newNode; // 更新栈顶指针为新节点
}

// 出栈操作(弹栈)
int Pop(LinkStack *s) {
    if (IsEmpty(s)) {
        printf("Stack is empty, cannot pop.\n");
        exit(EXIT_FAILURE); // 或者返回一个错误值
    }
    
    StackNode *temp = s->top;
    int item = temp->data;
    
    s->top = s->top->next; // 更新栈顶指针为原栈顶的下一个节点
    free(temp); // 释放弹出节点的内存
    
    return item; // 返回弹出的栈顶元素
}

// 销毁链栈
void DestroyStack(LinkStack *s) {
    while (!IsEmpty(s)) {
        StackNode *temp = s->top;
        s->top = s->top->next;
        free(temp);
    }
    s->top = NULL; // 清空栈顶指针
}

通过上述代码,我们可以看到链栈相比于顺序栈的优点在于不需要预先确定栈的大小,理论上它可以无限扩展,只要内存允许即可。每次压栈时创建新的节点并将其链接到栈顶,而弹栈时只需修改栈顶指针并将不再需要的节点释放掉。

标签:--,top,栈顶,介绍,int,StackNode,数据结构,data,Stack
From: https://blog.csdn.net/m0_61635718/article/details/137047944

相关文章

  • 13. 一起学习机器学习 PCA
    LineardimensionalityreductionThepurposeofthisnotebookistounderstandandimplementtwolineardimensionalityreductionmethods:Principlecomponentanalysis(PCA)Non-NegativeMatrixFactorization(NMF)Themainideaofthesemethodsistoappro......
  • LeetCode 11.盛最多的水(双指针,贪心)
    题目:思路:我们可以安排俩个指针(数组下标)放在数组的头部和尾部;每次移动高度较低的下标,判断是否为最大水量并记录;(水量=下标差乘较小高度)证明可行性:如果移动高度较高的下标,由于下标差减小,故不论后面下标对应的高度增大,不变或减小都会导致水量减小;(增大:下标差减小,较小高度......
  • 10. 一起学习机器学习 -- Convolutional Neural Networks (CNNs)
    ConvolutionalNeuralNetworks(CNNs)ThepurposeofthisnotebookistopracticeimplementingandtrainingCNNs.Westartwitha1-dimensionalconvolutionallayerinNumPy.WewillthenusePyTorch,anoptimisedmachinelearningframeworkforPythonbas......
  • 介绍一款非常不错的录像软件
    介绍一款非常不错的录像软件。支持很多录音格式,有AVI,MP4,MOV,TS,VOB等,你也可以自定义设置影片的FPS和比特率。如果你想长时间的录制视频,影片大小可支持4个G的超大文件录制。支持全屏幕录制,也支持自定义范围录制,你可通过调节录像框来决定录像的范围,将不想要录制的地方隐藏......
  • 3.26博客
    作业根据地域属性实现数据的可视化展示,可以看到省-市-区县三级数据下钻呈现的项目数量name为null的时候value显示为NAN因为地图该区域在数据库中没有匹配的name,所以这里count(*)直接为null,显示NAN; b->namec-<value 之前在select那里判空,没用,后来想起了地图部分在数据库......
  • 移动端 App
    移动端App概述思源笔记提供了Android端和iOS端App,已经上架部分手机应用商店,请在应用商店中搜索思源笔记​或者SiYuan​。安装和更新目前已经上架应用商店:小米华为OPPOvivo苹果酷安GooglePlayAPK下载:https://b3log.org/siyuan/download.html使用集市因......
  • 虚树
    虚树用途一棵树上进行m次不同的操作,每次用到k个节点($\sumk$$O(n)级别$)用于于树上DP原理将原树里的一部分用到的节点抠出来,建一棵新树(虚树),在上面进行DP优点:降低每次操作的复杂度构建将要用到的节点(设为s)按照dfn序排序dfn序相近的在原树上......
  • zabbix配置https访问
    1、启用ssl模块,apache2不用再去安装mod_ssl模块sudoa2enmodssl 2、创建存放证书文件的目录并赋予所有权限sudomkdir/etc/apache2/sslsudochmod777/etc/apache2/ssl 3、将证书文件上传至刚创建的目录下 4、将 /etc/apache2/sites-available/000-default......
  • 没想到三天10KStar的营销利器MediaCrawler开源作者已经删库了
    前言一站式社交平台数据抓取利器,带你玩转小红书、抖音、快手、B站和微博数据分析不经意间,来查看MediaCrawler仓库源码,发现作者已经删库了。看来是领奖了。才几天不到的时间Star数量已经直逼10K了,增长速度近乎疯狂。前两天只是将代码下载下来了,还没认真的玩。还好代码本地已经......
  • Div4 VP总结
    CodeforcesRound799(Div.4)E(最长子区间)基本思路求满足s的最长子区间。错误思路分析想用双指针左右贪心模拟题目要求删前或后的数(但在面对前后两个相等的时候,删前删后没有无后效性)简单暴力枚举子区间长度(显然在n=1e5的时候t了)正确思路虽然也是暴力枚举子区间,但有做......