【第三节】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) {  
		//构造函数, 空间大小为MaxSize
     	Array = 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。

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

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

硬件高效的线性注意力机制Gated Linear Attention论文阅读

硬件高效的线性注意力机制Gated Linear Attention论文阅读

0x0. 前言 上篇文章 flash-linear-attention中的Chunkwise并行算法的理解 根据GLA Transformer Paper&#xff08;https://arxiv.org/pdf/2312.06635 作者是这位大佬 sonta&#xff09;通过对Linear Attention的完全并行和RNN以及Chunkwise形式的介绍理解了Linear Attention的…
阅读更多...
精酿啤酒新风尚，FENDI CLUB盛宴启幕，品质生活触手可及

精酿啤酒新风尚，FENDI CLUB盛宴启幕，品质生活触手可及

随着现代人对生活品质的追求日益提升&#xff0c;精酿啤酒作为一种新兴的生活方式&#xff0c;正逐渐引领潮流。在这个背景下&#xff0c;FENDI CLUB的盛宴盛大开启&#xff0c;为广大消费者带来了一场别具一格的品质生活体验。 一、精酿啤酒的崛起 精酿啤酒以其独特的口感、…
阅读更多...
vscode 搜索框乱码

vscode 搜索框乱码

vscode 搜索文件夹 搜索txt文件 ignore取消 搜索中文乱码 https://zhuanlan.zhihu.com/p/661347670 文件 -》首选项-》设置 搜索encoding -》设置 simpified chinese 中文插件
阅读更多...
HTML5+CSS3+JS小实例：网格图库

HTML5+CSS3+JS小实例：网格图库

实例：网格图库 技术栈：HTML+CSS+JS 效果： 源码： 【HTML】 <!DOCTYPE html> <html lang="zh-CN"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0&…
阅读更多...
深入浅出mysql海量数据批量更新插入、批量查询

深入浅出mysql海量数据批量更新插入、批量查询

1. mysql的批量写 mysql 批量插入可以用下面这种&#xff0c;在values 之后跟上各种多个值列表。但这种写法可能导致sql长度超长、锁超时等问题。 insert into (field1,field1,field1,) values (value01,value02,value03),(value11,value12,value13),(value21,value22,value2…
阅读更多...
LLM推理加速原理（一）

LLM推理加速原理（一）

1.大语言模型的基本结构 transfomer block： 输入--->正则化-->qkv三个矩阵层（映射到三个不同空间中)---->q,k,v之后self attention进行三0合一---->线性映射，正则化。 2.大语言模型的推理 目前主流的语言大模型都采用decoder-only的结构，其推理过程由两部分…
阅读更多...
ubuntu22.04编译OpenCV4.9(带contrib-4.9.0）

ubuntu22.04编译OpenCV4.9(带contrib-4.9.0）

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;4.9.0 opencv_contrib版本&#xff1a;4.9.0 源码下载 OPenCV4.9.0下载地址&#xff1a;https://github.com/opencv/opencv/releases/tag/4.9.0 如下图所示&#xff1a; 按箭头所指点击下载source code(tar.gz)文件到…
阅读更多...
TG-5510CA温补晶振用于GPS应用

TG-5510CA温补晶振用于GPS应用

随着现代社会对精准定位和导航需求的不断增加&#xff0c;GPS&#xff08;全球定位系统&#xff09;已成为我们日常生活和各行各业中不可或缺的一部分。无论是在智能手机、汽车导航、无人机飞行控制&#xff0c;还是在精密的科学研究和军事应用中&#xff0c;GPS系统都扮演着至…
阅读更多...
【杂谈】AIGC之Stable Diffusion：AI绘画的魔法

【杂谈】AIGC之Stable Diffusion：AI绘画的魔法

Stable Diffusion&#xff1a;AI绘画的魔法 引言 在AI的世界里&#xff0c;Stable Diffusion就像一位魔法师&#xff0c;它能够将我们脑海中的幻想&#xff0c;用画笔一一描绘出来。今天&#xff0c;就让我们一探这位魔法师的奥秘&#xff0c;看看它是如何从无到有&#xff0…
阅读更多...
clickhouse学习笔记（一）入门与安装

clickhouse学习笔记（一）入门与安装

目录 一 、入门 简介 核心特性包括 1.1 列式存储 1.2 原生压缩 1.3 向量化执行引擎 1.4 DBMS 功能 1.5 分布式处理 1.6 高吞吐写入能力 1.7 实时分析 1.8 SQL支持 1.9 高度可扩展 1.10 数据分区与线程级并行 1.11 应用场景 1.12 不适用场景 二、ClickHouse单机版…
阅读更多...
【Qt】定时器播放多张图片，动画效果

【Qt】定时器播放多张图片，动画效果

1. 效果 2. 代码 2.1 头文件 #ifndef WIDGET_H #define WIDGET_H#include <QWidget>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);~Widget();void initGif(QS…
阅读更多...
MT3051 区间gcd

MT3051 区间gcd

思路&#xff1a; ST表&#xff0c;ST表模板可参考MT3024 maxmin 注意&#xff0c;这里使用快读快写避免超时 代码&#xff1a; #include <bits/stdc.h> using namespace std; const int N 1e6 10; int n, m, a[N], mn[N][20], Lg[N], l, r, ans; void pre() {Lg[1…
阅读更多...
python中的循环语句

python中的循环语句

while循环 基本语法格式 while 条件&#xff1a; 循环体 条件为真&#xff0c;则执行循环体代码 条件为假&#xff0c;则结束循环 打印 1-10的整数 死循环有时候也是必须的&#xff0c; while语句的语法&#xff1a; &#xff08;1&#xff09;变量的初始化&#xff0c;…
阅读更多...
Clo3D导出服装动画，使用Unity3D展示

Clo3D导出服装动画，使用Unity3D展示

1.前言 Clo3D是一款应用于时装行业的3D服装设计软件,其强大的布料模拟算法可在3D空间中实现设计、制版、试衣和走秀,大幅提升数字作品逼真度和制作效率。为了让服装动画效果展示在Unity3D上模拟效果&#xff0c;需要Clo3D模拟出逼着的衣服动画。总体流程为Clo3D - Mixamo -Blen…
阅读更多...
The 18th Northeast Collegiate Programming Contest（5/9/13）

The 18th Northeast Collegiate Programming Contest（5/9/13）

心得 赛中ac&#xff1a;5&#xff0c;目前ac&#xff1a;9&#xff0c;题目总数&#xff1a;13 中档可做题还是很多的&#xff0c;可惜遇到了难绷的queueforces&#xff0c; 最后15min才判出来&#xff0c;oi赛制5wa4遗憾离场&#xff0c;赛后把几个题都给调过了&#xff0…
阅读更多...
遗传算法+神经网络！基于遗传-神经网络(GA-BP)算法的光伏出力预测程序代码！

遗传算法+神经网络！基于遗传-神经网络(GA-BP)算法的光伏出力预测程序代码！

前言 准确地预测光伏发电出力对于电力系统运营和稳定性至关重要。随着预测技术的不断进步&#xff0c;越来越多的研究者逐渐意识到遗传算法在优化神经网络在新能源出力预测中的潜力。遗传算法是一种模拟生物进化过程的优化算法&#xff0c;通过不断迭代和选择&#xff0c;搜索…
阅读更多...
期望18K，4年前端Cvte 视源股份一面挂

期望18K，4年前端Cvte 视源股份一面挂

一面 1、自我介绍&#xff1f;毕业的时候一直在 xx 公司&#xff0c;你基本都在做什么项目&#xff1f; 2、你讲一下你主要负责哪一块的&#xff1f;balabala 3、你们的 json 是怎么定义组件间的联动的&#xff1f; 4、怎么确定区分两个 input&#xff1f; 5、你们是怎么触…
阅读更多...
聚观早报 | 苹果预热WWDC24；怪兽充电第一季度营收

聚观早报 | 苹果预热WWDC24；怪兽充电第一季度营收

聚观早报每日整理最值得关注的行业重点事件&#xff0c;帮助大家及时了解最新行业动态&#xff0c;每日读报&#xff0c;就读聚观365资讯简报。 整理丨Cutie 6月5日消息 苹果预热WWDC24 怪兽充电第一季度营收 vivo Watch GT设计细节 长城汽车关闭欧洲总部 小米MIX Flip将…
阅读更多...
电商架构浅析

电商架构浅析

前言 什么是电商&#xff0c;电商有哪些分类&#xff0c;以及一个完整的电商平台应该由哪些模块组成&#xff1f;本文将围绕电商平台系统的整体架构展开分析。 一、简介 1. 什么是电商 简单说就是通过网络进行的商务活动。以前的人都是通过现金进行交易&#xff0c;就是所谓的…
阅读更多...
热贡文化旅游APP的设计与实现-计算机毕业设计源码69932

热贡文化旅游APP的设计与实现-计算机毕业设计源码69932

摘 要 21世纪的今天&#xff0c;随着社会的不断发展与进步&#xff0c;人们对于信息科学化的认识&#xff0c;已由低层次向高层次发展&#xff0c;由原来的感性认识向理性认识提高&#xff0c;管理工作的重要性已逐渐被人们所认识&#xff0c;科学化的管理&#xff0c;使信息存…
阅读更多...
最新文章

Copyright @ 2022~2023