c++数据结构算法复习基础--7--线性表-队列-常用操作接口-复杂度分析

news/2024/11/1 20:37:34/

1、队列

特点:先进先出,后进后出

环形队列(依赖数组实现,单必须实现环形)

链式队列(依赖链表实现)

2、环形队列

理论

常规数组思想随着队列的不断使用,会出现越界
在这里插入图片描述
所以要将其设计成环形结构
在这里插入图片描述

边界判断

当不断加入元素,会出现队列使用满的情况,此时不是first == rear == 0,
在这里插入图片描述

在这里插入图片描述
在环形队列中,会留下一个位置,用来区分队列是否满的一个状态。

first == rear //队列为空
(rear + 1)%length == first //队列为满

代码实现

#include<iostream>using namespace std;//环形队列   
//容器适配器queue常用操作 --  push(入队)  pop(出队)  front(获取队头元素) back(获取队尾元素) empty(队列是否为空) size(队列元素个数)
class Queue
{
public:Queue(int size = 10): cap_(size), front_(0), rear_(0),size_(0){pQue_ = new int[cap_];}~Queue(){delete[]pQue_;pQue_ = nullptr;}//入队,入队尾void push(int val){if ((rear_ + 1) % cap_ == front_)//队满{expand(2 * cap_);}pQue_[rear_] = val;rear_ = (rear_ + 1) % cap_;size_++;}//出队,出队头void pop(){if (front_ == rear_)throw "queue is empty!";front_ = (front_ + 1) % cap_;size_--;}//获取队头元素int front()const{if (front_ == rear_)throw "stack is empty!";return pQue_[front_];}//获取队尾元素int back()const{if (front_ == rear_)throw "stack is empty!";/*if (rear_ == 0){return pQue_[cap_-1];}return pQue_[rear_-1];*/return pQue_[(rear_ - 1 + cap_) % cap_];}//判断是否栈空bool empty()const{return front_ == rear_;}//判断栈的元素个数int size() const   //方法一,添加一个成员变量,如果考虑多线程操作,该方法不可行{//return size_;//方法二: 遍历一遍队列统计元素个数 O(n)int size = 0;for (int i = front_; i != rear_; i = (i + 1) % cap_){size++;}return size;}private:void expand(int size)//扩容接口,这里不能直接memcpy{int* p = new int[size];int i = front_;  //遍历原队列int j = 0;       //遍历新队列for (; i != rear_; i = (i + 1) % cap_,j++){p[j] = pQue_[i];}delete[]pQue_;pQue_ = p;cap_ = size;front_ = 0;rear_ = j;}
private:int* pQue_;int cap_;   //空间容量int front_; //队头,入栈指针int rear_;  //队尾、出栈指针int size_;  //元素个数
};

测试

int main()
{int arr[] = { 5,10,66,77,88,99,100,111 }; Queue que;for (int v : arr){que.push(v);}cout << que.front() << endl;cout << que.back() << endl;//扩容que.push(200);que.push(300);que.push(400);cout << que.front() << endl;cout << que.back() << endl;while (!que.empty()){cout << que.front() <<"    "<< que.back() << endl;que.pop();}
}

测试结果

在这里插入图片描述

3、链式队列

基于双向循环链表实现的链式队列
队尾进,队头出

Java 里面有Linkedin的数据结构,可以充当栈、队列,基于链表实现。

代码实现

//环形队列   
//容器适配器queue常用操作 --  push(入队)  pop(出队)  front(获取队头元素) back(获取队尾元素) empty(队列是否为空) size(队列元素个数)
class LinkQueue
{
public:LinkQueue():size_(0){head_ = new Node();head_->next_ = head_;head_->pre_ = head_;}~LinkQueue(){Node* p = head_->next_;while (p != head_){head_->next_ = p->next_;p->next_->pre_ = head_;delete p;p = head_->next_;}delete head_;head_ = nullptr;}
public://入队,入队尾void push(int val){Node* node = new Node(val);node->next_ = head_;node->pre_ = head_->pre_;head_->pre_->next_ = node;head_->pre_ = node;size_++;}//出队,出队头void pop(){if (head_->pre_ == head_)throw "queue is empty!";Node* p = head_->next_;head_->next_ = p->next_;p->next_->pre_ = head_;delete p;p = nullptr;size_--;}//获取队头元素int front()const{if (head_->next_ == head_)throw "stack is empty!";return head_->next_->data_;}//获取队尾元素int back()const{if (head_->next_ == head_)throw "stack is empty!";return head_->pre_->data_;}//判断是否栈空bool empty()const{return head_->next_ == head_;}//判断栈的元素个数int size() const   //方法一,添加一个成员变量,如果考虑多线程操作,该方法不可行{return size_;//方法二: 遍历一遍队列统计元素个数 O(n)}private:struct Node{Node(int data = 0):data_(data), next_(nullptr), pre_(nullptr){}int data_;Node* next_;Node* pre_;};Node* head_;//指向头节点int size_;};

测试

int main()
{int arr[] = { 5,10,66,77,88,99,100,111 }; LinkQueue que;for (int v : arr){que.push(v);}que.push(200);que.push(300);cout << que.front() << endl;cout << que.back() << endl;while (!que.empty()){cout << que.front() <<"    "<< que.back() << endl;que.pop();}
}

运行结果

在这里插入图片描述


http://www.ppmy.cn/news/1543683.html

相关文章

《等保测评:安全与发展的双轮驱动》

在快速发展的数字经济时代&#xff0c;网络安全已成为企业生存与发展的关键因素。等保测评作为国家网络安全等级保护制度的核心内容&#xff0c;不仅为企业筑起一道坚实的安全防线&#xff0c;更成为推动企业高质量发展的双轮之一。本文将深入探讨等保测评如何在保障安全的同时…

视频编辑的创意工坊,使用视频剪辑软件将视频随机分割成两段并去声进行MP3音频和M3u8文件的生成,让视频制作更高效

面对海量的视频编辑任务&#xff0c;你是否曾感到手足无措&#xff0c;渴望一种既简单又高效的方式来处理它们&#xff1f;别担心&#xff0c;媒体梦工厂软件带着它的魔法棒来啦&#xff01;它就像一位技艺高超的视频巫师&#xff0c;能轻松帮你在线完成视频编辑任务&#xff0…

计算堆栈中的剩余数字

更多关于刷题的内容欢迎订阅我的专栏华为刷题笔记 该专栏题目包含两部分&#xff1a; 100 分值部分题目 200 分值部分题目 所有题目都会陆续更新&#xff0c;订阅防丢失 题目描述&#xff1a; 向一个空栈中依次存入正整数&#xff0c; 假设入栈元素 n ( 1 < n < 2…

Spring Boot在校园社团信息管理中的实践与思考

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常…

PHP语言学习教程:从入门到精通

PHP语言学习教程&#xff1a;从入门到精通 欢迎来到这篇关于 PHP 的学习教程&#xff01;在这篇文章中&#xff0c;我们将深入探讨 PHP 的各个方面&#xff0c;从基础语法到高级特性&#xff0c;帮助你掌握这门强大的服务器端编程语言。无论你是初学者还是有一定经验的开发者&…

kotlin android Handler removeCallbacks runnable不生效的一种可能

android Handler无法移除runnable。 比较老的解释就是因为messageQueue已经即将执行的不能被取消&#xff0c;这种我们很好理解它&#xff0c; 因为他已经在跑了&#xff0c;自然无法移掉。 但是在kotlin下有个大坑。 赶快来全局搜索检查你的removeCallbacks吧&#xff01; pr…

Python3 基础核心语法指南(初级版)

Python 是一门广泛使用的编程语言&#xff0c;适合从小项目到大规模应用开发。本文介绍 Python 的基本语法和一些实用的编程技巧&#xff0c;适合初学者与开发人员。为了方便大家理解&#xff0c;有些例子采用两种写法&#xff0c;一种采用的是英文变量名&#xff0c;另一种则采…

三、k8s快速入门之Kubectl 命令基础操作

⭐️创建Pod [rootmaster ~]# kubectl run nginx --imageharbor.tanc.com/library/ngix:latest kubectl run --generatordeployment/apps.v1 is DEPRECATED and will be rmoved in a future version. Use kubectl run --generatorrun-pod/v1 or kbectl create instead. deplo…