程序员经验分享-hwhale

CH3-栈和队列

2023-11-17

文章目录

3.1栈和队列的定义和特点

  • 栈和队列是两种常用的、重要的数据结构
  • 栈和队列是限定插入和删除只能在表的“端点”进行的线性表

20220110191610

20220110190514

20220110190827

20220110191732

栈的应用

20220110191159

队列的应用

  • 由于队列的操作具有先进先出的特性，使得队列成为程序设计中解决类似排队问题的有用工具。
    • 脱机打印输出，按申请的先后顺序依次输出
    • ·多用户系统中，多个用户排成队，分时地循环使用CPU和主存
    • 按用户的优先级排成多个队，每个优先级一个队列
    • 实时控制系统中，信号按接收的先后顺序依次处理
    • 网络电文传输，按到达的时间先后顺序依次进行

3.1.1栈的定义和特点

20220110192515

20220110192933

20220110195938

20220110200046

20220110200457

20220110200629

20220110200742

3.1.2队列的定义和特点

20220110200933

20220110201032

3.2案例引入

案例3.1 :进制转换

20220110201151

20220110205307

案例3.2:括号匹配的检验

20220110205721

案例3.3:表达式求值

20220110205922

20220110210221

案例3.4∶舞伴问题

幻灯片30

3.3栈的表示和实现

3.3.1抽象数据类型定义

20220110210836

幻灯片33

由于栈本身就是线性表，于是栈也有顺序存储和链式存储两种实现方式

  • 栈的顺序存储—顺序栈
  • ·栈的链式存储—链栈

3.3.2顺序栈

20220111103055

20220111103258

使用数组作为顺序栈存储方式的特点:

​ 简单方便、但易产生溢出（数组大小固定)

  • 上溢（overflow): 栈已经满，又要压入元素

    • 注:上溢是一种错误，使问题的处理无法进行;

  • 下溢(underflow): 栈已经空，还要弹出元素

    • 而下溢一般认为是—种结束条件，即问题处理结束。

顺序栈的表示

#define MAXSIZE 100
typedef struct{
    SElemType *base;	//栈底指针
    SElemType *top;		//栈顶指针
    int stacksize;		//栈可用最大容量
}SqStack;

20220111104038

【算法3.1】初始化

Status InitStack(SqStack &S){//构造一个空栈
    S.base = new SElemType[MAXSIZE];
    //或S.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType));
    if (!S.base) exit (OVERFLOW);	//存储分配失败
    S.top= S.base;					//栈顶指针等于栈底指针
	S.stacksize = MAXSIZE;
	return OK;
}

【算法补充】判断栈是否为空

Status StackEmpty(SqStack S)
   // 若栈为空，返回TRUE;否则返回FALSE
    if (S.top == S.base)
    	return TRUE;
	else
    	return FALSE;
}

【算法补充】求栈长

int StackLength( SqStack S)
{
    return S.top - S.base;
}

【算法补充】清空

Status ClearStack( SqStack S ) {
    if( S.base ) 	S.top = S.base;
    return OK;	
}

【算法补充】销毁

Status DestroyStack( SqStack &S ){
    if(S.base ) {
        delete S.base ;
        S.stacksize = O;
        S.base = S.top = NULL;
    }
    return OK;
}

【算法3.2】入栈

  • (1)判断是否栈满，若满则出错（上溢)
  • (2)元素e压入栈顶
  • (3)栈顶指针加1
Status Push( SqStack &S, SElemType e) {
    if( S.top - S.base== S.stacksize )//栈满
   		return ERROR;
    *S.top++=e;				//*S.top=e;	S.top++;
	return OK;
}

【算法3.3】出栈

  • (1)判断是否栈空，若空则出错（下溢)
  • (2)获取栈顶页元素
  • (3)栈顶指针减1
Status Pop(SqStack &S, SElemType &e){
//若栈不空，则删除S的栈顶无素，用e返回其值，并返回OK;否则返回ERROR
    if(S.top == S.base)		//等价于if(StackEmpty(S))
        return ERROR;
    e = *--S.top;			//--S.top;	e=*S.top; 
    retum OK;
}

3.3.3链栈

typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
} StackNode,*LinkStack;LinkStack S;

20220111111242

【算法3.5】初始化

void lnitStack(LinkStack &S ) {//构造一个空栈，栈顶指针置为空
	S=NULL;
	return OK;
}

【补充算法】判断栈是否为空

Status StackEmpty(LinkStack S)
    if (S==NULL) return TRUE;
    else return FALSE;
}

【算法3.7】出栈

Status Pop (LinkStack &S,SElemType &e){
    if (S==NULL)	return ERROR;
    e = S-> data;
    p = S;
    S = S-> next;
    delete p;
    return OK;
}

【算法3.8】取栈顶元素

SElemType GetTop(LinkStack S) {
    if (S!=NULL)	
    	return S->data;
}

3.4栈与递归

递归的定义

  • 若一个对象部分地包含它自己 ，或用它自己给自己定义，则称这个对象是递归的;

  • 若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。

    • 例如:涕归求n的阶乘

      long Fact ( long n ) {
    if ( n == 0) 	return 1;
    else 	return n * Fact (n-1);
}

  • 以下三种情况常常用到递归方法

    • 递归定义的数学函数
    • ·具有递归特性的数据结构
    • 可递归求解的问题

20220111113423

20220111113526

20220111113604

递归问题——用分治法求解

  • 分治法: 对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解
  • 必备的三个条件
    • 1、能将一个问题转变成、个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的
    • 2、可以通过上述转化而使白题简化
    • 3、必须有一个明确的递归出口，或称递归的边界

20220111113924

20220111113955

20220111114105

20220111114345

20220111114553

20220111114820

递归的优缺点

20220111114943

20220111115051

20220111115104

20220111115134

20220111115151

20220111115504

3.5队列的表示和实现

20220111120727

3.3.1抽象数据类型定义

20220111121047

3.5.2顺序队列

  • 队列的物理存储可以用顺序存储结构，也可用链式存储结构, 队列的存储方式也分为两种，即顺序队列和链式队列。

  • 队列的顺序表示——用一维数组base[MAXQSZE]

#define MAXQSIZE 100//最大队列长度
Typedef struct {
    QElemType *base;//初始化的动态分配存储空间
    int front;		//头指针
    int rear		//尾指针
}SqQueue;

20220111131411

20220111131526

解决假上溢的方法——引入循环队列

20220111131746

20220111132036

20220111132127

20220111132319

类型定义

#define MAXQSIZE 100//最大队列长度
typedef struct {
    QElemType *base;//动态分配存储空间
    int front;		//头指针，若队列不空，指向队列头元素
    int rear;		//尾指针，若队列不空，指向队列尾元素的下一个位置
} SqQueue;

【算法3.4】初始化

Status lnitQueue (SqQueue &Q){
    Q.base =new QElemType[MAXQSIZE]		//分配数组空间
    //Qbase = (QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
    if(!Q.base)exit(OVERFLOW);			//存储分配失败
    Q.front=Q.rear=O;					//头指针尾指针置为0，队列为空
    return OK;
}

【算法3.5】求队长

int QueueLength (SqQueue Q){
    return (Q.rear-Q.front+MAXQSIZE)% MAXQSIZE );
}

20220111133516

【算法3.6】入队

Status EnQueue(SqQueue &Q, QElemTypee){
    if((Q.rear+1)%MAXQSIZE==Q.front)	return ERROR;		//队满
    Q.base[Q.rear]=e;				//新元素加入队尾
    Q.rear=(Qrear+1)%MAXQSIZE;	    //队尾指针+1
    return OK;
}

【算法3.7】出队

Status DeQueue (SqQueue &Q,QElemType &e){
    if(Q.front==Qrear)	 return ERROR;	//队空
    Q.base[Q.front];						//保存队头元素
    Q.front=(Q.front+1)%MAXQSIZE;		//队头指针+1
    return OK;
}

【算法3.8】取队头元素

SElemType GetHead(SqQuere Q){
    if(Q.front!=Q.rear)			//队列不为空
    	return Q.base[Q.front];	//返回队头指针元素的值，队头指针不变
}

3.5.3链式队列

20220111134657

#define MAXQSIZE 100	//最大队列长度
typedef struct Qnode {
    QElemType data;
    struct Qnode *next;
}QNode,*QuenePtr;

typedef struct {
    QuenePtr front;//队头指针
    QuenePtr rear;//队尾指针
}LinkQueue;

20220111135210

【算法3.4】初始化

20220111140055

Status InitQueue (LinkQueue &Q){
    Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode));
    if(!Q.front) 	exit(OVERFLOW);
    Q.front->next=NULL;
    return OK;
}

【算法补充】销毁

20220111140145

Status DestroyQueue (LinkQueue &Q){
    while(Q.front){
        p=Q.front->next;	//Q.rear=Q.front->next; 
        free(Q.front);		//free(Q.front);
        Q.front=p;			//Q.front=Q.rear;
    }
    return OK;
}

【算法3.6】入队

20220111140622

Status EnQueue(LinkQueue &Q, QElemType e){
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p) 	exit(OVERFLOW);
    p->data=e;	 p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    return OK;
}

【算法3.7】出队

20220111140820

Status DeQueue (LinkQueue &Q,QElemType &e){
    if(Q.front==Q.rear)		 return ERROR;
    p=Q.front->next;
    e=p->data;
    Q.front->next = p->next;
    if(Q.rear==p)	Q.rear=Q.front;	
    delete p;
    return OK;
}

【算法3.8】取队头元素

Status GetHead (LinkQueue Q, QElemType &e){
    if(Q.front==Q.rear) 	return ERROR;
	e=Q.front->next->data;
	return OK;
}

ueue &Q, QElemType e){
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e; p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}




### 【算法3.7】出队

[外链图片转存中...(img-QNfcYgtG-1641895287115)]

```c
Status DeQueue (LinkQueue &Q,QElemType &e){
    if(Q.front==Q.rear)		 return ERROR;
    p=Q.front->next;
    e=p->data;
    Q.front->next = p->next;
    if(Q.rear==p)	Q.rear=Q.front;	
    delete p;
    return OK;
}

【算法3.8】取队头元素

Status GetHead (LinkQueue Q, QElemType &e){
    if(Q.front==Q.rear) 	return ERROR;
	e=Q.front->next->data;
	return OK;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

算法与数据结构第2版（严蔚敏）

栈

队列

数据结构

CH3-栈和队列 的相关文章

  • javascript代码混淆的原理

    如何对JavaScript进行保护 代码压缩 去除空格 换行等 代码加密 eval eval可以将其中的参数按照JavaScript的的语法进行解析并执行 其实就是将JavaScript的代码变成了eval的参数其中的一些字符会被按照特定的

随机推荐

  • Realtime_Multi-Person_Pose_Estimation demo.ipynb代码注释

    该部分可以帮助很好的理解论文的实现部分 源码地址 https github com ZheC Realtime Multi Person Pose Estimation 论文地址 https arxiv org abs 1611 08050

  • CVPR 2022

    点击下方卡片 关注 CVer 公众号 AI CV重磅干货 第一时间送达 作者 弃之 已授权转载 源 知乎 编辑 CVer https zhuanlan zhihu com p 478079763 PR一下我们在CVPR 2022上的pape

  • 12年经验资深产品经理领你从“产品小白”走向“产品大牛”

    当今社会 智能音箱 智能机器人 智能可穿戴设备等人工智能产品已经开始逐渐普及 而人工智能产品经理却少之又少 查看智联 拉勾 猎聘等多个招聘网站中企业招聘人工智能产品经理的岗位要求 发现不同公司在招聘人工智能产品经理时的标准都不一样 有些偏重

  • 单点登录的实现

    单点登录一般需要至少两个站 一个登录站 一个接入站 确切的说应该是N个接入站 各个站需要实现的功能如图 简单说明 登录站提供登录页面和退出功能 并提供用户信息的获取服务 接入站需要提供对应的登录成功回写服务 目的是为了存储本地登录信息 可以

  • VUE element-ui之el-popover弹出框在局部全屏下不显示问题及弹框、小箭头背景修改

    问题 局部全屏后el popover弹出框失效 解决方法

  • PackagesNotFoundError: The following packages are not available from current channels

    因为要用到lifelines 包 在cmd中使用conda install lifelines 显示如下错误 PackagesNotFoundError The following packages are not available fr

  • uniapp 离线打包webview无法上传图片问题

    离线打包上传文件选择文件上传失败 从文件点击选择的内容可以上传成功 其他路径进去上传失败 查了好久是因为清单文件的目标版本targetSdkVersion 写了29 改成28或者不填就好了

  • SpringBoot + Spring Security多种登录方式：账号+微信网页授权登录

    大家好 我是宝哥 一 概述 实现账号用户名 微信网页授权登录集成在Spring Security的思路 最重要的一点是要实现微信登录通过Spring Security安全框架时 不需要验证账号 密码 二 准备工作 要实现该功能 首先需要掌握

  • win10台式机rtl8188eu(FW 150 UM V2.0)无线网卡无法连接wifi（无法连接到这个网络）

    同一个网卡 同一个WiFi 在笔记本上能用 能连接wifi 但是在台式机上就不能连接wifi 提示 无法连接到这个网络 如下图 win10版本都是1903 尝试换各种驱动都没解决 最后更新主板bios 然后从微星主板客服得知可以问京东自营的

  • 高校评优评奖管理系统

    这是一个高校评优评奖管理系统 供大家参考学习 不懂的地方可以联系本人 1 管理员登陆 学生申请 管理员后台 评优记录 数据维护 信息统计 系统设置 学生申报 微信 17777665965 QQ 1161724197

  • 纯 CSS 开关切换按钮

  • brk和sbrk及内存分配函数相关

    brk和sbrk主要的工作是实现虚拟内存到内存的映射 在GNUC中 内存分配是这样的 每个进程可访问的虚拟内存空间为3G 但在程序编译时 不可能也没必要为程序分配这么大的空间 只分配并不大的数据段空间 程序中动态分配的空间就是从这 一块分配

  • 【Spark系列2】reduceByKey和groupByKey区别与用法

    在spark中 我们知道一切的操作都是基于RDD的 在使用中 RDD有一种非常特殊也是非常实用的format pair RDD 即RDD的每一行是 key value 的格式 这种格式很像Python的字典类型 便于针对key进行一些处理

  • 微前端--qiankun原理概述

    demo放最后了 一 微前端 一 微前端概述 微前端概念是从微服务概念扩展而来的 摒弃大型单体方式 将前端整体分解为小而简单的块 这些块可以独立开发 测试和部署 同时仍然聚合为一个产品出现在客户面前 可以理解微前端是一种将多个可独立交付的小

  • Android 热补丁动态修复框架小结

    转载 http blog csdn net xdgaozhan article details 51848570 一 概述 最新github上开源了很多热补丁动态修复框架 大致有 https github com dodola HotFix

  • Python与OpenCV（三）——基于光流法的运动目标检测程序分析

    光流的概念是指在连续的两帧图像当中 由于图像中的物体移动或者摄像头的移动而使得图像中的目标形成的矢量运动轨迹叫做光流 本质上光流是个向量场 表示了一个像素点从第一帧过渡到第二帧的运动过程 体现该像素点在成像平面上的瞬时速度 而当我们对图像当

  • oracle 游标 上限,ORA-01000: 超出打开游标的最大数

    语言 java 数据库 oracle 开发中通过jdbc做批量删除对象时 出现了如下异常 java sql SQLException ORA 01000 超出打开游标的最大数 at oracle jdbc driver T4CTTIoer

  • UE5_创建C++项目报错

    UE官方VS安装推荐 https docs unrealengine com 4 26 en US ProductionPipelines DevelopmentSetup VisualStudioSetup UE5报错 A fatal e

  • 下拉框怎么用ajax实现添加功能,ajax实现动态下拉框示例

    许多页面上都涉及有下拉框 即select标签 对于简单的下拉框 被选择的数据是不需要改变的 我们可以用写死 这样下拉框的数据永远都是那几条 示例 信息一 信息二 信息三 信息四 但是有些项目或者工程是需要将数据库中的数据呈现出来并提供选择的

  • CH3-栈和队列

    文章目录 3 1栈和队列的定义和特点 栈的应用 队列的应用 3 1 1栈的定义和特点 3 1 2队列的定义和特点 3 2案例引入 案例3 1 进制转换 案例3 2 括号匹配的检验 案例3 3 表达式求值 案例3 4 舞伴问题 3 3栈的表示

热门标签