数据结构----栈和队列

article/2025/10/15 22:13:01

xdm这玩意我不会导入,只能截图了。 

目录

栈篇

1.1栈

1.2.栈操作数据元素的两种动作:

2.代码实现

2.1初始化和销毁

2.2插入

2.3删除和判空

2.4返回栈顶值,计算栈长

队列篇

3.1队列

4.代码实现

4.1初始化和销毁和判空

4.2入列

4.3出列

4.4返回对首和队尾


栈篇

1.1栈

线性表的一种特殊的存储结构。与学习过的线性表的不同之处在于栈只能从表的固定一端对数据进行插入和删除操作,另一端是封死的。由于栈只有一边开口存取数据,称开口的那一端为“栈顶”,封死的那一端为“栈底”(类似于盛水的木桶,从哪进去的最后还得从哪出来)。

1.2.栈操作数据元素的两种动作:

  1. 数据元素用栈的数据结构存储起来,称为“入栈”,也叫“压栈”。
  2. 数据元素由于某种原因需要从栈结构中提取出来,称为“出栈”,也叫“弹栈”。

注意:栈遵循先进后出原则

1.3.栈的表示方式

既然栈也是线性表,那么它就同样有线性表的两种表示形式: 顺序(数组)和 链式栈。

但是,栈需要进行尾部的插入和删除,所以用顺序表实现比链表实现更好。

2.代码实现

接下来就来实现这几大功能

#pragma once
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int SLDateType;
typedef struct Stack
{SLDateType* a;int top;     //栈顶int capacity;   //内存
}ST;//初始化
void StackInit(ST* ps);//销毁
void StackDestroy(ST* ps);//插入
void StackPush(ST* ps, SLDateType x);//删除
void StackPop(ST* ps);//返回栈顶值
void StackTop(ST* ps);//判断是否为空
bool StackEmpty(ST* ps);//计算栈长
int StackSize(ST* ps);

是不是你们的教科书上用的是双指针,或者,这个栈顶元素top也用指针了。但是这个还是不用指针更好一点,这个top既能表示栈顶,又能表示此时栈中所存储的数据个数,用途更多了。

2.1初始化和销毁

//初始化
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}//销毁
void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}

初始化和销毁就这两步啊给指针a赋值NULL,给剩下俩赋值为0,

 销毁就是释放指针,给那俩赋值为0。

2.2插入

//插入
void StackPush(ST* ps, SLDateType x)
{assert(ps);if (ps->top == ps->capacity)//判断容量{int newcapacity = (ps->capacity == 0 ? 4 : 2 * ps->capacity);//扩容后的容量SLDateType* tmp = realloc(ps->a, sizeof(SLDateType) * newcapacity);//扩容if (tmp == NULL){perror("realloc fail");exit(-1);}ps->capacity = newcapacity;ps->a = tmp;}ps->a[ps->top] = x ;//压入数据ps->top++;
}

最后一步压入数据是往结构体的a中压入的,又因为a是结构体指针,所以a中有top,所以把要插入的值存在top中,然后top++。

至于那个ps->a=tmp是把开辟好的地址给ps->a。 

2.3删除和判空

//删除
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}//判断是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

注意bool的头文件<stdbool.h>

2.4返回栈顶值,计算栈长

//返回栈顶值
SLDateType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];}//计算栈长
int StackSize(ST* ps)
{assert(ps);return ps->top;
}

队列篇

3.1队列

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

注意:队列是先进先出。

 一般我们用链来实现队列。

4.代码实现

typedef int QDataType;typedef struct QueueNode//链表
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue//队列
{QNode* head;QNode* tail;
}Queue;

4.1初始化和销毁和判空

//初始化
void QueueInit(Queue* pd)
{assert(pd);pd->head = pd->tail = NULL;
}//销毁
void QueueDestroy(Queue* pd)
{assert(pd);QNode* cur = pd->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pd->head = pd->tail = NULL;
}//判空
int QueueEmpty(Queue* pd)
{if (pd->head == NULL){return 1;}elsereturn 0;
}

4.2入列

//入列
void QueuePush(Queue* pd, QDateType x)//入列
{assert(pd);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){printf("malloc:falue");exit(-1);}newnode->data = x;newnode->next = NULL;//一个没有就进行插入if (pd->tail == NULL){pd->head = pd->tail = newnode;}else{pd->tail->next = newnode;pd->tail = newnode;}}

4.3出列

//出列
void QueuePop(Queue* pd)
{assert(pd);assert(!QueueEmpty(pd));if (pd->head->next == NULL){free(pd->head);pd->head = pd->tail = NULL;}else{QNode* next = pd->head->next;   //保存下一个节点地址,防止找不到free(pd->head);pd->head = next;}
}

4.4返回对首和队尾

//返回队首
void QueueFront(Queue* pd)
{assert(pd);assert(!QueueEmpty(pd));return pd->head->data;
}//返回队尾
void QueueBack(Queue* pd)
{assert(pd);assert(!QueueEmpty(pd));return pd->tail->data;
}

这个返回首尾是看一位大佬的代码的临时启发,希望对各位有用。

一些代码没加备注,我认为各位都学到了这了,这些代码随便就来,就没写来凑字了。

总结:栈和队列都能用顺序表(数组)和链表来表示。再想想,这俩不就是链表的特殊情况吗,栈是后进先出,队列是先进先出,而链表(单,循环)是啥时候进出都可以,这不就是长方形里的正方形吗。


http://chatgpt.dhexx.cn/article/bKGsuX7x.shtml

相关文章

栈(Stack)和队列(Queue)详解

1. 什么是栈&#xff0c;栈存储结构详解 同顺序表和链表一样&#xff0c;栈也是用来存储逻辑关系为 “一对一” 数据的线性存储结构&#xff0c;如图 1 所示。 图 1 栈存储结构示意图 从图 1 我们看到&#xff0c;栈存储结构与之前所学的线性存储结构有所差异&#xff0c;这缘…

栈和队列--栈

1、顺序栈 一组地址连续的存储单元加一个标识栈顶元素的指针。 #define MaxSize 50 //定义栈中最大元素个数 typedef struct{ ElemType data[MaxSize];//存放栈中的元素int Top;//栈顶指针 }SqStack;栈空&#xff1a;s.top-1 栈满&#xff1a;s.topMaxSize-1 栈长&#xff…

什么是栈?什么是队列?栈与队列的特点

栈 栈&#xff08;Stack&#xff09;是限定在仅在表尾插入的线性表。 因此对于栈来说&#xff0c;表尾具有特殊的含义。我们把表尾称作栈顶&#xff08;top&#xff09;&#xff0c;把表头称作栈底&#xff08;bottom&#xff09;。不含元素的栈称为空栈。 想象一下进栈的顺序…

栈和队列——相关例题

文章目录 一、栈例题——模拟栈具体实现1. 模板1.1 代码注解1.2 实现代码 2. STL2.1 代码注解2.2 实现代码 二、栈例题——表达式求值具体实现1. 实现思路2. 代码注解3. 实现代码 三、单调栈例题——单调栈具体实现1. 实现思路2. 实现代码 四、队列例题——模拟队列具体实现1. …

【栈和队列】

大家好,这里是针对栈和队列做的一些总结归类,主要是介绍了栈和队列的相关操作,特意整理出来一篇博客供我们一起复习和学习,如果文章中有理解不当的地方,还希望朋友们在评论区指出,我们相互学习,共同进步! 文章目录 一&#xff1a;栈1.1 栈的概念及结构1.2 栈的实现1.3 典型案例…

栈、队列

顺序栈&#xff0c;即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素&#xff0c;同时附设指针top指示栈项元素在顺序栈中的位置。通常的习惯做法是以top&#xff1d;0表示空栈&#xff0c;鉴于C语言中数组的下标约定从0开始&#xff0c;则当以C…

栈、队列、数组

栈 定义 #include <stdio.h>/* 栈只允许在栈顶插入删除操作的线性表Last Insert First Out. */// 顺序栈#define MaxSize 10typedef struct {int data[MaxSize]; // 静态数组存放栈元素int top; // 栈顶指针 } SqStack; 栈顶指针指向栈顶元素的栈 空为-1 // 栈顶指针指…

使用SQL进行两个表关联查询(inner)

结果显示 公司类型表 公司表 实现方式 SELECTt_company.id,cName, typeName, cDescribe, t_company.modifyTime, t_company.createTime FROMt_company INNER JOIN t_company_type ON t_company.cType t_company_type.id代码解析 SELECT 显示字段,如果两个表都有字段,则需要…

sql进行两个关联表,根据其中一个表的一个属性进行条件查询查询

我最近遇到了表的查询,但是通过查询发现,网上的sql的大神,写的文章到底是什么玩意? 我打算自己写一个sql专栏,特意讲解sql的使用,来帮助大家 这篇文章技术指导为sql进行两个关联表,根据其中一个表的一个属性进行条件查询查询 假设只有两张表,其中一张表最后一个外键连…

SQL关联查询详解,SQL JOIN详解

关联查询&#xff0c;也称为多表查询&#xff0c;指两个或更多个表一起完成查询操作。 前提条件&#xff1a;这些一起查询的表之间是有关系的&#xff08;一对一、一对多&#xff09;&#xff0c;它们之间一定是有关联字段&#xff0c;这个关联字段可能建立了外键&#xff0c;也…

SQL-多表关联查询详解

为了在工作中能更顺利的使用多表关联查询&#xff0c;今天这篇博客就写这个内容了。 在讲解多表关联查询之前&#xff0c;先生成测试表。 登录scott用户&#xff0c;运行以下语句生成测试表。 create table ex1 as select * from emp; create table ex2 as select * from dept…

Mysql如何对两张表的相同字段,同时查询两张数据表

前言 假设现在有两张数据表 表1如下&#xff1a; 表2如下&#xff1a; 表1和表2同时都再mysql的情况下&#xff0c;只有他们的uuid是一样的&#xff0c;其他字段信息不同&#xff0c;现在需要用sql语句根据uuid&#xff0c;同时将符合要求的数据查询出来&#xff0c;怎么做呢&…

SQL- join多表关联

一、SQL 连接(JOIN) 1、笛卡尔积 &#xff08;1&#xff09;当多张表进行连接查询&#xff0c;没有任何条件限制的时候&#xff0c;最终查询结果条数&#xff0c;是多张表条数的乘积 如A表15条&#xff08;行&#xff09;数据&#xff0c;B表20条&#xff08;行&#xff09;…

SQL语言多表关联查询

新建两张表&#xff1a; 表1&#xff1a;student 截图如下&#xff1a; 表2&#xff1a;course 截图如下&#xff1a; &#xff08;此时这样建表只是为了演示连接SQL语句&#xff0c;当然实际开发中我们不会这样建表&#xff0c;实际开发中这两个表会有自己不同的主键。&…

[转载]静息态fMRI、DTI、VBM

[转载]静息态fMRI、DTI、VBM (2014-06-19 19:00:15) 转载▼ 标签&#xff1a; 转载 分类&#xff1a; fMRI-EEG 原文地址&#xff1a;静息态fMRI、DTI、VBM作者&#xff1a;426l 一、 简介 1、静息态fMRI数据处理学习内容 BOLD-fMRI技术自1990年发明至今&#xff0c;已经成…

用FSL进行VBM统计分析

用FSL进行VBM统计分析 总体步骤概览1.准备数据1.1 T1数据格式1.2 Template_list查看数据 2.剥头皮&#xff1a;fslvbm_1_bet3.数据分割生成模板&#xff1a;fslvbm_2_template4.后处理&#xff08;标准化、调制、平滑&#xff09;&#xff1a;fslvbm_3_proc5.统计检验5.2查看结…

[spm操作] VBM分析中,modulation的作用

本帖作为 《用Matlab和SPM批量处理被试的经验总结》 的一部分 目录贴请见 http://home.52brain.com/forum.ph ... 1&extra#pid158525 在VBM分析中&#xff0c;通常都有一个modulation的选项&#xff0c;有些滴友对这个步骤的作用有点不太理解。 我先举一个例子&#xff…

不同的工具包对Voxel-based morphometry (VBM)计算结果的影响

​《本文同步发布于“脑之说”微信公众号&#xff0c;欢迎搜索关注~~》 前期大量的MRI研究已经表明&#xff0c;精神分裂患者很多脑区的局部灰质体积&#xff08;regional grey matter volume&#xff09;出现异常变化&#xff0c;但是这些研究的结果似乎并不一致。而这种结果…

如何提取差异脑区的灰质体积与临床量表算相关?——基于体素的形态学方法(VBM)

基于体素的形态学方法(VBM)是分析大脑解剖学(结构)差异最常用方法之一, 其通过给大脑volume逐体素打标签(分类)的方式来进行组织分割,过程高度自动化,比传统的基于ROI先验假设的分析方式得到的结果,更加具有稳定性和可重复性。VBM可以定量地测量出脑组织中各组织成分的…