首页 > 编程语言 >【第三节】C/C++数据结构之栈与队列

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

时间：2024-06-05 10:03:38浏览次数：25  
标签：结点 const int ElemType void 之栈 C++ 数据结构 rear

目录

一、数据结构-栈

1.1 栈的定义

1.2 栈的 ADT (Abstract Data Type)

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

二、数据结构-队列

2.1 队列的定义

2.2 队列的 ADT

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

2.4 优先队列

一、数据结构-栈

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

标签：结点,const,int,ElemType,void,之栈,C++,数据结构,rear
From： https://blog.csdn.net/linshantang/article/details/139452738

相关文章

  • 计算机毕业设计项目推荐，28259校园信息交流平台的设计与实现（开题答辩+程序定制+全套文
    摘 要随着我国经济迅速发展，人们对手机的需求越来越大，各种手机软件也都在被广泛应用，但是对于手机进行数据信息管理，对于手机的各种软件也是备受用户的喜爱，校园信息交流平台被用户普遍使用，为方便用户能够可以随时进行校园信息交流平台的数据信息管理，特开发了基于校园信息交流......
  • 计算机毕业设计项目推荐，28326 校园商店管理系统的设计与实现（开题答辩+程序定制+全套文
    摘 要随着科学技术的飞速发展，社会的方方面面、各行各业都在努力与现代的先进技术接轨，通过科技手段来提高自身的优势，校园商店当然也不能排除在外。校园商店是以实际运用为开发背景，运用软件工程原理和开发方法，采用Java技术构建的一个管理系统。整个开发过程首先对软件系统......
  • （免费领源码）Java/Mysql数据库+04770 基于Java的书籍借阅管理系统设计与实现，计算机毕业
    摘 要随着科学技术的告诉发展，我们已经步入数字化、网络化的时代。图书馆是学校的文献信息中心，是为全校教学和科学研究服务的学术性机构，是学校信息化的重要基地。图书馆的工作是学校和科学研究工作的重要组成部分，是全校师生学习和研究的重要场所。为了提高图书馆的工作效率......
  • （免费领源码）Java/Mysql数据库+04827基于PHP的高校二手物品交易系统的设计与实现，计算机
    本科生毕业论文（设计） 题   目PHP高校二手物品交易系统学   院       XXXXX     专业班级   XXXXX学生姓名       XXXX    指导教师            XXXX          撰写日期：2022年5月10日目 录摘......
  • 巧用CMake编译策略：C++二次开发中的Release与Debug模式切换秘籍
    往期本博主的C++精讲优质博文可通过这篇导航进行查找：《Lemo的C++精华博文导航：进阶、精讲、设计模式文章全收录》前言在C++二次开发的过程中，理解各种编译模式并能灵活切换，对于提升软件性能和调试效率至关重要。本文将深入讨论Debug与Release模式的区别、默认编......
  • C/C++ while 语句的要点与注意事项
    while 语句是C语言中的一种基本控制流语句，用于在特定条件为真时重复执行一段代码。下面是关于 while 语句的要点和注意事项的详细介绍。要点基本语法：1while(condition){2//循环体：当condition为真时执行的代码3}其中，condition 是一个表达式，其结果为......
  • 数据结构复习笔记5.3：线索二叉树
    1.前言        在n个结点的⼆叉链表中，必定有n+1个空链域。⽽遍历运算是最重要的，也是最常⽤的运算⽅法，之前的⽆论是递归与非递归的算法实现遍历效率其实都不算⾼。        现有⼀棵结点数⽬为n的⼆叉树，采⽤⼆叉链表的形式存储。对于每个结点均有指向左右孩⼦......
  • 【数据结构与算法 经典例题】链表的回文结构（图文详解）
                  ......
  • C语言数据结构实现-顺序表基本操作
    顺序表，全名顺序存储结构，是线性表的一种。通过《什么是线性表》一节的学习我们知道，线性表用于存储逻辑关系为“一对一”的数据，顺序表自然也不例外。不仅如此，顺序表对数据的物理存储结构也有要求。顺序表存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依次存储起来，存储时......
  • 【每周例题】 C++ 力扣 优势洗牌
    优势洗牌题目优势洗牌 题目分析1.采用双指针方法进行匹配2.依照题目所说，采用索引，首先需要填充索引，然后对索引进行升序排序。2.使用双指针进行匹配如果nums1[idx1[i]]（即当前nums1中的元素）大于nums2[idx2[left]]（即nums2中的当前最小元素），则将nums1[idx1[i]]赋值给ans[idx2[......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99