【第三节】C/C++数据结构之栈与队列

目录

一、数据结构-栈

1.1 栈的定义

1.2 栈的 ADT (Abstract Data Type)

1.3 栈的顺序存储结构及实现

二、数据结构-队列

2.1 队列的定义

2.2 队列的 ADT

2.3 队列的顺序存储结构与实现

2.4 优先队列

2.5 各种队列异同点

一、数据结构-栈

1.1 栈的定义

栈(Stack)可以看成是一种特殊的线性表。

限定仅只能在表尾端进行插入和删除的线性表。
栈顶：表尾端被称之为栈顶。
栈底：和表尾相对应的另一端，称之为栈底。
时间有序表：LIFO （Last In First Out）后进先出特征的线性结构。

1e674f57d5df4273ae768853d2156b11.png

1.2 栈的 ADT (Abstract Data Type)

template <class ElemType> 
class AbsStack {public:AbsStack ( ) { }		  // 默认构造函数virtual ~ AbsStack ( ) {  } 	  // 析构函数virtual int IsEmpty ( ) const = 0;   // 判栈空吗？virtual int IsFull ( ) const = 0;      // 判栈满吗？virtual void MakeEmpty( ) = 0;    //将栈清空。virtual void Push ( const ElemType & X ) = 0;  //新结点进栈。virtual void Pop (  ) =  0;  // 栈顶结点出栈。virtual const ElemType & Top( ) const = 0;  // 取栈顶结点数据值。private:AbsStack( const AbsStack & ) {  } // 冻结复制另一堆栈的构造函数。
}；

1.3 栈的顺序存储结构及实现

与线性表类似，栈也有两种存储结构，即顺序存储和链表存储结构。
栈的顺序存储结构亦称顺序栈。
栈的顺序存储结构是利用一批地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针 top 指向栈顶元素的当前位置。
通常用一维数组来实现栈的顺栈存储，习惯上以数组下标小的一端做栈底，当top=0时为空栈。数据元素不断进栈时，栈顶指针top不断地加1，当top达到数组的最大下标值时为栈满。

dd66707323184d4087d01a6c12471936.png

顺序表示的栈的程序实现：

static const int InitStackSize = 10;
template <class ElemType> class Stack: public AbsStack<ElemType>  {
private:ElemType * Array;       //  存放结点的数组名。int top;	         //  top - 栈顶指针。int MaxSize;     //  栈内能够存放结点的最大个数，即栈的容量。void DoubleArray( int Max );	 // 更新数组的容量。public:Stack ( );             // 构造函数, 初始时构造大小为InitStackSize的栈。~Stack ( ) { delete [ ] Array; };	// 析构函数，释放占用的连续空间。void MakeEmpty ( ) { top = -1; };  // 将栈清空。int IsEmpty ( ) const { return top = = -1; };     //栈空为True,否则为False。int IsFull ( ) const { return top = = MaxSize-1; }; //栈满为True,否则为False。const ElemType & Top( ) const ;              // 读取栈顶结点。void Push ( const ElemType & X );    	        // 将X的值进栈。void Pop ( );                   		   // 栈顶结点出栈。const Stack & operator = ( const Stack & R );
}；template<class ElemType> 
Stack<ElemType> :: Stack( ) : top( -1), MaxSize(InitStackSize) {  //构造函数, 空间大小为MaxSizeArray = new ElemType[MaxSize];
}
template <class ElemType> const ElemType & Stack<ElemType> :: Top( ) const {// 对非空栈，读取栈顶结点并返回结点的值。Exception( IsEmpty( ),  ”Underflow:Satck is Empty!”);return Array[top];  
}
template <class ElemType> void Stack<ElemType>::Push ( const ElemType & X ) {   if  ( top + 1 = = MaxSize )	DoubleArray( 2 * MaxSize );Array[++top] = X;      	// 新结点放入新的栈顶位置。
}
template <class ElemType> void Stack<ElemType>::Pop() { //对非空栈,将栈顶结点出栈Exception( IsEmpty( ),  ”Stack is underflow!”);top--;	   
}template <class ElemType> 
const Stack<ElemType> & Stack<ElemType> :: operator = ( const Stack<ElemType> & R 						) {   if ( this = = &R )  return *this; delete [ ]Array; Array = new ElemType[R.MaxSize];   // 分配存储单元。top = R.top;  for( int j=0; j<= top; j++ )  Array[j] = R.Array[j];  // 逐个复制结点。return *this;
}
template <class ElemType> 
void  Stack<ElemType> :: DoubleArray( int Max ) {   ElemType * oldarr = Array;Exception( MaxSize≥Max, “New size is too small!”);Array = new ElemType[Max];for( int k = 0; k <= top; k++ ) Array[k] = oldarr[k]; 	// 逐个复制结点。MaxSize = Max;delete [ ] oldarr;return;
}

多栈共享一块顺序存储空间：栈顶指针指向实际栈顶的下一个单元。

5a8cefa60a10466ea4332701841d47a5.png

二个栈共享一块顺序存储空间：栈顶指针指向实际栈顶的下一个单元。指针相遇时，栈满。

7c12f37597ba4576aa4e1b7aa4e62d20.png

top 是栈顶指针。栈顶和栈底如图所示。

4faf281ea543483d8befaa5b2add298f.png

栈的 Push 操作：

4b06ab11f033470d9ff8b56b588ca236.png

6b64793c5e5443ab9104096710c8fe5f.png

栈的 Pop 操作：

790e5c83528545efa89c8a2c4220bce5.png

8050062353214a6ba8714d5127d4401d.png

二、数据结构-队列

2.1 队列的定义

队列(Queue)也是一种特殊的线性表。在现实中例子很多，如客户到银行办理业务往往需要排队，先来的先办理，晚来的则排在队尾等待。队列也有两种存储结构，即顺序存储和链表存储结构。下面主要讲顺序存储的实现。

在表的一端进行插入，而在另一端进行删除的线性表。
队尾：进行插入的一端。
队首：进行删除的一端。
时间有序表：FIFO （先进先出）特征的线性结构。

2.2 队列的 ADT

template <class ElemType>   class AbsQueue {
public:AbsQueue ( ) { } 		  // 默认构造函数virtual ~ AbsQueue ( ) {  } 	  // 析构函数virtual int IsEmpty ( ) const = 0;  // 判队空吗？virtual int IsFull ( ) const = 0;    // 判队满吗？virtual void MakeEmpty( ) = 0;  //将队清空。virtual void EnQueue( const ElemType & X ) = 0;  //新结点进队。virtual void DeQueue( ) =  0;    // 队首结点出队。virtual const ElemType & Front( ) const = 0;  // 取队首结点数据值。
private:AbsQueue ( const AbsQueue & ) {  } // 冻结复制另一队列的构造函数。}；

2.3 队列的顺序存储结构与实现

队列的表示

2e44941f9c744d11870aae4a87d464af.png

df63c904644443d7b497d136268c99a4.png

f6cfd49d044947058c1e51dbaf8ec967.png

出队时应先判队是否空：条件  rear == front
不空则出队，注意 front 是否会由最高下标跳至最低下标(循环)。


 进队时应先判队是否满：条件  ( ( rear + 1) % maxSize ) == front

不满则进队，注意 rear 是否会由最高下标跳至最低下标(循环)。

基本操作的实现程序:进队。

template <class ElemType>void Queue<ElemType>::EnQueue(const ElemType & x) {// 值为x的结点进队。if ( IsFull( ) )  DoubleQueue( );   Array[rear] = x; // 若队满，则数组容量扩大一倍。Increment( rear);    // rear 加 1;若为 MaxSize，则rear取0。 
}
int IsFull( ) const {return ( rear + 1) % MaxSize = = front ; }

8fbf14c183514035be714b352394d286.png

基本操作进队的实现程序：扩大数组容量

template <class ElemType>void Queue<ElemType>::EnQueue(const ElemType & x) {// 值为x的结点进队。if ( IsFull( ) )  DoubleQueue( );   Array[rear] = x;Increment( rear);
}template <class ElemType>
int IsFull( ) const {return ( rear + 1) % MaxSize = = front ; }	template <class ElemType> 
void Queue<ElemType>::DoubleQueue( )  {//重新创建数组单元个数多一倍的新数组，复制原队列中的结点。int NewSize = 2 * MaxSize; ElemType * old = Array;Array = new ElemType[NewSize];for ( int j = 0, k = front; k < rear; j++, Increment(k) ) Array[j] = old[k];front = 0;    // 新的队首指针。rear = j;  // 新的队尾指针。MaxSize = NewSize;  delete [ ]old; 
}

基本操作出队的实现程序：

template <class ElemType> void Queue<ElemType>::DeQueue( )  {//对于非空队列，将队首结点出队。Exception( IsEmpty( ),  ”Queue is underflow!”);Increment( front ); 
}
int IsEmpty() const {return front = = rear;}	//判断队列是否空.。为空返回True,否则返回False。

dc6f46763b314c5e87964c4490ba49f4.png

求队中结点的个数：( rear - front + MaxSize ) % MaxSize

front 和 rear 分别是队首和队尾指针。它们指示着真正的队首和真正的队尾结点。

6dff2b07e09249fc872ced16df7b5b0d.png

70b3b26d17c74184b9cd82e5a2b0032e.png

template <class ElemType> class Queue : public AbsQueue<ElemType>  {private:ListNode<ElemType> * front;	       //  队首指针。ListNode<ElemType> * rear;	       //  队尾指针。public:Queue ( ) : front(NULL), rear(NULL) { } // 构造函数: 队首指针和队尾指针初始化。~Queue ( ) { MakeEmpty( ); }	//析构函数，释放占用的连续空间。void MakeEmpty ( ); 		 // 将队列清空。int IsEmpty ( ) const { return front = = NULL; }  // 队空为True,否则为False。int IsFull ( ) const { return 0; } 	  // 总认为为False。const ElemType & Front ( ) const ; // 读取队首结点数据值。void EnQueue ( const ElemType & X );    // 将X的值进队。void DeQueue ( );                   		// 将队首结点出队。const Queue & operator = ( const Queue & R );}；

进队操作：

template <class ElemType> 
void Queue<ElemType>::EnQueue ( const ElemType & X ) {   if ( IsEmpty( ) )  front = rear= new ListNode <ElemType> ( X );else rear = rear->Next = new ListNode<ElemType> ( X );
}

c6db1f460b1547c7b58aa5d18b05e539.png

2.4 优先队列

优先权有序表：具有特征高优先权的结点将先离开的线性结构。和到达时刻无关。
实现方法：结点中处包含数据场外，还有本结点的优先权数。优先权数越小（如本书） ，优先级越高。或者优先权数越大，优先级越高。
顺序存储的优先队列：用数组

9a74669faed749bf92d60ddc21d08921.png

2.5 各种队列异同点

数据结构中普通队列、循环队列和优先队列的异同点如下：

相同点：

  1. 先进先出原则：普通队列和循环队列都遵循先进先出（FIFO）的原则，即最早进入队列的元素将最早被移除。优先队列虽然也遵循某种顺序，但其核心特点不在于FIFO，而是根据元素的优先级来决定出队的顺序。

  2. 基本操作：这些队列类型都支持基本的入队（在队列尾部添加元素）和出队（从队列头部移除元素）操作。

不同点：

  1. 存储和循环使用：

    • 普通队列：使用数组或链表来存储元素，当元素被移除后，其空间不会被再次利用，可能导致空间浪费。
    • 循环队列：通过逻辑上首尾相连的方式实现队列空间的循环利用，提高了存储空间的利用率。循环队列需要额外的机制来判断队列是满还是空1。
    • 优先队列：与普通队列和循环队列在存储空间使用上的主要区别在于其出队顺序。优先队列根据元素的优先级进行出队，而不是按照FIFO的原则。

  2. 出队顺序：

    • 普通队列和循环队列：按照元素进入队列的顺序进行出队。
    • 优先队列：出队顺序基于元素的优先级，优先级高的元素先出队2。

  3. 应用场景：

    • 普通队列和循环队列：常用于需要按照特定顺序处理元素的场景，如操作系统中的进程调度、广度优先搜索等3。
    • 优先队列：特别适用于需要根据优先级处理元素的场景，如任务调度、图像处理中的优先级渲染等34。

  4. 实现和性能：

    • 普通队列和循环队列：实现相对简单，性能稳定。循环队列在减少内存分配和释放的开销方面可能更优。
    • 优先队列：实现通常基于堆数据结构（如最大堆或最小堆），因此具有不同的性能特点。插入和删除元素的时间复杂度通常为O(logN)2。

总结来说，普通队列和循环队列主要在存储空间的利用和循环使用上有所不同，而优先队列则主要在元素的出队顺序和实现机制上与其他两种队列有所区别。这些队列类型各自适用于不同的应用场景和需求。

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

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

相关文章

Web3设计风格和APP设计风格

Web3设计风格和APP设计风格

Web3设计风格和传统APP设计风格在视觉和交互设计上有一些显著的区别。这些差异主要源于Web3技术和理念的独特性&#xff0c;以及它们在用户体验和界面设计中的具体应用。以下是Web3设计风格与传统APP设计风格的主要区别。北京木奇移动技术有限公司&#xff0c;专业的软件外包开…
阅读更多...
CSS（盒子模型，定位，浮动，扩展）

CSS（盒子模型，定位，浮动，扩展）

CSS 盒子模型&#xff1a;外边距&#xff1a;内边距&#xff1a;水平居中&#xff1a; 定位&#xff1a;相对定位&#xff1a;绝对定位&#xff1a;固定定位&#xff1a; 浮动&#xff1a;扩展&#xff1a; 盒子模型&#xff1a; 盒子模型(Box Model) 规定了元素框处理元素内容…
阅读更多...
2024最新python入门教程|python安装|pycharm安装

2024最新python入门教程|python安装|pycharm安装

前言&#xff1a;在安装PyCharm之前&#xff0c;首先需要明确PyCharm是一款功能强大的Python集成开发环境&#xff08;IDE&#xff09;&#xff0c;由JetBrains公司开发。PyCharm旨在通过提供智能代码补全、语法高亮、代码检查、快速导航和重构等丰富的编码辅助工具&#xff0c…
阅读更多...
恢复最近删除的照片！3个终极指南大揭秘！

恢复最近删除的照片！3个终极指南大揭秘！

亲爱的朋友们&#xff0c;你们有没有过这样的经历&#xff1a;一时手滑&#xff0c;不小心删除了手机里的重要照片&#xff0c;然后瞬间感觉自己的世界都要崩塌了&#xff1f;别担心&#xff0c;今天我就来给大家分享一下如何找回最近删除的照片&#xff0c;并介绍详细的方法和…
阅读更多...
详解Spring MVC

详解Spring MVC

目录 1.什么是Spring Web MVC MVC定义 2.学习Spring MVC 建立连接 RequestMapping 注解介绍及使用 获取单个参数 获取多个参数 获取普通对象 获取JSON对象 获取基础URL参数 获取上传文件 获取Header 获取Cookie 获取Session 总结 1.什么是Spring Web MVC 官⽅对于…
阅读更多...
AI 正在攻克难题——赋予计算机嗅觉

AI 正在攻克难题——赋予计算机嗅觉

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…
阅读更多...
MySQL 自定义函数（实验报告）

MySQL 自定义函数（实验报告）

一、实验名称&#xff1a; 自定义函数 二、实验日期&#xff1a; 2024年 6 月 1 日 三、实验目的&#xff1a; 掌握MySQL自定义函数的创建及调用&#xff1b; 四、实验用的仪器和材料&#xff1a; 硬件&#xff1a;PC电脑一台&#xff1b; 配置&#xff1a;内存&#…
阅读更多...
OpenCV学习 基础图像操作（十七）：泛洪与分水岭算法

OpenCV学习 基础图像操作（十七）：泛洪与分水岭算法

原理 泛洪填充算法和分水岭算法是图像处理中的两种重要算法&#xff0c;主要用于区域分割&#xff0c;但它们的原理和应用场景有所不同&#xff0c;但是他们的基础思想都是基于区域迭代实现的区域之间的划分。 泛洪算法 泛洪填充算法&#xff08;Flood Fill&#xff09;是一…
阅读更多...
中电金信：从规划到落地，中电金信全程陪伴式服务助力泛金融数字化转型

中电金信：从规划到落地，中电金信全程陪伴式服务助力泛金融数字化转型

在当前的全球经济和金融发展格局中&#xff0c;金融行业正经历着一场以数字化为核心的快速转型。中国银行业和保险业已经成功探索出一条数字化转型的路径&#xff0c;并积累了丰富的实践经验。然而&#xff0c;泛金融领域则仍处于数字化转型的初期阶段&#xff0c;其转型能力因…
阅读更多...
【案例实战】 基于OpenCV实现鹿茸面积计算

【案例实战】 基于OpenCV实现鹿茸面积计算

学习《人工智能应用软件开发》&#xff0c;学会所有OpenCV技能就这么简单&#xff01; 做真正的OpenCV开发者&#xff0c;从入门到入职&#xff0c;一步到位&#xff01; 有人在我得B站答疑群里发了下面的图&#xff1a; 问&#xff1a;如何计算鹿茸最外圈蜡皮面积占整个鹿茸…
阅读更多...
AI 入门指南二 ：AI提示词（Prompt）

AI 入门指南二 ：AI提示词（Prompt）

一&#xff0c;提示词的定义 提示词在中文中意为“触发”&#xff0c;在自然语言处理&#xff08;NLP&#xff09;的领域&#xff0c;它更接近于一个“心领神会”的概念&#xff0c;而非具有明确定义的术语。 简而言之&#xff0c;提示词是用户对大型语言模型的输入&#xff0…
阅读更多...
Centos 7部署NTP

Centos 7部署NTP

介绍 NTP是Network Time Protocol&#xff08;网络时间协议&#xff09;的简称&#xff0c;它是用来通过互联网或局域网将计算机时钟同步到世界协调时间&#xff08;UTC&#xff09;的协议。 安装 # yum安装 yum install -y ntp# 离线安装 #下载地址&#xff1a;https://mir…
阅读更多...
全球首款AR电脑上线，可投影100英寸屏幕

全球首款AR电脑上线，可投影100英寸屏幕

近日&#xff0c;Sightful公司推出了一款名为Spacetop G1的革命性笔记本电脑&#xff0c;将AR技术与传统笔记本电脑巧妙融合&#xff0c;打造出令人惊叹的全新办公体验。 全球首款AR电脑上线&#xff0c;可投影100英寸屏幕 不同于传统笔记本电脑依赖物理屏幕显示内容&#xff0…
阅读更多...
新手如何正确使用代理IP，一篇文章学会，包含实战案例

新手如何正确使用代理IP，一篇文章学会，包含实战案例

前言 一、代理IP1.1 什么是代理IP&#xff1f;1.2 代理ip分类1.3 代理IP的作用和优势 二、更换代理IP的方法2.1 重启路由器或光猫2.2 用拨号 vps 重拨更换动态IP代理。2.3 使用浏览器更换IP 三、IPIDEA代理的优势四、提取代理IP4.1 提取步骤4.2 浏览器使用代理IP 五、使用代理I…
阅读更多...
c#基础（）

c#基础（）

学习目标 了解&#xff1a;嵌套类&#xff0c;匿名类&#xff0c;对象初始化器 重点&#xff1a;类的定义以及对象&#xff0c;构造方法&#xff0c;this和static关键字 掌握&#xff1a;面向对象的概念&#xff0c;访问修饰符&#xff0c;垃圾回收 面向对象 面向对象的概…
阅读更多...
微信小程序毕业设计-在线订餐系统项目开发实战(附源码+论文)

微信小程序毕业设计-在线订餐系统项目开发实战(附源码+论文)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;微信小程序毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计…
阅读更多...
Flink系列一：flink光速入门 (^_^)

Flink系列一：flink光速入门 (^_^)

引入 spark和flink的区别&#xff1a;在上一个spark专栏中我们了解了spark对数据的处理方式&#xff0c;在 Spark 生态体系中&#xff0c;对于批处理和流处理采用了不同的技术框架&#xff0c;批处理由 Spark-core,SparkSQL 实现&#xff0c;流处理由 Spark Streaming 实现&am…
阅读更多...
期刊的分类与级别

期刊的分类与级别

在学术界&#xff0c;期刊的分类与级别构成了一个评价学术成果和学者贡献的重要标准&#xff0c;同时也是学术出版与学术交流的基础。然而&#xff0c;对于初涉学者来说&#xff0c;理解期刊的分类与级别可能并不直观。本文旨在提供一个系统性的解释&#xff0c;并阐述为何期刊…
阅读更多...
云南区块链商户平台发票助手成品

云南区块链商户平台发票助手成品

目录 1 概述2 功能对比3 项目演示图4 核心逻辑4.1智能赋码4.2 解密方法4.3 登录与检测4.4 发票金额大写转换4.5 检查登录是否失效4.6 验证码识别5 演示效果6 项目部署6.1 Web站点部署6.1.1 环境6.1.2 前端6.1.3 后端6.2 Docker部署6.2.1 构建镜像6.2.2 创建容器6.3.3 访问项目域…
阅读更多...
基于PHP+MySQL开发的一套游泳馆预约报名小程序开发源码模板

基于PHP+MySQL开发的一套游泳馆预约报名小程序开发源码模板

最近新开发了一套游泳馆线上预约报名小程序&#xff0c;其主要功能有预约功能&#xff0c;报名功能&#xff0c;支付功能&#xff0c;个人中心&#xff0c;订单管理&#xff0c;商品管理等等。 游泳馆预约报名小程序系统-运行环境 开发语言&#xff1a;PHP 数据库&#xff1a;M…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023