数据结构4-栈、队列

摘要：本文系统介绍了栈和队列两种基础数据结构。栈采用"先进后出"原则，分为顺序栈和链式栈，详细说明了压栈、出栈等基本操作及其实现方法。队列遵循"先进先出"规则，同样分为顺序队列和链式队列，重点讲解了循环队列的判满条件（牺牲一个存储空间）和操作实现。最后通过编程练习展示了如何用链式栈（需两次压栈）和链式队列（直接实现）来完成输入输出顺序一致的功能，提供了完整的代码实现方案。文章内容涵盖数据结构基本概念、分类及具体实现。

一、栈

1、栈的概念：

        1. 先进后出，后进先出
2. 栈顶：允许入栈和出栈的一端称为栈顶
3. 栈底：不允许入栈和出栈的一端称为栈底
4. 入栈（压栈）：将元素放入栈顶位置
5. 出栈（弹栈）：将栈顶元素取出
6. 栈针：记录栈顶位置的标记

2、栈的分类：

        顺序栈、链式栈

3、顺序栈：

3.1 概念:

        1. 增栈：栈的方向自低向高增长
2. 减栈：栈的方向自高向低增长
3. 空栈：栈针指向要入栈的位置
4. 满栈：栈针指向栈顶元素的位置

3.2 顺序栈的实现
3.2.1 节点的定义

3.2.2 顺序栈的创建
  • 申请存放标签的空间
  • 申请存放数据的空间

3.2.3 顺序栈的销毁：
  • 销毁存放数据的空间
  • 销毁存放标签的空间

3.2.4判断是否为空栈
  • 栈针为0即为空栈

3.2.5是否为满栈
  • 栈针与tlen相同即为满栈

3.2.6压栈(输入数据)

  • 将元素放入栈顶位置

  • 栈针位置++

3.2.7出栈
  • 栈针位置--
  • 将栈顶元素出栈

4、链式栈

4.1概念

  1. 使用链表的思想实现链式栈
  2. 参考单向链表节点定义
  3. 压栈参考单向链表头插法
  4. 出栈返回链表第一个有效节点的值，并删除该节点
  5. 销毁栈参考单向链表销毁

4.2链式栈的实现

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

//创建、判断、插入头插法、出栈、销毁
linknode *create_empty_linkstack(void)
{
linknode *ptmpnode = NULL;
ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return NULL;
}
ptmpnode->pnext = NULL;

    return ptmpnode; 
}


int is_empty_linkstack(linknode *phead)
{
return NULL == phead->pnext;     
}


int push_linkstack(linknode *phead,datatype tmpdata)
{
linknode *ptmpnode = NULL;
ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return -1;
}
ptmpnode->data = tmpdata;
ptmpnode->pnext = phead->pnext;
phead->pnext = ptmpnode;

    return 0;
}


datatype pop_linkstack(linknode *phead)
{
linknode *ptmpnode = NULL;
datatype deledata;

    ptmpnode = phead->pnext;
deledata = ptmpnode->data;
phead->pnext = ptmpnode->pnext;
free(ptmpnode);
return deledata;   

}


int destroy_linkstack(linknode **pphead)
{
linknode *ptmpnode = NULL;
linknode *pfreenode = NULL;

    ptmpnode = *pphead;
pfreenode = *pphead;
while (ptmpnode != NULL)
{
ptmpnode = ptmpnode->pnext;
free(pfreenode);
pfreenode = ptmpnode;
}
*pphead = NULL;

    return 0;

}

二、队列

1、概念：

        1. 先进先出，后进后出
2. 队头：出队的一端
3. 队尾：入队的一端
4. 入队：将元素放入队列末尾
5. 出队：将元素从队头中取出

2、分类：

        顺序队列（循环队列）、链式队列

3、顺序队列

3.1基本类型

3.2顺序队列的实现
3.2.1顺序队列的创建

3.2.2顺序队列销毁

3.2.3判断顺序队列是否为空

3.2.4 判断顺序队列是否为满
  • 为避免循环队列空与满的条件冲突，牺牲一个存放数据的空间，将tail+1 == head作为判断队满的条件
  • 循环队列如果head或者tail下标超过tlen范围，需要对tlen取余，保障head和tail的值在队列下标范围内变

3.2.5顺序队列入队

3.2.6顺序队列出队

4、链式队列

4.1概念

  1. 使用链表的思想实现链式栈
  2. 参考单向链表节点定义
  3. 压栈参考单向链表尾插法
  4. 出栈返回链表第一个有效节点的值，并删除该节点
  5. 销毁栈参考单向链表销毁

4.2链式队列的实现

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

//创建、判断、插入只能尾插法、出队、销毁
linknode *create_empty_linkqueue(void)
{ 
//单向链表创建

    linknode *ptmpqueue = NULL;
ptmpqueue = malloc( sizeof(linknode));
if (NULL == ptmpqueue)
{
perror("fail to malloc");
return NULL;
}
ptmpqueue->pnext = NULL;
return ptmpqueue;

}

int is_empty_linkqueue(linknode *phead)
{
//链式队判断是否为NULL

    return NULL == phead->pnext; 

}

int enter_linkqueue(linknode *phead, datatype tmpdata)
{
//尾插法
linknode *ptmpqueue = NULL;
linknode *plastqueue = NULL;

    ptmpqueue = malloc(sizeof(linknode));
if (NULL == ptmpqueue)
{
perror("fail to malloc");
return -1;
}
ptmpqueue->data = tmpdata;
ptmpqueue->pnext = NULL;

    plastqueue = phead;
while (plastqueue->pnext != NULL)
{
plastqueue = plastqueue->pnext;
}
plastqueue->pnext = ptmpqueue;

    return 0;

}

datatype quit_linkqueue(linknode *phead)
{
//链式队列的出队
linknode *ptmpqueue = NULL;
datatype tmpdata;
if (is_empty_linkqueue(phead))
{
return -1;
}
ptmpqueue = phead->pnext;
phead->pnext = ptmpqueue->pnext;
tmpdata = ptmpqueue->data;
free(ptmpqueue);

    return tmpdata;
}

int destroy_linkqueue(linknode **pphead)
{
//单向队表销毁
linknode *ptmpqueue = NULL;
linknode *pfreequeue = NULL;

    ptmpqueue = pfreequeue = *pphead;
while (ptmpqueue != NULL)
{
ptmpqueue = ptmpqueue->pnext;
free(pfreequeue);
pfreequeue = ptmpqueue;
}
*pphead = NULL;
return 0;

}

三、练习

题目：   实现终端输入若干个数（-1结束），输入和输出顺序相同

eg：输入：1  2  3  4  5  -1

        输出：1  2  3  4  5  -1

1、利用链式栈实现 

（1）题目分析

        链式栈只能使用头插法实现，所以输入：1 2 3 4 5 则输出：5 4 3 2 1 要实现题目操作需得再压栈一次再出栈一次便可以实现

（2）注意事项

        1）实现终端接收数，在循环中利用scanf接受数据，用if条件语句结束循环

        2)  利用两个链式栈实现压栈—出栈—压栈—出栈

                两个方法实现，写一个函数实现，在main函数中调用

（3）代码实现

        linkstack.h

#ifndef __LINKSTACK_H__
#define __LINKSTACK_H__

typedef int datatype;
typedef struct node
{
datatype data;
struct node *pnext;
}linknode;

extern linknode *create_empty_linkstack(void);
extern int is_empty_linkstack(linknode *phead);
extern int push_linkstack(linknode *phead,datatype tmpdata);
extern datatype pop_linkstack(linknode *phead);
extern int chance_linkstack(linknode *phead,linknode *phead2);

#endif

        linkstack.c

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

linknode *create_empty_linkstack(void)
{
linknode *ptmpnode = NULL;
ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return NULL;
}
ptmpnode->pnext = NULL;

    return ptmpnode;
}

int is_empty_linkstack(linknode *phead)
{
return NULL == phead->pnext;
}

int push_linkstack(linknode *phead,datatype tmpdata)
{
linknode *ptmpnode = NULL;
ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return -1;
}
ptmpnode->data = tmpdata;
ptmpnode->pnext = phead->pnext;
phead->pnext = ptmpnode;

    return 0;
}

datatype pop_linkstack(linknode *phead)
{
linknode *ptmpnode = NULL;
datatype tmpdata;

    if (is_empty_linkstack(phead))
{
return -1;
}
ptmpnode = phead->pnext;
tmpdata = ptmpnode->data;
phead->pnext = ptmpnode->pnext;
free(ptmpnode);
return tmpdata;

}

int chance_linkstack(linknode *phead,linknode *phead2)
{
linknode *ptmpnode = NULL;
linknode *ptmpnode1 = NULL;

    datatype tmpdata;

    if (is_empty_linkstack(phead))
{
return -1;
}

    ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return -1;
}
ptmpnode->pnext = phead2->pnext;
phead2->pnext = ptmpnode; 

    tmpdata = phead->pnext->data;
ptmpnode->data = tmpdata;

    return 0;
}

        main.c

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

int main(void)
{
linknode *plinkstack = NULL;
linknode *plinkstack2 = NULL;

plinkstack = create_empty_linkstack();
plinkstack2 = create_empty_linkstack();

    while (1)
{
scanf("%d",&plinkstack->data);
if (-1 == plinkstack->data)
{
break;
}
push_linkstack(plinkstack,plinkstack->data);
}


#if 0
//查看是否入栈成功
while (!is_empty_linkstack(plinkstack))
{
printf("%d ",pop_linkstack(plinkstack));
}
printf("\n");
#endif

#if 0
//难为版：自己创个函数
while (1)
{

        if (is_empty_linkstack(plinkstack))
{
break;
}

        chance_linkstack(plinkstack,plinkstack2);
pop_linkstack(plinkstack);

    }

    while (!is_empty_linkstack(plinkstack2))
{
printf("%d ",pop_linkstack(plinkstack2));
}
printf("\n");
#endif


    //灵活版：简单快捷

    while (!is_empty_linkstack(plinkstack))
{

        push_linkstack(plinkstack2,pop_linkstack(plinkstack));
printf("%d ",pop_linkstack(plinkstack2));
}
printf("\n");


    return 0;
}

#if 0

        中间内容可以注释掉

#endif

2、链式队列实现

（1）题目分析：

        队列采用的就是尾插法，只需要在链式队列中加入接收数据。

（2）注意事项：

        注意事项尾插法中的找最后一个节点的条件是while(ptmpqueue->pnext != NULL)

（3）代码实现：

        linkqueue.h

#ifndef __LINKQUEUE_H__
#define __LINKQUEUE_H__

typedef int datatype;
typedef struct node 
{
datatype data;
struct node *pnext;
}linknode;

extern linknode *create_empty_linkqueue(void);
extern int is_empty_linkqueue(linknode *phead);
extern int enter_linkqueue(linknode *phead, datatype tmpdata);
extern datatype quit_linkqueue(linknode *phead);

#endif

        linkqueue.c

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

linknode *create_empty_linkqueue(void)
{
linknode *ptmpqueue = NULL;
ptmpqueue = malloc( sizeof(linknode));
if (NULL == ptmpqueue)
{
perror("fail to malloc");
return NULL;
}
ptmpqueue->pnext = NULL;
return ptmpqueue;
}


int is_empty_linkqueue(linknode *phead)
{
return NULL == phead->pnext;
}

int enter_linkqueue(linknode *phead, datatype tmpdata)
{
linknode *ptmpqueue = NULL;
linknode *plastqueue = NULL;

    ptmpqueue = malloc(sizeof(linknode));
if (NULL == ptmpqueue)
{
perror("fail to malloc");
return -1;
}

    ptmpqueue->data = tmpdata;
ptmpqueue->pnext = NULL;

    plastqueue = phead;
while (plastqueue->pnext != NULL)
{
plastqueue = plastqueue->pnext;
}
plastqueue->pnext = ptmpqueue;

    return 0;
}

datatype quit_linkqueue(linknode *phead)
{
linknode *ptmpqueue = NULL;
linknode *pfreequeue = NULL;
datatype tmpdata;

    if (is_empty_linkqueue(phead))
{
return -1;
}
ptmpqueue = phead->pnext;
phead->pnext = ptmpqueue->pnext;
tmpdata = ptmpqueue->data;
free(ptmpqueue);
return tmpdata;

}

        main.c

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

int main(void)
{
linknode *plinkqueue = NULL;

    plinkqueue = create_empty_linkqueue();

    while (1)
{
scanf("%d",&plinkqueue->data);

        if (-1 == plinkqueue->data)
{
break;
}
enter_linkqueue(plinkqueue,plinkqueue->data);
}

    while (!is_empty_linkqueue(plinkqueue))
{
printf("%d",quit_linkqueue(plinkqueue));
}
printf("\n");

    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/news/917924.shtml
繁体地址，请注明出处：http://hk.pswp.cn/news/917924.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

大数据spark、hasdoop 深度学习、机器学习算法的音乐平台用户情感分析系统设计与实现

大数据spark、hasdoop 深度学习、机器学习算法的音乐平台用户情感分析系统设计与实现

大数据spark、hasdoop 深度学习、机器学习算法的音乐平台用户情感分析系统设计与实现
阅读更多...
视频汇聚系统EasyCVR调用设备录像保活时视频流不连贯问题解决方案

视频汇聚系统EasyCVR调用设备录像保活时视频流不连贯问题解决方案

在使用EasyCVR过程中&#xff0c;有用户反馈调用设备录像保活功能时&#xff0c;出现视频流不连贯的情况。针对这一问题&#xff0c;我们经过排查与测试&#xff0c;整理出如下解决步骤&#xff0c;供开发者参考&#xff1a;具体解决步骤1&#xff09;先调用登录接口完成鉴权确…
阅读更多...
【保姆级喂饭教程】python基于mysql-connector-python的数据库操作通用封装类（连接池版）

【保姆级喂饭教程】python基于mysql-connector-python的数据库操作通用封装类（连接池版）

目录项目环境一、db_config.py二、mysql_executor.py三、test/main.py在使用mysql-connector-python连接MySQL数据库的时候&#xff0c;如同Java中的jdbc一般&#xff0c;每条sql需要创建和删除连接&#xff0c;很自然就想到写一个抽象方法&#xff0c;但是找了找没有官方标准的…
阅读更多...
【MCP服务】蓝耘元生代 | 蓝耘MCP平台来袭！DeepSeek MCP服务器玩转大模型集成

【MCP服务】蓝耘元生代 | 蓝耘MCP平台来袭！DeepSeek MCP服务器玩转大模型集成

【作者主页】Francek Chen 【专栏介绍】⌈⌈⌈人工智能与大模型应用⌋⌋⌋ 人工智能&#xff08;AI&#xff09;通过算法模拟人类智能&#xff0c;利用机器学习、深度学习等技术驱动医疗、金融等领域的智能化。大模型是千亿参数的深度神经网络&#xff08;如ChatGPT&#xff09…
阅读更多...
Spring Boot 整合 Minio 实现高效文件存储解决方案(本地和线上)

Spring Boot 整合 Minio 实现高效文件存储解决方案(本地和线上)

文章目录前言一、配置1.配置文件&#xff1a;application.yml2.配置类&#xff1a;MinioProperties3.工具类&#xff1a;MinioUtil3.1 初始化方法3.2 核心功能3.3 关键技术点二、使用示例1.控制器类&#xff1a;FileController2.服务类3.效果展示总结前言 Minio 是一个高性能的…
阅读更多...
【Unity3D实例-功能-镜头】第三人称视觉-镜头优化

【Unity3D实例-功能-镜头】第三人称视觉-镜头优化

这一篇我们一起来调整一下Cinemachine的第三人称视觉的镜头设置。一般用于ARPG角色扮演游戏的场景中。Unity里头&#xff0c;这种视角简直就是标配。来吧&#xff0c;咱们一起研究研究怎么调出这种视角效果&#xff01;目录&#xff1a;1.调整虚拟摄像机的Y轴2.调整虚拟摄像机的…
阅读更多...
二叉树算法之【中序遍历】

二叉树算法之【中序遍历】

目录 LeetCode-94题 LeetCode-94题 给定一个二叉树的根节点root&#xff0c;返回它的中序遍历结果。 class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result new ArrayList<>();order(root, result);return res…
阅读更多...
Android14的QS面板的加载解析

Android14的QS面板的加载解析

/frameworks/base/packages/SystemUI/src/com/android/systemui/statusbar/phone/CentralSurfacesImpl.java QS 面板的创建 getNotificationShadeWindowView()&#xff1a;整个systemui的最顶级的视图容器&#xff08;super_notification_shade.xml&#xff09;R.id.qs_frame &…
阅读更多...
解锁webpack核心技能（二）：配置文件和devtool配置指南

解锁webpack核心技能（二）：配置文件和devtool配置指南

一、配置文件webpack 提供的 cli 支持很多的参数&#xff0c;例如 --mode 。在我们平时的开发过程中&#xff0c;我们要学习很多的功能&#xff0c;这些很多都是可以用参数来完成的。那么后边就会导致参数越来越多&#xff0c;我们使用命令特别的不方便&#xff0c;所以我们会使…
阅读更多...
Gitlab+Jenkins+K8S+Registry 建立 CI/CD 流水线

Gitlab+Jenkins+K8S+Registry 建立 CI/CD 流水线

一、前言 DevOps是一种将开发&#xff08;Development&#xff09;和运维&#xff08;Operations&#xff09;相结合的软件开发方法论。它通过自动化和持续交付的方式&#xff0c;将软件开发、测试和部署等环节紧密集成&#xff0c;以提高效率和产品质量。在本篇博客中&#xf…
阅读更多...
【Linux】特效爆满的Vim的配置方法 and make/Makefile原理

【Linux】特效爆满的Vim的配置方法 and make/Makefile原理

一、软件包管理器 1、Linux下安装软件的常见方式&#xff1a; 1&#xff09;源代码安装——不推荐。 2&#xff09;rpm包安装——不推荐。 3&#xff09;包管理器安装——推荐 2、安装软件命令 # Centos$ sudo yum install -y lrzsz# Ubuntu$ sudo apt install -y lrzsz 3、卸…
阅读更多...
Spring Boot Actuator 监控功能的简介及禁用

Spring Boot Actuator 监控功能的简介及禁用

Spring Boot Actuator: Production-ready Features 1. 添加依赖 <dependencies><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-actuator</artifactId></dependency> </dependencie…
阅读更多...
Matlab（1）

Matlab（1）

一、基本操作1. matlab四则运算规则&#xff1a;先乘除后加减&#xff0c;从左到右2、对数和指数的表示sin(pi^0.5)log(tan(1))exp&#xff08;sin&#xff08;10&#xff09;&#xff09;3、类型&#xff1a;matlab变量默认为double4、who&whos&#xff1a;命令行输入who&…
阅读更多...
Kotlin Android 开发脚手架封装

Kotlin Android 开发脚手架封装

Kotlin Android 开发脚手架封装&#xff08;模块化版本&#xff09; 我将按照模块化设计原则&#xff0c;将脚手架拆分为多个文件&#xff0c;每个文件负责特定功能领域&#xff1a; 1. 核心初始化模块 文件路径: core/AppScaffold.kt object AppScaffold {lateinit var contex…
阅读更多...
Flutter 报错解析：No TabController for TabBar 的完整解决方案

Flutter 报错解析：No TabController for TabBar 的完整解决方案

目录 Flutter 报错解析&#xff1a;No TabController for TabBar 的完整解决方案 一、错误场景&#xff1a;当 TabBar 失去 "指挥官" 二、为什么 TabBar 必须依赖 Controller&#xff1f; 1. TabBar 与 TabController 的协作关系 2. 状态管理的核心作用 3. 实战…
阅读更多...
【24】C++实战篇——【 C++ 外部变量】 C++多个文件共用一个枚举变量，外部变量 extern，枚举外部变量 enum

【24】C++实战篇——【 C++ 外部变量】 C++多个文件共用一个枚举变量，外部变量 extern，枚举外部变量 enum

文章目录1 方法2 外部变量 应用2.1 普通外部全局变量2.2 枚举外部全局变量 应用2.2.2 枚举外部变量优化c多个文件中如何共用一个全局变量 c头文件的使用和多个文件中如何共用一个全局变量 C共享枚举类型给QML 1 方法 ①头文件中 声明外部全局变量&#xff1b; ②在头文件对…
阅读更多...
Linux SELinux 核心概念与管理

Linux SELinux 核心概念与管理

Linux SELinux 核心概念与管理一、SELinux 基本概念 SELinux 即安全增强型 Linux&#xff08;Security-Enhanced Linux&#xff09;&#xff0c;由美国国家安全局&#xff08;NSA&#xff09;开发&#xff0c;是一套基于强制访问控制&#xff08;MAC&#xff09;的安全机制&…
阅读更多...
Git 中**未暂存**和**未跟踪**的区别：

Git 中**未暂存**和**未跟踪**的区别：

文件状态分类 Git 中的文件有以下几种状态&#xff1a; 工作区文件状态&#xff1a; ├── 未跟踪 (Untracked) ├── 已跟踪 (Tracked)├── 未修改 (Unmodified) ├── 已修改未暂存 (Modified/Unstaged)└── 已暂存 (Staged)1. 未跟踪 (Untracked) 定义&#xff1a;Gi…
阅读更多...
前端1.0

前端1.0

目录 一、 什么是前端 二、 HTML 1.0 概述 2.0 注释 三、开发环境的搭建 1.0 插件 2.0 笔记 四、 常见标签&#xff08;重点&#xff09; 四、案例展示&#xff08;图片代码&#xff09; 五、CSS引入 一、 什么是前端 web前端 用来直接给用户呈现一个一个的网页 …
阅读更多...
Flutter镜像替换

Flutter镜像替换

一、核心镜像替换&#xff08;针对 Maven 仓库&#xff09; Flutter 依赖的 Google Maven 仓库&#xff08;https://maven.google.com 或 https://dl.google.com/dl/android/maven2&#xff09;可替换为国内镜像&#xff0c;常见的有&#xff1a;阿里云镜像&#xff08;推荐&am…
阅读更多...
最新文章

Copyright @ 2022~2023