数据结构初阶--栈和队列（讲解+类模板实现）

news/2024/4/20 4:09:25/文章来源:https://blog.csdn.net/jh035/article/details/128110023

栈的概念和结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）加粗样式的原则。
入栈：从栈顶放入数据的操作。
出栈：从栈顶取出元素的操作。

栈的实现

栈用链表和顺序表两种数据结构都可以实现，我们要确定选择哪一种更优，我们来分析一下。
链表栈：如果选择单链表的话，我们应该选择头当栈顶，尾当栈底，不然的话，每次存取数据都要遍历一遍链表。所以选双链表会比较好一点。
数组栈：访问栈顶的时间复杂度为O(1)，相比链表栈比较优。
所以下面我们用顺序表来实现栈的这种数据结构。
结构如下：初始化栈的大小为5

#define InitSize  5
template <class DateType>
class Stack
{
public:
private:DateType* data;//栈空间指针int size;//栈容量int top;//栈顶，栈中元素个数
};

栈的接口

栈要实现的接口有以下几个：

Stack();//初始化栈，初始化的大小是5
Stack(const Stack& stack);//拷贝构造函数
Stack& operator=(const Stack& stack);//等号运算符的重载
~Stack();//销毁栈
bool ifFull();//判断栈是否满了
bool isEmpty();//判断栈是否为空
void Push(const DateType& val);//入栈
bool Pop(DateType &item);//出栈，并获取出栈元素
void ExpandStack();//扩容
void PrintStack();//打印

栈的初始化

初始化栈就是把结构体中的成员都初始化一下，方便后续的扩容等操作。
具体实现如下：

//初始化栈，初始化的大小是5
Stack()
{data = new DateType[InitSize];if (data == NULL){cout << "内存分配失败" << endl;exit(-1);}size = InitSize;top = 0;
}

拷贝构造

//拷贝构造函数
Stack(const Stack& stack)
{this->data = new DateType[stack.size];if (data == NULL){cout << "内存分配失败" << endl;exit(-1);}for (int i = 0; i < stack.size; i++){this->data[i] = stack.data[i];}this->size = stack.size;this->top = stack.top;
}

判断栈满

//判断栈是否满了
bool ifFull()
{if (top == size){return true;}return false;
}

扩容

//扩容
void ExpandStack()
{this->size = this->size == 0 ? 4 : 2 * this->size;DateType* tmp = new DateType[this->size];if (tmp == NULL){cout << "内存分配失败" << endl;exit(-1);}for (int i = 0; i < top; i++){tmp[i] = data[i];}delete[] data;data = tmp;
}

判断栈空

//判断栈是否为空
bool isEmpty()
{if (top == 0){return true;}return false;
}

入栈

压栈就是在栈顶插入元素，其中是肯定要考虑到扩容的问题，当this->top == this->size时，就要考虑到扩容了，扩容也是像之前顺序表那样每次扩一倍，这样可以一定程度地减少扩容次数，但同时是会带来一定的空间消耗的。

//入栈
void Push(const DateType& val)
{if (ifFull()){ExpandStack();}data[top++] = val;
}

出栈

出栈就是在栈顶pop掉一个元素，也就是top-1指向的位置，只需要将top进行一个减1的操作即可。
与此同时，我们要确保此次栈不为空，所以要进行判断栈空的操作，防止程序崩溃。

//出栈，并获取出栈元素
bool Pop(DateType &item)
{if (isEmpty()){cout << "栈为空，无法出栈" << endl;return false;}item = data[--top];return true;
}

赋值运算符重载

运算符重载的注意事项在前面的博客我已经介绍过了，尤其是赋值运算符，感兴趣的小伙伴可以去看看，这里要注意几点

  • 返回的是*this，对象本身
  • 不要自己给自己赋值
  • 要防止内存泄漏
  • 防止浅拷贝的发生
//等号运算符的重载
Stack& operator=(const Stack& stack)
{//防止自赋值if (this == &stack){return *this;}//防止内存泄漏if (data != NULL){delete[] data;}//防止浅拷贝this->data = new DateType[stack.size];if (data == NULL){cout << "内存分配失败" << endl;exit(-1);}for (int i = 0; i < stack.top; i++){this->data[i] = stack.data[i];}this->size = stack.size;this->top = stack.top;return *this;
}

打印

//打印
void PrintStack()
{for (int i = 0; i < top; i++){cout << data[i] << "  ";}cout << endl;
}

整体代码以及测试

#define _CRT_SECURE_NO_WARNINGS
#include<iostream> //引入头文件
#include<string>//C++中的字符串
using namespace std; //标准命名空间
#define InitSize  5
/*
栈,利用顺序表实现
*/
template <class DateType>
class Stack
{
public://初始化栈，初始化的大小是5Stack(){data = new DateType[InitSize];if (data == NULL){cout << "内存分配失败" << endl;exit(-1);}size = InitSize;top = 0;}//拷贝构造函数Stack(const Stack& stack){this->data = new DateType[stack.size];if (data == NULL){cout << "内存分配失败" << endl;exit(-1);}for (int i = 0; i < stack.size; i++){this->data[i] = stack.data[i];}this->size = stack.size;this->top = stack.top;}//等号运算符的重载Stack& operator=(const Stack& stack){//防止自赋值if (this == &stack){return *this;}//防止内存泄漏if (data != NULL){delete[] data;}//防止浅拷贝this->data = new DateType[stack.size];if (data == NULL){cout << "内存分配失败" << endl;exit(-1);}for (int i = 0; i < stack.top; i++){this->data[i] = stack.data[i];}this->size = stack.size;this->top = stack.top;return *this;}//销毁栈~Stack(){if (data != NULL){delete[] data;data = NULL;}}//判断栈是否满了bool ifFull(){if (top == size){return true;}return false;}//判断栈是否为空bool isEmpty(){if (top == 0){return true;}return false;}//入栈void Push(const DateType& val){if (ifFull()){ExpandStack();}data[top++] = val;}//出栈，并获取出栈元素bool Pop(DateType &item){if (isEmpty()){cout << "栈为空，无法出栈" << endl;return false;}item = data[--top];return true;}//扩容void ExpandStack(){this->size = this->size == 0 ? 4 : 2 * this->size;DateType* tmp = new DateType[this->size];if (tmp == NULL){cout << "内存分配失败" << endl;exit(-1);}for (int i = 0; i < top; i++){tmp[i] = data[i];}delete[] data;data = tmp;}//打印void PrintStack(){for (int i = 0; i < top; i++){cout << data[i] << "  ";}cout << endl;}
private:DateType* data;//栈空间指针int size;//栈容量int top;//栈顶，栈中元素个数
};
int main()
{Stack<int> stack;stack.Push(1);stack.Push(2);stack.Push(3);stack.Push(4);stack.Push(5);stack.PrintStack();cout << "-------------------------" << endl;int b = 0;stack.Pop(b);cout << b << endl;stack.Pop(b);cout << b << endl;stack.PrintStack();cout << "-------------------------" << endl;Stack<int> stack2(stack);stack2.PrintStack();cout << "-------------------------" << endl;Stack<int> stack3;stack3 = stack2;stack3.PrintStack();cout << "-------------------------" << endl;system("pause");return EXIT_SUCCESS;
}

队列

队列的概念和结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。

队列的结构，我们选取单链表来实现，秩序进行头删和为插的不足即可。如果选数组，那么每一次删头我们都要挪动一遍数据，这种方式不优，所以我们还是选取用单链表来实现。
定义的结构如下：

template<class DateType>
//链队的结点类型
struct Node
{DateType data;Node<DateType> *next;Node(Node<DateType>* p = NULL){next = p;}//构造函数Node(DateType val, Node<DateType>* p = NULL){data = val;next = p;}
};

template <class DateType>
class Queue
{
public:
private://声明，也是定义，只不过定义的是指针类型，保存的应该是地址，未初始化//队头指针Node<DateType>* front;//队尾指针Node<DateType>* rear;
};

队列的实现

队列的接口

Queue();//构造函数，初始化队列
~Queue();//析构函数
bool QueuePush(const DateType& val);//队尾入队
bool QueuePop(DateType& val);//对头出队列
bool getFront(DateType& val) const;//获取对头元素的值
bool getRear(DateType& val);//获取队尾元素的值
void MakeEmpty();//将队列清空
bool isEmpty() const;//判断队列是否为NULL
int getSize() const;//返回队列元素的个数
void PrintQueue();//输出队列元素

队列的初始化

初始化很简单，只要将头指针和尾指针都置空。

//构造函数
Queue()
{front = NULL;rear = NULL;
}

判断队列是否为空

//判断队列是否为NULL
bool isEmpty() const
{if (front == NULL){return true;}else{return false;}
}

入队

出队就是进行单链表尾删的操作，要考虑链表为空时不能进行删除，还要注意的是只有一个节点进行删除是要改变尾指针的指向。

//队尾入队列
bool QueuePush(const DateType& val)
{if (front == NULL){//如果队列为空，直接用指针开辟结点front = rear = new Node<DateType>(val);if (front == NULL){cout << "内存分配失败" << endl;return false;}}else{Node<DateType>* p = new Node<DateType>(val);rear->next = p;if (rear->next == NULL){cout << "内存分配失败" << endl;return false;}//更新尾结点rear = rear->next;}return true;
}

出队

出队就是进行单链表尾删的操作，要考虑链表为空时不能进行删除，还要注意的是只有一个节点进行删除是要改变尾指针的指向。

bool QueuePop(DateType& val)
{//如果队列为空，不允许出列if (isEmpty()){return false;}else{Node<DateType>* p = front;val = front->data;front = front->next;delete p;return true;}
}

获取队头元素和队尾元素

首先要确保链表不为空，对头就是返回头节点的大小，队尾就是返回尾节点的大小。
具体实现如下：

//获取对头元素的值
bool getFront(DateType& val) const
{if (isEmpty()){return false;}val = front->data;return true;
}
//获取队尾元素的值
bool getRear(DateType& val) {if (isEmpty()){return false;}val = rear->data;return true;
}

获取队列元素个数

遍历一遍链表，同时进行计数操作，最后返回计数结果即可。

//返回队列元素的个数
int getSize() const
{//函数返回队列元素的个数Node<DateType>* p = front;int count = 0;while (p != NULL){++count;p = p->next;}return count;
}

队列的销毁

为了防止内存泄漏，动态内存申请的空间一定要我们自己手动释放，养成一个良好的习惯。所以要将链表的空间逐个释放。

//将队列清空
void MakeEmpty()
{//置空队列，释放链表中所有的结点Node<DateType>* current;if (front != NULL){current = front;front = front->next;delete current;}
}

打印队列

//输出队列元素
void PrintQueue()
{Node<DateType>* p = front;while (p != NULL){cout << p->data << "  ";p = p->next;}cout << endl;
}

整体代码以及测试

#define _CRT_SECURE_NO_WARNINGS
#include<iostream> //引入头文件
#include<string>//C++中的字符串
using namespace std; //标准命名空间
/*
队列，单链表实现
*/
template<class DateType>
//链队的结点类型
struct Node
{DateType data;Node<DateType> *next;Node(Node<DateType>* p = NULL){next = p;}//构造函数Node(DateType val, Node<DateType>* p = NULL){data = val;next = p;}
};
template <class DateType>
class Queue
{
public://构造函数Queue(){front = NULL;rear = NULL;}//析构函数~Queue(){MakeEmpty();}//队尾入队列bool QueuePush(const DateType& val){if (front == NULL){//如果队列为空，直接用指针开辟结点front = rear = new Node<DateType>(val);if (front == NULL){cout << "内存分配失败" << endl;return false;}}else{Node<DateType>* p = new Node<DateType>(val);rear->next = p;if (rear->next == NULL){cout << "内存分配失败" << endl;return false;}//更新尾结点rear = rear->next;}return true;}//对头出队列bool QueuePop(DateType& val){//如果队列为空，不允许出列if (isEmpty()){return false;}else{Node<DateType>* p = front;val = front->data;front = front->next;delete p;return true;}}//获取对头元素的值bool getFront(DateType& val) const{if (isEmpty()){return false;}val = front->data;return true;}//获取队尾元素的值bool getRear(DateType& val) {if (isEmpty()){return false;}val = rear->data;return true;}//将队列清空void MakeEmpty(){//置空队列，释放链表中所有的结点Node<DateType>* current;if (front != NULL){current = front;front = front->next;delete current;}}//判断队列是否为NULLbool isEmpty() const{if (front == NULL){return true;}else{return false;}}//返回队列元素的个数int getSize() const{//函数返回队列元素的个数Node<DateType>* p = front;int count = 0;while (p != NULL){++count;p = p->next;}return count;}//输出队列元素void PrintQueue(){Node<DateType>* p = front;while (p != NULL){cout << p->data << "  ";p = p->next;}cout << endl;}
private://声明，也是定义，只不过定义的是指针类型，保存的应该是地址，未初始化//队头指针Node<DateType>* front;//队尾指针Node<DateType>* rear;
};
int main()
{Queue<int> que;que.QueuePush(1);que.QueuePush(2);que.QueuePush(3);que.QueuePush(4);que.PrintQueue();cout << "----------------------" << endl;int b = 0;que.QueuePop(b);cout << b << endl;que.QueuePop(b);cout << b << endl;que.PrintQueue();cout << "----------------------" << endl;int c = 0;que.getFront(c);cout << c << endl;que.PrintQueue();cout << que.getSize() << endl;cout << "----------------------" << endl;system("pause");return EXIT_SUCCESS;
}

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

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

相关文章

Redis数据结构和类型

Redis数据结构和类型

Redis 包含五种数据类型&#xff0c;分别为String、List、Hash、Set、ZSet 底层实现的数据结构包SDS、双向链表、压缩列表、哈希表、整数集合、跳表 redis结构图数据类型和数据结构的关系Redis六种数据结构 一、动态字符串(SDS) Redis 是用 C 语言实现的&#xff0c;但是它…
阅读更多...
在Word、WPS中插入AxMath公式导致行间距异常的解决办法

在Word、WPS中插入AxMath公式导致行间距异常的解决办法

引言 我最近需要写一些文章&#xff0c;在排版时发现AxMath插入的公式竟然会导致行间距异常&#xff0c;如下图所示&#xff1a; 查遍互联网&#xff0c;最有效的办法竟然要取消文档网格对齐&#xff0c;这对于一些严格要求的场合是非常不利的&#xff0c;经过我的尝试&#…
阅读更多...
SpringBoot3.0正式发布，我来尝尝鲜

SpringBoot3.0正式发布，我来尝尝鲜

GraalVM 版本&#xff1a;graalvm-ce-java17-22.3.0 SpringBoot3.0 中最重要的特性就是对 GraalVM 的支持&#xff0c;从而达到更快的启动速度&#xff0c;有两种使用方式。 利用 GraalVM 构建可执行文件 因为需要利用 GraalVM 来打包可执行文件&#xff0c;所以需要你的机器上…
阅读更多...
Casein-PEG-Indocyanine green 络蛋白-聚乙二醇-吲哚菁绿 Casein-ICG

Casein-PEG-Indocyanine green 络蛋白-聚乙二醇-吲哚菁绿 Casein-ICG

产品名称&#xff1a;络蛋白-聚乙二醇-吲哚菁绿 英文名称&#xff1a;Casein-PEG-Indocyanine green 质量控制&#xff1a;95% 原料分散系数PDI&#xff1a;≤1.05 存储条件&#xff1a;-20C&#xff0c;避光&#xff0c;避湿 用 途&#xff1a;仅供科研实验使用&#xff0c;…
阅读更多...
Ansible 企业级自动化运维实战

Ansible 企业级自动化运维实战

一、Ansible 简介 如果Ansible不采用0mq（ZeroMQ），在操作1000个以下的节点性能还可以，如果操作1000个以上的节点，性能就很差。 目前来说Ansible支持local，ssh，0mq，Ansible用ssh来管理被管理主机是最常见的方法。 saltstack简称salt，默认采用0mq（ZeroMQ），支持数万…
阅读更多...
TaWRKY19/61/82激活糖转运蛋白TaSTP3从而增强小麦条锈病敏感性

TaWRKY19/61/82激活糖转运蛋白TaSTP3从而增强小麦条锈病敏感性

文章信息 题目&#xff1a;Sugar transporter TaSTP3 activation by TaWRKY19/61/82 enhances stripe rust susceptibility in wheat 刊名&#xff1a;New Phytologist 作者&#xff1a;Baoyu Huai&#xff0c;Zhensheng Kang,Jie Liu et al. 单位&#xff1a;Northwest A&…
阅读更多...
麒麟信安携手河南IT联盟召开 《麒麟信安信创应用解决方案》线上分享会

麒麟信安携手河南IT联盟召开 《麒麟信安信创应用解决方案》线上分享会

在党政及金融、交通、能源等重要行业的信创应用步伐逐步加快的背景下&#xff0c;各行业均面临着不同程度的国产化落地难题。11月29日下午&#xff0c;麒麟信安与河南省信息协会IT产业分会&#xff08;河南IT联盟&#xff09;携手召开《麒麟信安信创应用解决方案》线上分享会&a…
阅读更多...
ARM汇编之乘法指令

ARM汇编之乘法指令

ARM汇编之乘法指令前言 首先&#xff0c;请问大家几个小小问题&#xff0c;你清楚&#xff1a; 乘法指令有哪些种类呢&#xff1f;ARM乘法指令具体的使用场景又有哪些&#xff1f; 今天&#xff0c;我们来一起探索并回答这些问题。为了便于大家理解&#xff0c;以下是本文的…
阅读更多...
基础知识java

基础知识java

1.浅克隆和深克隆&#xff1f;深克隆的方法 浅克隆&#xff1a;对象的引用变量只会拷贝地址&#xff0c;不会新建一个对象 深克隆&#xff1a;对象的引用变量也会新建一个对象 实现方式&#xff1a; 浅克隆&#xff1a;实现cloneable接口的clone方法 深克隆&#xff1a;实现Ser…
阅读更多...
西门子精彩触摸屏SMART V3组态报警的具体方法示例

西门子精彩触摸屏SMART V3组态报警的具体方法示例

西门子精彩触摸屏SMART V3组态报警的具体方法示例 用户自定义报警分为离散量报警和模拟量报警。 离散量报警：离散量对应于二进制数的1位，离散量的两种相反状态可以用1位二进制数的0、1状态来表示。例如：电动机的交流接触器的接通和断开、各种故障信号的出现和消失，都可以用…
阅读更多...
flask入门教程之请求与响应

flask入门教程之请求与响应

Flask是一个轻量级的web开发框架&#xff0c;依赖jinja2和Werkzeug WSGI服务的一个微型框架。 官方文档&#xff1a;https://flask.palletsprojects.com/en/2.0.x/ 中文文档&#xff1a;http://docs.jinkan.org/docs/flask/ 中文文档的版本会比较低&#xff0c;如果英语OK的话&…
阅读更多...
22年-自研-面试题

22年-自研-面试题

目录背景题目Activiti回退功能条件分支功能&#xff0c;并行网关、包含网关有没有用到流程流转中&#xff0c;需知会其他人&#xff0c;这些人需同意/做处理&#xff08;有点流程的感觉&#xff09;&#xff0c;最后所有的意见都要汇总。你的实现思路Redis哪些数据结构&#xf…
阅读更多...
【毕业设计】15-基于单片机的交通灯系统设计（原理图+仿真+论文）

【毕业设计】15-基于单片机的交通灯系统设计（原理图+仿真+论文）

【毕业设计】15-基于单片机的交通灯系统设计&#xff08;原理图、仿真、源代码工程答辩论文答辩PPT&#xff09; 文章目录【毕业设计】15-基于单片机的交通灯系统设计&#xff08;原理图、仿真、源代码工程答辩论文答辩PPT&#xff09;任务书设计说明书摘要设计框架架构设计说明…
阅读更多...
【Rust日报】2022-11-29 Wirefish：基于 Tauri 的跨平台数据包嗅探器

【Rust日报】2022-11-29 Wirefish：基于 Tauri 的跨平台数据包嗅探器

Wirefish&#xff1a;基于 Tauri 的跨平台数据包嗅探器作者 stefanodevenuto 通过 Rust Tauri 实现&#xff0c;构建了一个类似 Wireshark 的跨平台数据包嗅探器。这个应用离生产阶段当然还很远&#xff0c;功能和页面上还有很多改善的空间&#xff0c;但是代码组织良好&#…
阅读更多...
基于 Hive 的 Flutter 文档类型存储

基于 Hive 的 Flutter 文档类型存储

基于 Hive 的 Flutter 文档类型存储 原文 https://medium.com/gytworkz/document-type-storage-in-flutter-using-hive-a18ea9659d84 前言 长久以来&#xff0c;我们一直使用共享首选项以键对格式在本地存储中存储数据&#xff0c;或者使用 SQLite 在 SQL 数据库中存储数据。 存…
阅读更多...
【收藏】安科瑞企业微电网能效管理系统云平台演示账号

【收藏】安科瑞企业微电网能效管理系统云平台演示账号

安科瑞 李亚俊 Acrel8757 1、AcrelCloud-1000变电所电力运维云平台 网址&#xff1a;https://acrelcloud.cn/ 演示账号&#xff1a;acrel 密码:123456 2、SCADA电力监控系统 网址&#xff1a;http://scada.acrel-eem.com/ 演示账号&#xff1a;acrel 密码:…
阅读更多...
Android——使用ContentProvider共享数据

Android——使用ContentProvider共享数据

实验名称&#xff1a; 使用ContentProvider共享数据 实验目的&#xff1a; &#xff08;1&#xff09;能使用ContentProvider共享数据 &#xff08;2&#xff09;能使用内容观察者观察其他程序的数据变化 实验内容及原理&…
阅读更多...
Kamiya丨Kamiya艾美捷小鼠血红蛋白ELISA说明书

Kamiya丨Kamiya艾美捷小鼠血红蛋白ELISA说明书

Kamiya艾美捷小鼠血红蛋白ELISA预期用途&#xff1a; 小鼠血红蛋白ELISA是一种高灵敏度的双位点酶联免疫分析&#xff08;ELISA&#xff09;小鼠生物样品中血红蛋白的测定。仅供研究使用。 引言 血红蛋白&#xff08;HM&#xff09;是红细胞中的含铁氧转运蛋白。它吸收肺部的…
阅读更多...
第10讲：Python列表对象查操作之通过切片获取列表中的元素

第10讲：Python列表对象查操作之通过切片获取列表中的元素

文章目录1.切片获取列表中的技术要点1.1切片获取列表中的概念总结1.2.切片的语法格式以及含义3.使用切片方法获取列表中元素3.1.定义一个原始列表列表3.2.当step步长为正数时切片的案例3.3.当step步长为负数时切片的案例3.4.使用负数索引作为切片范围4.将切片后的列表赋值给新的…
阅读更多...
【LeetCode】No.103. Binary Tree Zigzag Level Order Traversal -- Java Version

【LeetCode】No.103. Binary Tree Zigzag Level Order Traversal -- Java Version

题目链接&#xff1a;https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/ 1. 题目介绍&#xff08;Binary Tree Zigzag Level Order Traversal&#xff09; Given the root of a binary tree, return the zigzag level order traversal of its nodes’…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023