【C 数据结构】栈

文章目录

  • 【 1. 基本原理 】
    • 栈的分类
  • 【 2. 动态链表栈 】
    • 2.1 双结构体实现
      • 2.1.0 栈的节点设计
      • 2.1.1 入栈
      • 2.1.2 出栈
      • 2.1.3 遍历
      • 2.1.4 实例
    • 2.2 单结构体实现
      • 2.2.0 栈的节点设计
      • 2.2.1 入栈
      • 2.2.2 出栈
      • 2.2.3 实例
  • 【 3. 顺序栈 】
    • 3.1 入栈
    • 3.2 出栈
    • 3.3 实例

【 1. 基本原理 】

  • 栈(Stack) 是一个线性的数据结构:
    • 栈只能从表的一端存取数据,另一端是封闭的;
    • 在栈中,无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。
      在这里插入图片描述
  • 栈的开口端被称为 栈顶,栈顶元素指的就是距离栈顶最近的元素;封口端被称为 栈底,栈底元素指的是位于栈最底部的元素。
    在这里插入图片描述
  • 栈的的应用
    • 网页的返回。
    • 代码中的括号匹配。
    • 进制转换。

栈的分类

  • 栈分为数组栈和链表栈:
    • 顺序栈(数组栈) 采用顺序存储结构,使用数组进行功能的模拟,实现较为快速和便利。
    • 链表栈(链栈) 采用链式存储结构,实现较为麻烦,但是其稳定不易出错。在链表栈中又分为静态链表栈 和 动态链表栈:
      • 静态链表栈 给定栈的空间大小,不允许超过存储超过给定数据大小的元素。
      • 动态链表栈 使用的是 自动创建空间 的方法进行创建,只要符合机器的硬件要求以及编译器的控制,其理论上是极大的。

【 2. 动态链表栈 】

  • 我们以链表栈的动态链表栈为例子,进行栈的设计,在后文直接以栈一名字称呼动态链表栈,这也是各类语言标准模板中栈的实现方式。
    在这里插入图片描述

2.1 双结构体实现

2.1.0 栈的节点设计

  • 我们可以设计出两个结构体:
    • 一个结构体Node表示结点,其中包含有一个data域和next指针。其中data表示数据,其可以是简单的类型(如int,double等等),也可以是复杂的结构体(struct类型);next指针表示,下一个的指针,其指向下一个结点,通过next指针将各个结点链接。
      在这里插入图片描述
    • 额外添加的另一个结构体,其包括了一个永远指向栈头的指针top和一个计数器count记录元素个数,(也可以设计成一个指针top和一个指针bottom分别指向栈头和栈尾)其主要功效就是设定允许操作元素的指针以及确定栈何时为空(count的方法是当count为0时为空,top和bottom方法就是两者指向同一个空间时为栈为空)。
      在这里插入图片描述
  • 采用的 top 和 count 组合的方法,C 实现:
//栈的结点设计
//单个结点设计,数据和下一个指针
typedef struct node     
{
    int data; 
    struct node *next;
} Node;
//利用上面的结点创建栈,分为指向头结点的top指针和计数用的count
typedef struct stack    
{
    Node *top;
    int count;
} Link_Stack;

2.1.1 入栈

  • 入栈(push)操作时,我们只需要找到top所指向的空间,创建一个新的结点,将新的结点的next指针指向我们的top指针指向的空间,再将top指针转移,指向新的结点,即是入栈操作。
    在这里插入图片描述
  • C 实现:
//入栈 push
Link_Stack *Push_stack(Link_Stack *p, int elem)
{
    if (p == NULL)
        return NULL;
    Node *temp;
    temp=(Node*)malloc(sizeof(Node));
    temp->data = elem;
    temp->next = p->top;
    p->top = temp;
    p->count++;
    return p;
}

2.1.2 出栈

  • 出栈(pop)操作,是在栈不为空的情况下(注意一定要进行判空操作),将栈顶的元素删除,同时top指针,next向下进行移动即可的操作。
    在这里插入图片描述
  • C 实现:
//出栈 pop
Link_Stack *Pop_stack(Link_Stack *p)
{
    Node *temp;
    temp = p->top;
    if (p->top == NULL)
    {
        printf("错误:栈为空");
        return p;
    }
    else
    {
        p->top = p->top->next;
        free(temp);
        p->count--;
        return p;
    }
}

2.1.3 遍历

  • 栈的遍历,由于栈的特殊性质,其只允许在一端进行操作,所以我们的遍历操作永远都是逆序的,其过程为:在栈不为空的情况下,一次从栈顶元素向下访问,直到指针指向空(即到栈尾)为结束。
  • C 实现:
//遍历栈:输出栈中所有元素
int show_stack(Link_Stack *p)
{
    Node *temp;
    temp = p->top;
    if (p->top == NULL)
    {
        printf("");
        printf("错误:栈为空");
        return 0;
    }
    while (temp != NULL)
    {
        printf("%d\t", temp->data);
        temp = temp->next;
    }
    printf("\n");
    return 0;
}

2.1.4 实例

  • C 实现:
#include <stdio.h>
#include <stdlib.h>
//栈的结点设计
//单个结点设计,数据和下一个指针
typedef struct node     
{
    int data; 
    struct node *next;
} Node;
//利用上面的结点创建栈,分为指向头结点的top指针和计数用的count
typedef struct stack    
{
    Node *top;
    int count;
} Link_Stack;
 
//创建栈
Link_Stack *Creat_stack()
{
    Link_Stack *p;
    //p = new Link_Stack;
    p=(Link_Stack*)malloc(sizeof(Link_Stack));
    if(p==NULL){
        printf("创建失败,即将退出程序");
        exit(0);
    }
    p->count = 0;
    p->top = NULL;
    return p;
}
 
//入栈 push
Link_Stack *Push_stack(Link_Stack *p, int elem)
{
    if (p == NULL)
        return NULL;
    Node *temp;
    temp=(Node*)malloc(sizeof(Node));
    //temp = new Node;
    temp->data = elem;
    temp->next = p->top;
    p->top = temp;
    p->count++;
    return p;
}
 
//出栈 pop
Link_Stack *Pop_stack(Link_Stack *p)
{
    Node *temp;
    temp = p->top;
    if (p->top == NULL)
    {
        printf("错误:栈为空");
        return p;
    }
    else
    {
        p->top = p->top->next;
        free(temp);
        //delete temp;
        p->count--;
        return p;
    }
}
 
//遍历栈:输出栈中所有元素
int show_stack(Link_Stack *p)
{
    Node *temp;
    temp = p->top;
    if (p->top == NULL)
    {
        printf("");
        printf("错误:栈为空");
        return 0;
    }
    while (temp != NULL)
    {
        printf("%d\t", temp->data);
        temp = temp->next;
    }
    printf("\n");
    return 0;
}
 
int main()
{ //用主函数测试一下功能
    Link_Stack *p;
    p = Creat_stack();
    int n = 5;
    int input[6] = {10,20,30,40,50,60};
    /以依次入栈的方式创建整个栈//
    for(int i=0;i<n;i++){
        Push_stack(p, input[i]);
    }
    show_stack(p);
    出栈///
    Pop_stack(p);
    show_stack(p);
    return 0;
}

在这里插入图片描述

2.2 单结构体实现

  • 使用单结构体实现链表:
    • 在实现数据"入栈"操作时,需要将数据从链表的头部插入(单链表的头插法);
    • 在实现数据"出栈"操作时,需要删除链表头部的首元节点;

2.2.0 栈的节点设计

  • C实现:
//链表中的节点结构
typedef struct lineStack{
    int data;
    struct lineStack * next;
}lineStack;

2.2.1 入栈

  • 将元素 1、2、3、4 依次入栈,等价于将各元素采用头插法依次添加到链表中,每个数据元素的添加过程如图所示:
    在这里插入图片描述
  • C实现:
//链表中的节点结构
typedef struct lineStack{
    int data;
    struct lineStack * next;
}lineStack;
//stack为当前的链栈,a表示入栈元素
lineStack* push(lineStack * stack,int a){
    //创建存储新元素的节点
    lineStack * line=(lineStack*)malloc(sizeof(lineStack));
    line->data=a;
    //新节点与头节点建立逻辑关系
    line->next=stack;
    //更新头指针的指向
    stack=line;
    return stack;
}

2.2.2 出栈

  • 若要将元素 3 出栈,根据"先进后出"的原则,要先将元素 4 出栈,也就是从链表中摘除,然后元素 3 才能出栈:
  • C 实现:
//栈顶元素出链栈的实现函数
lineStack * pop(lineStack * stack){
    if (stack) {
        //声明一个新指针指向栈顶节点
        lineStack * p=stack;
        //更新头指针
        stack=stack->next;
        printf("出栈元素:%d ",p->data);
        if (stack) {
            printf("新栈顶元素:%d\n",stack->data);
        }else{
            printf("栈已空\n");
        }
        free(p);
    }else{
        printf("栈内没有元素");
        return stack;
    }
    return stack;
}

2.2.3 实例

#include <stdio.h>
#include <stdlib.h>
typedef struct lineStack{
    int data;
    struct lineStack * next;
}lineStack;
lineStack* push(lineStack * stack,int a){
    lineStack * line=(lineStack*)malloc(sizeof(lineStack));
    line->data=a;
    line->next=stack;
    stack=line;
    return stack;
}
lineStack * pop(lineStack * stack){
    if (stack) {
        lineStack * p=stack;
        stack=stack->next;
        printf("弹栈元素:%d ",p->data);
        if (stack) {
            printf("栈顶元素:%d\n",stack->data);
        }else{
            printf("栈已空\n");
        }
        free(p);
    }else{
        printf("栈内没有元素");
        return stack;
    }
    return stack;
}
int main() {
    lineStack * stack=NULL;
    stack=push(stack, 1);
    stack=push(stack, 2);
    stack=push(stack, 3);
    stack=push(stack, 4);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    return 0;
}

在这里插入图片描述

【 3. 顺序栈 】

  • 我们通过顺序表(底层实现是数组)模拟顺序栈/数组栈。思路为:在顺序表中设定一个实时指向栈顶元素的变量(一般命名为 top),top 初始值为 -1,表示栈中没有存储任何数据元素,及栈是"空栈"。一旦有数据元素进栈,则 top 就做 +1 操作;反之,如果数据元素出栈,top 就做 -1 操作。

在这里插入图片描述

3.1 入栈

  • 比如,模拟栈存储 {1,2,3,4} 的过程。最初,栈是"空栈",即数组是空的,top 值为初始值 -1:
    在这里插入图片描述
  • 首先向栈中添加元素 1,我们默认数组下标为 0 一端表示栈底,因此,元素 1 被存储在数组 a[0] 处,同时 top 值 +1:
    在这里插入图片描述
  • 采用以上的方式,依次存储元素 2、3 和 4,最终,top 值变为 3:
    在这里插入图片描述
  • C 实现:
//元素elem进栈,a为数组,top值为当前栈的栈顶位置
int push(int* a,int top,int elem){
    a[++top]=elem;
    return top;
}

3.2 出栈

  • 将上图中的元素 2 出栈,则需要先将元素 4 和元素 3 依次出栈。当有数据出栈时,要将 top 做 -1 操作。因此,元素 4 和元素 3 出栈的过程分别如图所示:
    在这里插入图片描述
  • 上图中数组中元素的消失仅是为了方便初学者学习,其实,这里只需要对 top 值做 -1 操作即可,因为 top 值本身就表示栈的栈顶位置,因此 top-1 就等同于栈顶元素出栈。并且后期向栈中添加元素时,新元素会存储在类似元素 4 这样的旧元素位置上,将旧元素 覆盖
  • C 实现:
//数据元素出栈
int pop(int * a,int top){
    if (top==-1) { //防止用户做 "栈中已无数据却还要数据出栈" 的错误操作
        printf("空栈");
        return -1;
    }
    printf("弹栈元素:%d\n",a[top]);
    top--;
    return top;
}

3.3 实例

  • 实例1:直接数组法
#include <stdio.h>
//元素elem进栈
int push(int* a, int top, int elem) {
    a[++top] = elem;
    return top;
}
//数据元素出栈
int pop(int* a, int top) {
    if (top == -1) {
        printf("空栈");
        return -1;
    }
    printf("弹栈元素:%d\n", a[top]);
    top--;
    return top;
}
int main() {
    int a[100];
    int top = -1;
    top = push(a, top, 3);
    top = push(a, top, 1);
    top = push(a, top, 4);
    top = push(a, top, 5);
    top = pop(a, top);
    top = pop(a, top);
    top = pop(a, top);
    top = pop(a, top);
    top = pop(a, top);
    return 0;
}

在这里插入图片描述

  • 实例2:构建结构体
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 10000
  
//结点设计
typedef struct stack{
    int data[maxn];
    int top;
}stack;
  
//创建
stack *init(){
    stack *s=(stack *)malloc(sizeof(stack));
    if(s==NULL){
        printf("分配内存空间失败");
        exit(0);
    }
    memset(s->data,0,sizeof(s->data));
    //memset操作来自于库文件string.h,其表示将整个空间进行初始化
    //不理解可以查阅百度百科https://baike.baidu.com/item/memset/4747579?fr=aladdin
    s->top=0;     //栈的top和bottom均为0(表示为空)
    return s;
}
  
//入栈push
void push(stack *s,int data){
    s->data[s->top]=data;
    s->top++;
}
  
//出栈pop
void pop(stack *s){
    if(s->top!=0){
        s->data[s->top]=0;  //让其回归0模拟表示未初始化即可
        s->top--;
    }
}
  
//模拟打印栈中元素
void print_stack(stack *s){
    for(int n=s->top-1;n>=0;n--){
        printf("%d\t",s->data[n]);
    }
    printf("\n");   //习惯性换行
}
  
int main(){
    stack *s=init();
    int input[5]={11,22,33,44,55};  //模拟五个输入数据
    for(int i=0;i<5;i++){
        push(s,input[i]);
    }
    print_stack(s);
    /
    pop(s);
    print_stack(s);
    return 0;
}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/546992.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

操作系统:进程(二)

进程的状态 进程状态反映进程执行过程的变化。这些状态随着进程的执行和外界条件的变化而转换。在三态模型中&#xff0c;进程状态分为三个基本状态&#xff0c;即运行态&#xff0c;就绪态&#xff0c;阻塞态。 一个进程从创建而产生至撤销而消亡的整个生命期间&#xff0c;…

【图像分类】基于深度学习的轴承和齿轮识别(ResNet网络)

写在前面: 首先感谢兄弟们的关注和订阅,让我有创作的动力,在创作过程我会尽最大能力,保证作品的质量,如果有问题,可以私信我,让我们携手共进,共创辉煌。(专栏订阅用户订阅专栏后免费提供数据集和源码一份,超级VIP用户不在服务范围之内,不想订阅专栏的兄弟们可以私信…

java的深入探究JVM之类加载与双亲委派机制

前言 前面学习了虚拟机的内存结构、对象的分配和创建&#xff0c;但对象所对应的类是怎么加载到虚拟机中来的呢&#xff1f;加载过程中需要做些什么&#xff1f;什么是双亲委派机制以及为什么要打破双亲委派机制&#xff1f; 类的生命周期 类的生命周期包含了如上的7个阶段&a…

A complete evaluation of the Chinese IP geolocation databases(2015年)

下载地址:A Complete Evaluation of the Chinese IP Geolocation Databases | IEEE Conference Publication | IEEE Xplore 被引用次数:12 Li H, He Y, ** R, et al. A complete evaluation of the Chinese IP geolocation databases[C]//2015 8th International Conference…

MyBatis 源码分析系列文章导读

1.本文速览 本篇文章是我为接下来的 MyBatis 源码分析系列文章写的一个导读文章。本篇文章从 MyBatis 是什么&#xff08;what&#xff09;&#xff0c;为什么要使用&#xff08;why&#xff09;&#xff0c;以及如何使用&#xff08;how&#xff09;等三个角度进行了说明和演…

异地组网如何安装?

【天联】是一款强大的异地组网安装工具&#xff0c;可以帮助企业实现远程设备的统一管理和协同办公。以下是【天联】可以应用的一些场景&#xff1a; 零售、收银软件应用统一管理&#xff1a;【天联】可以结合医药、餐饮、商超等零售业的收银软件&#xff0c;实现异地统一管理。…

TongRds docker 镜像做成与迁移(by liuhui)

TongRds docker 镜像做成与迁移 一&#xff0c;使用 docker commit 命令制作 TongRds docker 镜 像 1.1 拉取基础镜像 centos 并运行该镜像 拉取镜像&#xff1a;docker pull ubuntu 镜像列表&#xff1a;docker images 运行镜像&#xff1a;docker run -itd --name myubuntu…

吴恩达2022机器学习专项课程(一) 第二周课程实验:使用 scikit-learn 进行线性回归(Lab_05 Lab_06)

目标 使用scikit-learn实现线性回归(SGDRegressor和LinearRegression)。 1.什么是scikit-learn? 一个用于 Python 编程语言的开源机器学习库,用于实现各种机器学习算法。 2.特征缩放&#xff08;Z标准化&#xff09; 第一步先使用Z标准化处理训练样本&#xff0c;减少训练…

C#创建随机更换背景图片的窗体的方法:创建特殊窗体

目录 一、涉及到的知识点 1.图片资源管理器设计Resources.Designer.cs 2.把图片集按Random.Next方法随机化 3.BackgroundImage属性 二、实例设计 1. Resources.Designer.cs 2.Form1.Designer.cs 3.Form1.cs 4.生成效果 很多时候&#xff0c;我们需要每次打开窗体时能够…

项目三:学会如何使用python爬虫请求库(小白入门级)

根据上一篇文章我们学会的如何使用请求库和编写请求函数&#xff0c;这一次我们来学习一下爬虫常用的小技巧。 自定义Headers Headers是请求的一部分&#xff0c;包含了关于请求的元信息。我们可以在requests调用中传递一个字典来自定义Headers。代码如下 import requests h…

如何做一个springboot的starter类型的SDK

关键的东西 首先我们是一个starter类型的SDK&#xff0c;为了给调用者使用&#xff0c;其中有一些Bean我们会放到SDK中&#xff0c;并且这些Bean能够注入到调用者的Spring容器中。 最关键的spring.factories文件 这个文件所在位置如下图所示&#xff0c;该文件通过写入一下代…

六、新闻主题分类任务

以一段新闻报道中的文本描述内容为输入&#xff0c;使用模型帮助我们判断它最有可能属于哪一种类型的新闻&#xff0c;这是典型的文本分类问题。我们这里假定每种类型是互斥的&#xff0c;即文本描述有且只有一种类型&#xff0c;例如一篇新闻不能即是娱乐类又是财经类&#xf…

云正在使 IT 受益,但对业务却没有好处

云具有巨大的商业价值&#xff01;这是云提供商及其盟友在每次云计算会议上高喊的战斗口号。 您永远不会听到我说“云”始终是正确的解决方案&#xff0c;或者就此而言&#xff0c;是错误的解决方案。 在作为云专家 20 多年的时间里&#xff0c;从来没有盲目追随云计算先驱或…

面试手撕合集

82.删除排序链表中的重复元素II 定义单个指针 cur&#xff0c;指向虚拟头节点。如果 cur.next cur.next.next&#xff0c;说明 cur 后面的两个节点重复&#xff0c;例如 节点2 后面存在 2个节点3。我们令 节点2 -> 节点4&#xff0c;实现删除两个节点3的操作。 class Solut…

visual studio连接ubuntu不成功原因(SSH问题)及解决办法

原因1&#xff1a; 网络没有互通&#xff08;一般VMware&#xff09; 使用ping来看网络是不是可以互通&#xff0c;例如&#xff1a; //这里的ip是ubuntu的ip&#xff0c;也可以从ubuntu的客户端ping一下当前主机 ping 192.168.1.101原因2&#xff1a; SSH没有密钥&#xf…

从iPhone恢复已删除照片的最佳软件

本文分享了从iPhone恢复已删除照片的最佳软件。如果您正在寻找如何从iPhone恢复已删除的照片&#xff0c;请查看这篇文章。 为什么您需要软件从iPhone恢复已删除的照片&#xff1f; 没有什么比丢失iPhone上的重要数据更痛苦的了&#xff0c;尤其是一些具有珍贵回忆的照片。有时…

❤ vue3 使用报错

❤ vue3 项目使用报错 vue3语法变动 TypeError: Assignment to constant variable &#xff08;常量变量&#xff09; 背景&#xff1a; Vue3 项目使用 TypeError: Assignment to constant variable. 原因&#xff1a; 因为我对const定义的常量重新赋值了 解决方法&#…

JVM(Java虚拟机)内存管理基础理论

JVM&#xff08;Java虚拟机&#xff09;内存管理是Java开发和性能优化中的一个核心领域。理解JVM的内存结构和管理机制对于编写高效的Java程序和进行有效的性能调优非常重要。以下是一个关于JVM内存学习的大纲&#xff0c;涵盖了从基础知识到高级主题的各个方面&#xff1a; 1.…

EasyRecovery2024专业免费的电脑数据恢复软件

EasyRecovery数据恢复软件是一款功能强大的数据恢复工具&#xff0c;广泛应用于各种数据丢失场景&#xff0c;帮助用户从不同类型的存储介质中恢复丢失或删除的文件。 该软件支持恢复的数据类型非常广泛&#xff0c;包括但不限于办公文档、图片、音频、视频、电子邮件以及各种…

Hive on spark源码编译与调优

文章目录 一、编译环境准备1、hadoop和hive安装2、编译环境搭建3、Hive on Spark配置 二、Hive相关问题1、Hadoop和Hive的兼容性问题1.1 问题描述1.2 解决思路1.3 修改并编译Hive源码 2、Hive插入数据StatsTask失败问题3.1 问题描述3.2 解决思路 3、Hive和Spark兼容性问题3.1 问…