【Queue新技法】用双数组实现一个队列 C++

目录

  • 1 常规的队列构建
  • 2 加入一些限制
    • 2-1形式化说明
    • 2-2 优化：平衡队列
  • 附录
    • 0 双数组或双链表实现队列
    • 1 单链表与循环缓冲区实现队列
    • 3 参考资料

1 常规的队列构建

  到火车站办理退票，排队的人构成队列。注意到有两个关键动作：

  1. 入队，即自觉站到队伍的末尾。
  2. 出队，从柜台离开。

  单链表：先建立一个漂亮的柜员姐姐（哨兵或额外的头结点），记忆当前队列的第一个人，再来个尾指针，用于添加下一个人。

  循环数组，也叫循环缓冲区，如图灰色部分就是队列的内容。

  这两种方式容易理解，其中入队、出队都是O(1)也容易实现，代码放在末尾附录中。

2 加入一些限制

  现先引入新情境：考虑一种情况在函数式环境不能用变量来记录末尾，怎么办？

  • 如果只能用链表实现（如Haskell语言），这时候入队必须遍历到末尾，时间复杂度O(N)
  • 如果只能用数组实现（如BASIC语言），入队必须把所有元素往后移动，时间复杂度又是O(N)

  如上图所示，左边是原来的队列，右边是翻转后的队列。然后会出现几个问题：

  1. 在队伍末尾直接插入，是O(N)复杂度，虽然翻转后插入是O(1)，但翻转不也是O(N)吗？
  2. 翻转后入队是O(N)，那出队呢？再翻转回来吗？不是更麻烦了吗？

  两个问题其实一个纠结在一个队列怎么能来回翻转呢？然而，我们可以用两个链表（或数组结构），一个只管出队，一个只管入队，只有在出队的队列为空，才把入队的队列翻转并放到出队（修改指针O(1)），可以看到本质是延时处理，翻转并不针对每次入队操作，其分摊性能可以降低为常数O(1)。

2-1形式化说明

  说明：记入队的列表为F(Front)，出队的队列为R(Rear)，那完整的队列 Q ( F ， R ) Q(F，R) Q(F，R)，此外定义两个操作，设列表 X = { x 1 , x 2 , x 3 . . . } X=\{x_1,x_2,x_3...\} X={x1​,x2​,x3​...}，则

  • 函数 t a i l ( X ) = { x 2 , x 3 , x 4 . . . } tail(X)=\{x_2,x_3,x_4...\} tail(X)={x2​,x3​,x4​...}即去掉首个元素的剩余部分；
  • 函数 b a l a n c e ( F , R ) = Q ( r e v e r s e ( R ) , ∅ ) : F = ∅ balance(F,R)=Q(reverse(R),\emptyset):F=\emptyset balance(F,R)=Q(reverse(R),∅):F=∅，此外当出队队列F不空，什么也不做。

  此时，入队和出队操作定义如下：
p u s h ( Q , x ) = b a l a n c e ( F , x ∪ R ) p o p ( Q ) = b a l a n c e ( t a i l ( F ) , R ) push(Q,x)=balance(F,{x} \cup R) \\ \\[2ex] pop(Q)=balance(tail(F),R) push(Q,x)=balance(F,x∪R)pop(Q)=balance(tail(F),R)  实现是容易的代码放在附录，现在先点这里平摊分析，证明一下两个链表（或数组）的分摊性能的确是常数级别。只有出队操作可能引发翻转，尽管翻转的总复杂度是O(N)，可只有几次，但O(1)出队操作却有N个，即均摊到每次出队操作上只有 O ( 1 ) = O ( N ) / N O(1)=O(N)/N O(1)=O(N)/N。
p o p ( Q ) = { O ( N ) , L为空集 1 , 其他 pop(Q) = \begin{cases} O(N), & \text{L为空集} \\ 1, & \text{其他} \end{cases} pop(Q)={O(N),1,​L为空集其他​

2-2 优化：平衡队列

  注意到，当入队的Rear队列过长时，翻转所消耗的时间很大，表现为在查看队头时，若发现队列为空，需要等好一会儿，才能完成翻转进而得到所需队头数据。
  造成这一困难的原因是入队队列Rear和出队队列Front之间的数量太不平衡。所以，我们加一个限制，来保证Front的长度不小于Rear。修改函数
b a l a n c e ( F , R ) = Q ( r e v e r s e ( R ) , ∅ ) : F . l e n < R . l e n balance(F,R)=Q(reverse(R),\emptyset):F.len<R.len balance(F,R)=Q(reverse(R),∅):F.len<R.len

  实现时，对链表来说可以用哨兵的key记录当前队列的长度；对数组来说，可以直接采用vector.size()获取长度信息。

附录

  队列的基本的方法说明：

  • 判断是否非空？ empty(is_empty)
  • 入队 push 、（append、push_back）
  • 出队 pop 、（tail、pop_front）
  • 查看头部元素 front （head）

0 双数组或双链表实现队列

#include<iostream>
#include<vector>// 代替数组
#include<algorithm>// 翻转vector
using namespace std;

#define ERROR -1
using Key=int;

//定义节点
struct Node
{
    Key key;
    struct Node *nxt;
    Node(Key k, struct Node *ptr = nullptr) : key(k), nxt(ptr) {}
};
using Nptr = struct Node *;
//定义链表
struct List{
    Nptr sentry;//哨兵节点
    List(){
        sentry=new Node(-1);
    }
};

class dualListQ
{
private:
    List m_front;
    List m_rear;

    int balance();
    Nptr reverse_list(Nptr head);//递归翻转链表
public:
    bool is_empty() const;
    void push_back(const Key &k) ;
    void pop_front();
    Key front();
};
int dualListQ::balance()
{
    if(m_front.sentry->nxt!=nullptr) return 0;
    if(m_rear.sentry->nxt==nullptr){
        cerr<<"balance()-> queue is empty!"<<endl;
        return ERROR;
    }
    m_front.sentry->nxt=reverse_list(m_rear.sentry->nxt);
    m_rear.sentry->nxt=nullptr;
    return 0;
}
//haed 指向哨兵的下一个节点
Nptr dualListQ::reverse_list(Nptr head){
    //递归的出口：空链或只有一个结点，直接返回头指针
    if (head == nullptr || head->nxt == nullptr) 
    {
        return head;
    }
    else
    {
        //一直递归，找到链表中最后一个节点
        Nptr new_head = reverse_list(head->nxt);
        //当逐层退出时，new_head 的指向都不变，一直指向原链表中最后一个节点；
        //递归每退出一层，函数中 head 指针的指向都会发生改变，都指向上一个节点。
        //每退出一层，都需要改变 head->next 节点指针域的指向，同时令 head 所指节点的指针域为 NULL。
        head->nxt->nxt = head;
        head->nxt = nullptr;
        //每一层递归结束，都要将新的头指针返回给上一层。由此，即可保证整个递归过程中，能够一直找得到新链表的表头。
        return new_head;
    }

}

bool dualListQ::is_empty() const
{
    return m_front.sentry->nxt==nullptr&&nullptr==m_rear.sentry->nxt; 
}

void dualListQ::push_back(const Key &k)
{
    Nptr old_=m_rear.sentry->nxt;
    Nptr new_=new Node(k);
    m_rear.sentry->nxt=new_;
    new_->nxt=old_;
    if(ERROR==balance()) return;
}

void dualListQ::pop_front()
{   
    if(ERROR==balance()) return;
    Nptr tmp=m_front.sentry->nxt;
    m_front.sentry->nxt=tmp->nxt;
    delete tmp;
}

Key dualListQ::front()
{
    if(is_empty()){
        cerr<<"front()-> queue is empty!"<<endl;
        return ERROR;
    }
    if(m_front.sentry->nxt==nullptr){
        balance();
    }
    return m_front.sentry->nxt->key;
}



class dualVectorQ
{
private:
    vector<Key> m_front,m_rear;
    int balance();
public:
    bool is_empty() const;
    int push_back(const Key &k) ;
    void pop_front();
    Key front();
};
int dualVectorQ::balance()
{
    if(m_front.empty()){
        if(m_rear.empty()){
            cerr<<"balance()-> queue is empty."<<endl;
            return ERROR;
        }
        reverse(m_rear.begin(),m_rear.end());
        for(auto &k:m_rear){
            m_front.push_back(k);
        }
        m_rear.clear();
    }
    return 0;
}
bool dualVectorQ::is_empty() const
{
    return m_front.size()+m_rear.size()==0;
}

int dualVectorQ::push_back(const Key &k)
{
    m_rear.push_back(k);
    return 0;
}
void dualVectorQ::pop_front(){
    balance();
    m_front.pop_back();// 翻转后，队尾即对头
}
Key dualVectorQ::front(){
    if(is_empty()){
        cerr<<"front()-> Queue is empty..."<<endl;
        return ERROR;
    }
    balance();
    return m_front.back();// 翻转后，队尾即对头
}


#define see(x) cout<<x<<endl
void test(){
    // dualListQ que;//创建空的队列
    dualVectorQ que;
    int arr[]={1,3,5,7,9};
    for (size_t i = 0; i < 5; i++)
    {
        que.push_back(arr[i]);
    }
    see(que.front());//1
    que.pop_front();
    see(que.front());//3
    que.pop_front();
    que.pop_front();
    que.pop_front();
    if(que.is_empty())
        see("queue is empty");//无
    see(que.front());//9
    que.pop_front();
    if(que.is_empty())
        see("queue is empty");//有
    see(que.front());

}

int main(){
    test();
    return 0;
}

1 单链表与循环缓冲区实现队列

#include<iostream>
using namespace std;

#define ERROR -1
using Key=int;
class listQ
{
private:
    struct Node 
    {
        Key key;
        struct Node* nxt;
        Node(Key k,struct Node* ptr=nullptr):key(k),nxt(ptr){}
    };
    using Nptr=struct Node*; 
    Nptr m_sentry=nullptr;//头结点，指向真实的头一个数据
    Nptr m_tail=nullptr;//指向尾节点
public:
    listQ();//创建空队列
    ~listQ();
    bool is_empty() const;
    void push_back(const Key &k) ;
    void pop_front();
    Key front();
};
listQ::listQ()
{
    m_sentry=new Node(-1);
    m_tail=m_sentry;
}

listQ::~listQ()
{
    while(!is_empty()){
        pop_front();
    }

    delete m_sentry;
    cout<<"over   ..."<<endl;
}

bool listQ::is_empty() const
{
    if(m_sentry->nxt==nullptr) return true;
    return false;
}

void listQ::push_back(const Key &k)
{
    Nptr new_node=new Node(k);
    m_tail->nxt=new_node;
    m_tail=new_node;
}

void listQ::pop_front()
{
    Nptr tmp=m_sentry->nxt;
    m_sentry->nxt=tmp->nxt;
    delete tmp;
}

Key listQ::front()
{
    if(is_empty()){
        cerr<<"queue is empty!"<<endl;
        return ERROR;
    }
    return m_sentry->nxt->key;
}


//循环缓冲区
class arrayQ
{
private:
    static const size_t QSIZE=5;
    Key m_buf[100];
    int m_head=0;
    int m_tail=0;//指向队列末尾下一个空位
    int m_length=0;
public:
    bool is_empty() const{ return 0==m_length;}
    int push_back(const Key &k) ;
    void pop_front();
    Key front();

};
void arrayQ::pop_front(){
    --m_length;
    ++m_head;
    m_head -= (m_head < QSIZE) ?  0 : QSIZE;//模拟取余数，因为某些机器取余很慢
}
int arrayQ::push_back(const Key &k){
    if(m_length==QSIZE){
        cerr<<"push-> Queue is full!!"<<endl;
        return ERROR;
    }

    m_buf[m_tail++]=k;
    m_tail -=(m_tail < QSIZE) ?  0 : QSIZE;
    ++m_length;
    return 0;
}
Key arrayQ::front(){
    if(is_empty()){
        cerr<<"front()-> Queue is empty..."<<endl;
        return ERROR;
    }

    return m_buf[m_head];
}


#define see(x) cout<<x<<endl
void test(){
    // listQ que;//创建空的队列
    arrayQ que;
    int arr[]={1,3,5,7,9};
    for (size_t i = 0; i < 5; i++)
    {
        que.push_back(arr[i]);
    }

    // que.push_back(11);
    see(que.front());//1
    que.pop_front();
    see(que.front());//3
    que.pop_front();
    que.pop_front();
    que.pop_front();
    see(que.is_empty());
    see(que.front());//9
    que.pop_front();
    see(que.is_empty());
    see(que.front());

}

int main(){
    test();
    return 0;
}

3 参考资料

刘新宇 《算法新解》

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

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

相关文章

Linux-初学者系列7_shell编程

Linux-初学者系列7_shell编程

在进行服务器集群管理时&#xff0c;需要编写shell程序来进行服务器管理。 shell是一个命令行解释器&#xff0c;他会为用户提供了一个向Linux内核发送请求以便运行程序的界面系统级程序&#xff0c;用户用shell启动、挂起、停止和编写一些程序。 Linux-初学者系列7_shell编程…
阅读更多...
股票量价关系基础知识7----图解各阶段量价关系：价涨量缩

股票量价关系基础知识7----图解各阶段量价关系：价涨量缩

图解各阶段量价关系&#xff1a;价涨量缩 价涨量缩是指股价上涨&#xff0c;成交量却萎缩的一种价量背离走势。它通常反映上涨力道不足&#xff0c;预示股价可能反转向下。 一、上涨初期的价涨量缩 &#xff08;一&#xff09;形态分析 股价经过一轮下跌后止跌回升&#xff0c…
阅读更多...
VolSDF

VolSDF

Volume Rendering of Neural Implicit Surfaces&#xff08;VolSDF&#xff09;&#xff1a;神经隐式曲面的体渲染 摘要&#xff1a;一个神经隐式表面体积渲染框架&#xff0c;将体积密度建模为几何形状的函数来实现表面重建。定义的体积密度函数作为拉普拉斯的累积分布函数&am…
阅读更多...
( 位运算 ) 190. 颠倒二进制位 ——【Leetcode每日一题】

( 位运算 ) 190. 颠倒二进制位 ——【Leetcode每日一题】

❓190. 颠倒二进制位 难度&#xff1a;简单 颠倒给定的 32 位无符号整数的二进制位。 提示&#xff1a; 请注意&#xff0c;在某些语言&#xff08;如 Java&#xff09;中&#xff0c;没有无符号整数类型。在这种情况下&#xff0c;输入和输出都将被指定为有符号整数类型&a…
阅读更多...
看大老如何用Postman+Jmeter实现接口实例

看大老如何用Postman+Jmeter实现接口实例

一、接口基础 为什么要单独测试接口&#xff1f; 1. 程序是分开开发的&#xff0c;前端还没有开发&#xff0c;后端已经开发完了&#xff0c;可以提前进入测试 2. 接口直接返回的数据------越底层发现bug&#xff0c;修复成本是越低的 3. 接口测试能模拟功能测试不能测到的异常…
阅读更多...
Baklib知识库搭建平台产品操作手册

Baklib知识库搭建平台产品操作手册

产品概述 Baklib是一款专业的知识库搭建平台&#xff0c;它帮助客户搭建内部知识库和对外帮助中心。在今天的信息时代&#xff0c;知识已经成为组织的核心竞争力&#xff0c;而Baklib正是为了帮助组织构建完整的知识体系&#xff0c;提高组织的核心竞争力而生。 Baklib具有以…
阅读更多...
程序进制换算

程序进制换算

进制数介绍 一、进制介绍 二进制 &#xff1a;0或1&#xff0c;满2进1&#xff0c;以0B或者0b开头&#xff0c;如 0b1101 八进制&#xff1a;0-7&#xff0c;满8进1&#xff0c;&#xff0c;以0开头&#xff0c;如0234 十进制&#xff1a;0-9&#xff0c;满10进1&#xff0c;…
阅读更多...
阿里云服务器建站教程（5分钟网站上线）

阿里云服务器建站教程（5分钟网站上线）

使用阿里云服务器快速搭建网站教程&#xff0c;先为云服务器安装宝塔面板&#xff0c;然后在宝塔面板上新建站点&#xff0c;阿里云服务器网以搭建WordPress网站博客为例&#xff0c;来详细说下从阿里云服务器CPU内存配置选择、Web环境、域名解析到网站上线全流程&#xff1a; …
阅读更多...
CLion安装（详细步骤+截图）

CLion安装（详细步骤+截图）

目录 一、CLion-2021.1.3.exe 下载 二、运行环境mingw-w64压缩包下载 三、 安装插件 ---- ide-eval-resetter-2.1.13压缩包下载 一、CLion-2021.1.3.exe 下载 Other Versions - CLion (jetbrains.com) 1、下载 2、更改路径 &#xff08;不要放在含有中文的路径下&a…
阅读更多...
Qt+WebRTC学习笔记（七）ubuntu22.04下搭建coturn(STUN/TURN)

Qt+WebRTC学习笔记（七）ubuntu22.04下搭建coturn(STUN/TURN)

前言 因工作原因&#xff0c;很长时间没更新相关文档了&#xff0c;笔者之前测试时&#xff0c;一直使用示例自带的公网中转服务器。考虑到后期项目需要&#xff0c;笔者在线搭建一个coturn服务器测试&#xff0c;供有需要的小伙伴使用 一、安装coturn 若需要最新版本的cotu…
阅读更多...
如何通过appuploader把ipa文件上传到App Store教程步骤

如何通过appuploader把ipa文件上传到App Store教程步骤

​ iOS APP上架App Store其中一个步骤就是要把ipa文件上传到App Store&#xff01;​ 下面进行步骤介绍&#xff01;​ 利用Appuploader这个软件&#xff0c;可以在Windows、Linux或Mac系统中申请ios和上传IPA到App Store Connect。​ 非常的方便&#xff0c;没有Mac也可以…
阅读更多...
tiechui_lesson08_内存的分配和链表

tiechui_lesson08_内存的分配和链表

主要是将链表结构的使用&#xff0c;在内核开发中使用起来比较方便的一种数据结构【LIST_ENTRY】。 一、内存的分配 主要是学习一些基本操作。现在推荐使用的动态分配函数【ExAllocatePoolWithTag】 PVOID tempbuffer ExAllocatePoolWithTag(NonPagedPool, 0x1000, xxaa); …
阅读更多...
APP外包项目的线上维护方案

APP外包项目的线上维护方案

APP的使用已经非常普及&#xff0c;不论是2C还是2B的APP都已经渗透到了我们生活的方方面面&#xff0c;对于APP的开发公司来说APP项目的线上维护是一个非常重要的问题。如果APP项目比较重要而且用户规模比较大&#xff0c;那更需要专业的技术团队来维护。今天和大家分享这方面的…
阅读更多...
计算机网络-SNMP协议与pysnmp

计算机网络-SNMP协议与pysnmp

1.概念 2.典型架构 3.snmp的信息交互 4.MIB 4.1常见MIB节点 5.SNMP管理模型 MIB位于被管理进程 6.SNMP的三个版本 6.1 SNMPv1 6.2 SNMPv2C 6.3 SNMPv3 6.3.1 SNMP3的基本操作 6.3.2 SNMP交互GET 6.3.3 SNMP交互-GETBULK 6.3.4 SNMP交互-SET 6.3.5 SNMP交互-trap 6.3.6 SNMP交…
阅读更多...
【技术干货】PCB焊盘设计之问题详解

【技术干货】PCB焊盘设计之问题详解

SMT的组装质量与PCB焊盘设计有直接的关系&#xff0c;焊盘的大小比例十分重要。如果PCB焊盘设计正确&#xff0c;贴装时少量的歪斜可以再次回流焊纠正(称为自定位或自校正效应)&#xff0c;相反&#xff0c;如果PCB焊盘设计不正确&#xff0c;即使贴装位置十分准确&#xff0c;…
阅读更多...
【 图像水印 2019 CVPR】 StegaStamp 论文翻译

【 图像水印 2019 CVPR】 StegaStamp 论文翻译

【 图像水印 2019 CVPR】 StegaStamp 论文翻译 论文题目&#xff1a;StegaStamp: Invisible Hyperlinks in Physical Photographs 中文题目&#xff1a;物理照片中不可见的超链接 论文链接&#xff1a;https://arxiv.org/abs/1904.05343 论文代码&#xff1a;https://github.co…
阅读更多...
Linux内核架构和工作原理

Linux内核架构和工作原理

**前言&#xff1a;**作用是将应用层序的请求传递给硬件&#xff0c;并充当底层驱动程序&#xff0c;对系统中的各种设备和组件进行寻址。目前支持模块的动态装卸(裁剪)。Linux内核就是基于这个策略实现的。Linux进程1.采用层次结构&#xff0c;每个进程都依赖于一个父进程。内…
阅读更多...
django基础知识详解

django基础知识详解

1. 安装与介绍 课程特点&#xff1a; 学习难度大&#xff0c;大部分内容需要理解并记忆文件较多易混淆学习阶段注重框架使用&#xff0c;工作阶段注重实现业务逻辑综合应用强&#xff0c;小练习少 1.1 Django框架的介绍 2005年发布,采用Python语言编写的开源web框架早期的时…
阅读更多...
分享105个NET源码ASP源码，总有一款适合您

分享105个NET源码ASP源码，总有一款适合您

分享105个NET源码&#xff0c;总有一款适合您 源码下载链接&#xff1a;https://pan.baidu.com/s/1zFMIHX6juXdR2CaHMEr5mQ?pwdf5hz 提取码&#xff1a;f5hz 下面是文件的名字&#xff0c;我放了一些图片&#xff0c;文章里不是所有的图主要是放不下...&#xff0c;大家下载后…
阅读更多...
每天一个提高效率的Matlab编程小技巧(1)-dbstop if error

每天一个提高效率的Matlab编程小技巧(1)-dbstop if error

相信在matlab调试程序的时候都遇到过这种情况&#xff1a;运行程序时命令行报错&#xff0c;而且出错的位置在我们自己定义的函数里&#xff0c;比如下面这个例子&#xff1a; 主函数main.m: a[1 2 3]; b[4 5]; csum_squares(a,b); 子函数sum_squares.m function csum_squa…
阅读更多...
最新文章

Copyright @ 2022~2023