C++数据结构与算法之双缓存队列实现方法详解
本文实例讲述了C++数据结构与算法之双缓存队列实现方法。分享给大家供大家参考，具体如下：
“双缓存队列”是我在一次开发任务中针对特殊场景设计出来的结构。使用场景为：发送端持续向接收端发送数据包——并且不理会接收端是否完成业务逻辑。由于接收端在任何情况下停止响应即可能产生数据丢失，因此无法简单的设计一条线程安全队列来对数据写入或读取（读取数据时将队列上锁视为对写入的停止响应）。
鉴于此，我的设计思路如下：
接收端首先向A队列中写入数据，然后当数据处理请求到来的时候切换到B队列继续写入，之后将A队列中的数据交给数据处理模块，处理完成以后A队列数据清空。当下一次数据处理请求到来时，再将写入请求切换回A队列，并把B队列中的数据提交给数据处理模块再清空队列B，轮流作业。
有了思路以后，代码就比较简单了。
#include <list>
template<typename T>
class DoubleArray {
struct NODE {
T t;
NODE* next;
};
int size_a;
int size_b;
NODE* header_a;
NODE* header_a_cur;
NODE* header_b;
NODE* header_b_cur;
int trigger;
public:
DoubleArray() : size_a(0), size_b(0), trigger(0), header_a(0), header_a_cur(0), header_b(0), header_b_cur(0) {
}
int push(T t);
std::list<T>& fetch(std::list<T>& list);
};
template<typename T>
int DoubleArray<T>::push(T t) {
NODE *n = new NODE;
n->t = t;
n->next = 0;
if (size_a == 0 && trigger == 0) {
header_a = n;
header_a_cur = n;
size_a++;
} else if (size_b == 0 && trigger == 1) {
header_b = n;
header_b_cur = n;
size_b++;
} else {
switch (trigger) {
case 0:
header_a_cur->next = n;
header_a_cur = n;
size_a++;
break;
case 1:
header_b_cur->next = n;
header_b_cur = n;
size_b++;
break;
}
}
}
template<typename T>
std::list<T>& DoubleArray<T>::fetch(std::list<T>& list) {
switch (trigger) {
case 0:
if (header_a != 0) {
// change b
trigger = 1;
// fetch a
NODE* temp = header_a;
while (temp) {
list.push_back(temp->t);
temp = temp->next;
}
// delete a
temp = header_a;
for (int i = 0; i < size_a; ++i) {
NODE* p = temp;
temp = temp->next;
delete p;
}
size_a = 0;
header_a = 0;
header_a_cur = 0;
}
break;
case 1:
if (header_b != 0) {
// change a
trigger = 0;
// fetch b
NODE* temp = header_b;
// delete b
while (temp) {
list.push_back(temp->t);
temp = temp->next;
}
temp = header_b;
for (int i = 0; i < size_b; ++i) {
NODE* p = temp;
temp = temp->next;
delete p;
}
size_b = 0;
header_b = 0;
header_b_cur = 0;
}
break;
}
return list;
}
注：开发环境与IDE分别为CentOS 7，NetBeans 8.2
希望本文所述对大家C++程序设计有所帮助。
相关推荐
-
C语言数据结构旋转链表的实现
C语言数据结构旋转链表的实现 实例: 给出链表1->2->3->4->5->null和k=2 返回4->5->1->2->3->null 分析: 感觉很直观,直接把分割点找出来就行,记得k可能大于len,要取模 代码: /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x
-
C语言数据结构 快速排序实例详解
C语言数据结构 快速排序实例详解 一.快速排序简介 快速排序采用分治的思想,第一趟先将一串数字分为两部分,第一部分的数值都比第二部分要小,然后按照这种方法,依次对两边的数据进行排序. 二.代码实现 #include <stdio.h> /* 将两个数据交换 */ void swap(int* Ina , int* Inb) { int temp = *Ina; *Ina = *Inb; *Inb = temp; } /* 进行一趟的快速排序,把一个序列分为两个部分 */ int getPart
-
C++数据结构之文件压缩（哈夫曼树）实例详解
C++数据结构之文件压缩(哈夫曼树)实例详解 概要: 项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压 开发环境:windows vs2013 项目概述: 1.压缩 a.读取文件,将每个字符,该字符出现的次数和权值构成哈夫曼树 b.哈夫曼树是利用小堆构成,字符出现次数少的节点指针存在堆顶,出现次数多的在堆底 c.每次取堆顶的两个数,再将两个数相加进堆,直到堆被取完,这时哈夫曼树也建成 d.从哈夫曼树中获取哈夫曼编码,然后再根据整个字符数组来获取出现了得字符的编
-
C++ 数据结构之对称矩阵及稀疏矩阵的压缩存储
对称矩阵及稀疏矩阵的压缩存储 1.稀疏矩阵 对于那些零元素数目远远多于非零元素数目,并且非零元素的分布没有规律的矩阵称为稀疏矩阵(sparse). 人们无法给出稀疏矩阵的确切定义,一般都只是凭个人的直觉来理解这个概念,即矩阵中非零元素的个数远远小于矩阵元素的总数,并且非零元素没有分布规律. 实现代码: //稀疏矩阵及其压缩存储 #pragma once #include <vector> #include <iostream> using namespace std; templa
-
ES6新增数据结构WeakSet的用法详解
WeakSet和Set类似,同样是元素不重复的集合,它们的区别是WeakSet内的元素必须是对象,不能是其它类型. 特性: 1.元素必须是对象. 添加一个number类型的元素. const ws = new WeakSet() ws.add(1) 结果是报类型错误. TypeError: Invalid value used in weak set 添加一个对象. const ws = new WeakSet() var a = {p1:'1', p2:'2'} ws.add(a) conso
-
C++数据结构与算法之反转链表的方法详解
本文实例讲述了C++数据结构与算法之反转链表的方法.分享给大家供大家参考,具体如下: 算法概述:要求实现将一条单向链表反转并考虑时间复杂度. 算法分析: 数组法(略): 将列表元素逐个保存进数组,之后再逆向重建列表 点评:实现逻辑最简单,需要额外的内存开销. 移动指针: 通过三个指针逐个从链表头开始逐一反转链表元素的指针 点评:不需要额外的内存开销,会改变原始链表. 递归: 以递归的方式首先找到链表尾部,再逐一反转指针 点评:不需要额外的内存开销,不会改变原始链表. 算法实现: 构建链表结构 /
-
C语言数据结构之线索二叉树及其遍历
C语言数据结构之线索二叉树及其遍历 遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一个非线性的结构进行线性化.使得在这个访问序列中每一个节点都有一个直接前驱和直接后继.传统的链式结构只能体现一种父子关系,￥不能直接得到节点在遍历中的前驱和后继￥,而我们知道二叉链表表示的二叉树中有大量的空指针,当使用这些空的指针存放指向节点的前驱和后继的指针时,则可以更加方便的运用二叉树的某些操作.引入线索二叉树的目的是: 为了加快查找节点的前驱和后继
-
C语言数据结构之顺序数组的实现
C语言数据结构之顺序数组的实现 以下为展示顺序数组的示例: 1.用C语言实现的版本 #include<stdio.h> /* EOF(=^Z或F6),NULL */ #include<math.h> /* floor(),ceil(),abs() */ #include<stdlib.h> /*申请和释放内存*/ #include<stdarg.h> /*可变参数*/ #define OK 1 //成功标志 #define ERROR 0 //错误标志 #d
-
C++数据结构与算法之双缓存队列实现方法详解
本文实例讲述了C++数据结构与算法之双缓存队列实现方法.分享给大家供大家参考,具体如下: "双缓存队列"是我在一次开发任务中针对特殊场景设计出来的结构.使用场景为:发送端持续向接收端发送数据包--并且不理会接收端是否完成业务逻辑.由于接收端在任何情况下停止响应即可能产生数据丢失,因此无法简单的设计一条线程安全队列来对数据写入或读取(读取数据时将队列上锁视为对写入的停止响应). 鉴于此,我的设计思路如下: 接收端首先向A队列中写入数据,然后当数据处理请求到来的时候切换到B队列继续写入,之
-
Python实现的数据结构与算法之双端队列详解
本文实例讲述了Python实现的数据结构与算法之双端队列.分享给大家供大家参考.具体分析如下: 一.概述 双端队列(deque,全名double-ended queue)是一种具有队列和栈性质的线性数据结构.双端队列也拥有两端:队首(front).队尾(rear),但与队列不同的是,插入操作在两端(队首和队尾)都可以进行,删除操作也一样. 二.ADT 双端队列ADT(抽象数据类型)一般提供以下接口: ① Deque() 创建双端队列 ② addFront(item) 向队首插入项 ③ addRe
-
Python数据结构与算法的双端队列详解
目录 什么是双端队列 用Python实现双端队列 运用双端队列构建回文检测器 总结 什么是双端队列 双端队列是与队列类似的有序集合.它有一前.一后两端,元素在其中保持自己的位置.与队列不同的是,双端队列对在哪一端添加和移除元素没有任何限制.新元素既可以被添加到前端,也可以被添加到后端.同理,已有的元素也能从任意一端移除.某种意义上,双端队列可以是栈和队列的结合. 值得注意的是,尽管双端队列有栈和队列的很多特性,但是它并不要求按照这两种数据结构分别规定的LIFO原则和FIFO原则操作元素.具
-
Python cookbook（数据结构与算法）实现优先级队列的方法示例
本文实例讲述了Python实现优先级队列的方法.分享给大家供大家参考,具体如下: 问题:要实现一个队列,它能够以给定的优先级对元素排序,且每次pop操作时都会返回优先级最高的那个元素: 解决方案:采用heapq模块实现一个简单的优先级队列 # example.py # # Example of a priority queue import heapq class PriorityQueue: def __init__(self): self._queue = [] self._index =
-
Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】
本文实例讲述了Python数据结构与算法之链表定义与用法.分享给大家供大家参考,具体如下: 本文将为大家讲解: (1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计 (2)链表类插入和删除等成员函数实现时需要考虑的边界条件, prepend(头部插入).pop(头部删除).append(尾部插入).pop_last(尾部删除) 2.1 插入: 空链表 链表长度为1 插入到末尾 2.2 删除 空链表 链表长度为1 删除末尾元素 (3)从单链表到单链表的一众变体: 带尾节点的单链表
-
laravel使用Redis实现网站缓存读取的方法详解
redis的简介 Redis 是完全开源免费的,遵守BSD协议,是一个高性能的key-value数据库. Redis 与其他 key - value 缓存产品有以下三个特点: Redis支持数据的持久化,可以将内存中的数据保持在磁盘中,重启的时候可以再次加载进行使用. Redis不仅仅支持简单的key-value类型的数据,同时还提供list,set,zset,hash等数据结构的存储. Redis支持数据的备份,即master-slave模式的数据备份. Redis 优势 性能极高 – Red
-
PHP使用ActiveMQ实现消息队列的方法详解
本文实例讲述了PHP使用ActiveMQ实现消息队列的方法.分享给大家供大家参考,具体如下: 前面我们已经学了如何部署ActiveMQ, 我们知道通过ActiveMQ的一个管理后台可以查看任务队列. 今天 用PHP来操作ActiveMQ,我们可以借助一个第三方扩展. 下载: composer require fusesource/stomp-php:2.0.* 然后新建test.php: <?php require __DIR__.'/vendor/autoload.php'; //引入自动加载
-
JavaScript数据结构之广义表的定义与表示方法详解
本文实例讲述了JavaScript数据结构之广义表的定义与表示方法.分享给大家供大家参考,具体如下: 广义表是线性表的推广,也有人称其为列表. 那么它和线性表有什么区别呢?线性表中每个成员只能是单个元素,而广义表中的成员可以是单个元素,也可以是广义表,分别称为广义表的原子和子表.下面举几个广义表的例子. A=(); B=(e); C=(a,(b,c,d)); D=((),(e),(a,(b,c,d))); E=(a,E); 由于广义表中的数据元素可以具有不同的结构(原子或列表),因此难以用顺序存
-
PHP排序算法之冒泡排序(Bubble Sort)实现方法详解
本文实例讲述了PHP排序算法之冒泡排序(Bubble Sort)实现方法.分享给大家供大家参考,具体如下: 基本思想: 冒泡排序是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止. 最简单排序实现: 我们先来看看在没有学习各种排序方法前经常使用的排序方法(至少我是这样....): //这里使用了类型提示(type hint) array,不熟悉或者不习惯的同学大可去掉,不影响运算结果 function MySort(array &$arr){ $le
-
C++中用两个标准容器stack,实现一个队列的方法详解
代码如下所示: 复制代码 代码如下: // StackToQueue.cpp : 定义控制台应用程序的入口点.//用两个标准容器stack,实现一个队列#include "stdafx.h"#include <iostream>#include <stack>using namespace std;template <class T>class StackToQueue{public: StackToQueue() { stack1; stack