数据结构(顺序栈——c语言实现)

news/2024/11/19 9:31:54/

栈的基本概念:

       栈是限制在一端进行插入操作和删除操作的线性表(俗称堆栈),允许进行操作的一端称为“栈顶”,另一固定端称为“栈底”,当栈中没有元素时称为“空栈”

       特点:先进后出(FILO)或后进先出(LIFO)

栈的优点

  1. 方便快捷:栈的操作非常明确,主要包括Push(压栈)和Pop(弹栈)两个操作,非常方便快捷。

  2. 逻辑清晰:栈的特性使得程序的逻辑非常清晰,因为它保证了操作的顺序和依赖关系。例如,在函数调用中,每进入一个函数,都会将临时变量作为栈帧入栈;当被调用函数执行完成返回后,将这个函数对应的栈帧出栈。这种顺序关系使得程序更易于理解和维护。

  3. 节省空间:栈是一种线性的数据结构,通常只需要在内存中分配一块连续的空间来存储元素,因此可以节省空间。此外,栈的插入和删除操作(即压栈和弹栈)通常只涉及栈顶元素,因此这些操作的时间复杂度较低,通常为O(1)。

  4. 支持递归:栈的特性使得它可以支持递归调用,这是一种非常便利的编程方式。递归调用本身就是一个不断压栈和弹栈的过程,栈能够很好地记录每一层递归的状态,从而确保递归调用的正确性和安全性。

栈的应用场景

  1. 函数调用:操作系统会给每个线程分配一块内存空间,这块内存被组织成栈结构。每进入一个函数,都会将临时变量作为栈帧入栈;当被调用函数执行完成返回后,将这个函数对应的栈帧出栈。这样,就可以保证函数调用的正确性和安全性。

  2. 表达式求值:编译器通过两个栈来实现表达式的求值。一个栈用来保存操作数,另一个栈用来保存运算符。从左到右遍历表达式,当遇到数字时,将其压入操作数栈;当遇到运算符时,将其与运算符栈栈顶元素进行比较,并根据优先级决定是压入栈还是进行运算。

  3. 括号匹配:在编写代码或处理文本时,经常需要检查括号是否匹配。可以使用栈来保存未匹配的左括号,从左到右依次扫描字符串。当扫描到左括号时,将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号进行匹配。这种方法可以高效地检查括号是否匹配。

  4. 浏览器的前进和后退功能:浏览器的前进和后退功能也可以看作是一个栈的应用。当用户浏览网页时,可以将每个网页的URL压入栈中;当用户点击后退按钮时,可以从栈中取出上一个网页的URL并跳转过去。同样地,当用户点击前进按钮时,可以从另一个栈(记录前进历史的栈)中取出下一个网页的URL并跳转过去。

 顺序栈:

       顺序栈是指采用地址连续的存储空间(如数组)来依次存储栈中的数据元素。在顺序栈中,栈底位置是固定不变的,通常设置在数组空间的起始处,而栈顶位置则随着入栈和出栈操作的进行而发生变化。因此,需要用一个整型变量(通常称为“栈顶指针”或“top”)来记录当前栈顶元素在数组中的位置。

#ifndef _SEQSTACK_H
#define _SEQSTACK_H#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//表尾为栈顶,表头为栈底
typedef int Type;
typedef struct{//Type data[size];Type *data;    //栈存储空间的首地址size_t size;      //保存栈空间的长度,无符号的长整形int top;       //栈顶元素的下标
}stack;            //顺序栈//创建栈
stack *create_stack(size_t size);
//判满
int full_stack(stack *s);
//判空 空为0非空为1
int empty_stack(stack *s);
//压栈
void push_stack(stack *s,Type data);
//弹栈
Type pop_stack(stack *s);
//获取栈顶元素
Type get_stack(stack *s);
//初始化
void init_stack(stack *s);
//回收
void free_stack(stack **s);#endif

       对于顺序栈,我这次采用跟之前不同的方法去创建,之前都是在一开始就规定了大小,但是这一次我们在功能函数中创建的时候再去定它的大小,所以在定义结构体的时候里面就有三个成员,一个为Type *类型的指针,用来接收数组的首地址,第二个用来保存栈空间的长度,第三个成员是用来保存栈顶元素下标的一个变量。

#include "seqstack.h"//创建栈
stack *create_stack(size_t size)
{stack *s = (stack *)malloc(sizeof(stack));if(NULL == s){perror("create stack malloc");return NULL;}s->size = size;s->top = -1;s->data = (Type *)malloc(sizeof(Type)*size);if(NULL == s->data){perror("create array  malloc");free(s);return NULL;}return s;
}
//判满 满为0,不满为1
int full_stack(stack *s)
{if(NULL == s){puts("stack is NULL");return -1;}return s->top == s->size-1?0:1;
}
//判空 空为0非空为1
int empty_stack(stack *s)
{if(NULL == s){puts("stack is NULL");return -1;}return s->top == -1?0:1; 
}
//压栈
void push_stack(stack *s,Type data)
{if(!full_stack(s)){puts("栈已满");return;}elses->data[++s->top] = data;
}
//弹栈
Type pop_stack(stack *s)
{if(0 == empty_stack(s)){puts("栈为空,无法操作");}elsereturn s->data[s->top--];
}
//获取栈顶元素
Type get_stack(stack *s)
{if(NULL == s){puts("stack is NULL");}if(0 == empty_stack(s)){puts("空栈,无法获取栈顶元素");}elsereturn s->data[s->top];
}
//初始化
void init_stack(stack *s)
{if(NULL == s){puts("stack is NULL");return;}s->top = -1;
}
//回收
void free_stack(stack **s)
{if(NULL == *s){puts("stack is NULL");return;}free((*s)->data);free(*s);*s = NULL;
}

创建:stack *create_stack(size_t size)

       在这里创建函数跟之前的有所区别,这里的创建我们需要传参,传入所需要创建顺序栈空间的大小;首先创建这个结构体,然后给结构体里的size赋值;因为一开始栈为空栈,没有元素,所以栈顶元素的下标为-1,然后就是顺序栈的空间大小,这个也需要我们开辟,将开辟的空间的首地址赋值给结构体里面的data,之后就通过操作结构体里的data来操作栈;因为这里开辟了两次空间,所以要进行两次判断,来判断开辟空间是否成功。

判满:int full_stack(stack *s)

       顺序栈的判满其实就是看栈顶元素的下标是否与栈长度减去一相等,如果相等证明放满,不等则没有放满;满返回0,不满返回1。

判空:int empty_stack(stack *s)

       判空和判满类似,判空就是看栈顶元素下标top与-1是否相等,如果相等证明栈为空,不相等则栈非空,空返回0,非空返回1。

压栈:void push_stack(stack *s,Type data)

        因为顺序栈是有大小的,所以在压栈之前我们需要判断栈是否放满,如果放满就不能再进行压栈操作,直接return结束即可;如果没有放满那就可以进行压栈,压栈先让栈顶元素下标top++,然后再赋值;顺序栈压栈操作其实就相当于数组的赋值,每次赋值都先让top往后移再赋值,这样top保存的就是最后一个元素的下标。

弹栈:Type pop_stack(stack *s)

       弹栈首先需要判断栈是否为空,如果是空的就无法进行弹栈操作;因为是顺序栈,因此弹栈操作也只需要将弹出的元素作为函数返回值,然后栈顶元素下标往前移动一位即可,下次压栈到这个位置会将原来的值覆盖,因此并不会对压栈造成影响。

获取栈顶元素:Type get_stack(stack *s)

       获取栈顶元素就是直接将top下标对应的元素当做函数返回值返回即可,当然在获取栈顶元素之前需要判断栈是否为空,如果为空就无法获取栈顶元素,就打印一个提示,告诉用户空栈无法获取栈顶元素。

初始化:void init_stack(stack *s)

       顺序栈的初始化和之前顺序表的初始化是一样的,在顺序栈这里只需让栈顶元素的下标top为-1即可,这样在下次压栈的时候就算里面有值也会被覆盖,所以不会对后续操作产生影响。

回收:void free_stack(stack **s)

       回收需要注意的点就是我们在创建的时候不仅创建了结构体,还给顺序栈开辟了空间,因此在回收的时候需要先将存放元素的空间释放,然后再释放存放结构体的空间;当然传参需要传二级指针,我们需要得到的是指针的地址,将存放元素的空间和存放结构体的空间都释放之后再让指针指向NULL就完成了回收。

测试(主函数)

#include "seqstack.h"
int main(int agrc,char *agrv[])
{stack *s = create_stack(5);puts("压栈,将1,2,3,依次压入栈中");push_stack(s,1);push_stack(s,2);push_stack(s,3);puts("弹栈,将栈顶元素弹出");printf("%d\n",pop_stack(s));puts("获取栈顶元素");printf("%d\n",get_stack(s));puts("回收");free_stack(&s);printf("s=%p\n",s);return 0;
}


http://www.ppmy.cn/news/1548198.html

相关文章

有限状态机(续)

一、添加刀光和场景 1、资源链接&#xff1a; 武器刀光&#xff1a;https://assetstore.unity.com/packages/tools/particles-effects/melee-weapon-trail-1728 场景&#xff1a;https://assetstore.unity.com/packages/3d/environments/fantasy/casual-tiny-environment-ju…

【WiFi】ubuntu20.4 WiFi6 无线抓包环境搭建及使用

环境说明 笔记本电脑&#xff0c;无线网卡AX200&#xff0c;安装ubuntu20.04 安装无线网卡工具aircrack-ng sudo apt-get install aircrack-ng 安装wireshark sudo add-apt-repository ppa:wireshark-dev/stable sudo apt update sudo apt -y install wireshark sudo apt -…

CSS基础知识01

一、定义 CSS&#xff08;Cascading Style Sheets&#xff0c;层叠样式表&#xff09;是一种样式表语言&#xff0c;用于描述HTML文档的呈现和美化内容。 二、css的引入方式 2.1.内联样式&#xff08;行内样式&#xff09; 直接在HTML元素的style属性中添加CSS样式。这种方式只…

Flutter:input输入框

输入框&#xff1a; // 是否显示关闭按钮 bool _showClear false; // 文字编辑控制器&#xff0c;监听搜索框的变化。 final TextEditingController _controller TextEditingController(); // 输入框发生变化事件 void _onChange(String value){if(value.length > 0){setS…

游戏引擎学习第16天

视频参考:https://www.bilibili.com/video/BV1mEUCY8EiC/ 这些字幕讨论了编译器警告的概念以及如何在编译过程中启用和处理警告。以下是字幕的内容摘要&#xff1a; 警告的定义&#xff1a;警告是编译器用来告诉你某些地方可能存在问题&#xff0c;尽管编译器不强制要求你修复…

【GAT】 代码详解 (2) 主体框架【pytorch】可运行版本

GRAPH ATTENTION NETWORKS 代码详解 前言一、数据集介绍二、文件整体架构三、GAT代码详解3.1 utils 模块3.1.1 函数 encode_onehot(labels)3.1.2 函数 load_data(path, dataset)3.1.3 函数 normalize_adj(mx)3.1.4 函数 normalize_features(mx)3.1.5 函数 accuracy(output, lab…

【Telephony】Android移动数据网络的控制面和数据面含义

控制面主要负责网络连接的建立和管理&#xff0c;而数据面则负责数据的传输和路由。这两个方面共同协作&#xff0c;为用户提供稳定、高效的移动网络体验。 控制面流程 控制面主要负责处理移动网络的信令和连接管理。当用户尝试使用移动数据网络时&#xff0c;控制面会进行一…

D3基础:绘制圆形、椭圆形、多边形、线、路径、矩形

在D3.js中&#xff0c;可以通过SVG元素来创建各种几何图形。以下是D3.js中常用的几何图形及其简单的创建方法&#xff1a; 1. 圆形 (Circle) 圆形是最基本的形状之一&#xff0c;可以通过<circle>标签来创建。 <!DOCTYPE html> <html> <head><met…