当前位置: 首页 > article >正文

数据结构---堆栈和列

一、堆栈

1.栈堆:具有一定操作约束的线性表;(只在一端做插入删除)

2.栈的顺序存储结构:

由一个一维数组和一个记录栈顶元素位置的变量组成。定义方式如下:

3.入栈操作:

注意:(1)top表示栈顶元素的下标,maxsize表示数组容量;

(2)要放入栈顶的上面,同时top加1;

4.出栈操作:

注意:(1)栈堆初始化时top为-1,即数组首元素之前的那个位置的下标;

5.一个数组实现两个堆栈:

堆栈初始化:

注意:top2代表数组最后一个元素之后位置的下标;

对两个堆栈的区别方法:引入标识tag:

出栈操作:(记得先检验是否为空)

6.堆栈的链式存储:

栈的链式存储结构实际上就是一个单链表,叫做链栈。插入和删除操作只能在链栈的栈顶进行。

(1)创建堆栈结构:

(2)创建堆栈:

(3)判断是否为空:

(4)入栈操作:

注意:最后才对s->next做处理;

(5)出栈操作:

注意:第一个赋值语句,是让firstcell指向s->next指向的位置,所以firstcell指向的是要删除的结点;

7.中缀转换为后缀:

8.堆栈的应用:

主要应用的是堆栈的特性:先来先用,后来后用;

二、队列

1.队列的顺序存储实现:

队列的顺序存储结构通常由一个一维数组和一个记录队列头元素的变量front以及一个记录队列尾元素位置的变量rear组成;

类比排队,队列元素的添加在尾,元素的删除在头;

队列结构创建:

具体位置表示:

2.顺环队列:

这样的位置排列会出现一个问题:

即无法知道队列是空的还是满的,相应的判断条件都是front=rear

解决办法:

(1)增加标记size,当增加元素时size+1,用来标识元素个数;

(2)仅仅使用n-1个数组空间,即少使用一个数组空间;

我们一般采用方法(2);

相应入队操作:

注意:其中的(ptrq->rear+1) % maxsize代表的是在顺环中,rear元素对应的下一个元素的位置下标;

出队操作:

记住:我们都是在头删除元素,在尾添加元素;

3.队列的链式存储结构:

结构创建:

注意:要额外创建一个结构体,一个存头部指针,一个存尾部指针;

结构图解:

出列操作:

这是一个不带头结点的队列,实际上,front指向的头结点一般为辅助结点(不是空节点),它不存储实际数据,只是为了方便后续插入、删除操作;


http://www.kler.cn/a/587671.html

相关文章:

  • 入门基础项目-前端Vue_02
  • JPom使用Docker方式构建SpringBoot项目详解
  • Word 小黑第27套
  • C#程序员接口调用工具与方法
  • 有关Spring 简介和第一个Spring案例:基于XML配置的IoC容器
  • 鸿蒙 @ohos.animator (动画)
  • 具身沟通——机器人和人类如何通过物理交互进行沟通
  • Ubuntu22.04 安装 Isaac gym 中出现的问题
  • oracle 中创建 socket客户端 监听数据库变动,返回数据给服务端!!!
  • 系统架构设计师—案例分析—数据库篇—关系型数据库设计
  • Java 并发编程——BIO NIO AIO 概念
  • [设计模式]1_设计模式概览
  • FastGPT原理分析-数据集创建第一步
  • RHCE(RHCSA复习:npm、dnf、源码安装实验)
  • 驾驭 DeepSeek 科技之翼,翱翔现代学习新天际
  • Harmony OS NEXT API 12核心API深度解析与开发实践
  • 《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(34)混元金斗装万物 - 0-1背包问题(二维DP)
  • Python 正则表达式模块 re
  • uniapp scroll组件下拉刷新异步更新数据列表
  • 基于SSM + JSP 的图书商城系统