- 浏览: 128675 次
- 性别:
- 来自: 成都
最新评论
-
yi_chao_jiang:
你好,多谢分享,问个问题,在上传数据的时候判断文件是否有上传记 ...
断点续传和下载原理分析 -
a41606709:
为什么我的tabhost显示不出来? 怎么设置在全部页面中让他 ...
TabActivity中的Tab标签详细设置 -
Zero颴:
大神篇,思路,配图都很清晰,perfect!
Android事件模型之interceptTouchEvnet ,onTouchEvent关系正解 -
QAZ503602501:
牛死人了!!!
B-树 -
mengsina:
很牛的文档。数学功底好啊
Android Matrix理论与应用详解
1.算法描述
a.数据结构与算法(Mark Allen Weiss)3.28双端队列的实现,在队列的两端都可以进行插入和删除工作,每种操作复杂度O(1).
b.没有头结点和尾结点的队列实现
c.循环数组的队列实现
2.算法实现
a.由于有复杂度的限制,和两端插入删除,故而使用数组是不适合的,必须使用链表,我这里使用的是双向链表,在两端操作的复杂度就一样的,非常方便
b.没有头尾结点实现队列,关键就是注意空队列的判断,在空队列情况下的插入删除操作。
c.循环数组就是在尾部循环的时候操作。
3.代码实现
a.双端队列
deque.h
//双端队列(两头都可以插入删除,故而使用的双向链表) #ifndef DEQUE_H #define DEQUE_H template<class T> struct Node{ Node* next; Node* pre; T data; }; template<class T> class Deque{ public: Deque(); ~Deque(); void push(T x); //插入双端队列的前端 T pop(); //删除前端元素并返回 T top() const; //前端元素 void inject(T x); //插入双端队列的尾端 T eject(); //从双端队列尾端删除并返回 T last() const; //尾端元素 int size() const; void printDeque() const; private: Node<T> *first; //双端队列的前端 Node<T> *end; //双端队列的尾端 int length; //双端队列长度 void freeDeque(); }; #endif
deque.cpp
#include <iostream> #include "deque.h" #include "dsexceptions.h" template<class T> Deque<T>::Deque(){ first = new Node<T>; end = new Node<T>; first->next = end; first->pre = NULL; end->next = NULL; end->pre = first; length = 0; } template<class T> Deque<T>::~Deque(){ freeDeque(); } //插入双端队列的前端 template<class T> void Deque<T>::push(T x){ Node<T> *r = first->next; Node<T> *t = new Node<T>; t->data = x; first->next = t; t->pre = first; t->next = r; r->pre = t; length++; } //删除前端元素并返回 template<class T> T Deque<T>::pop(){ if(first->next == end) throw DequeOverFlowException(); Node<T> *r = first->next; T data = r->data; first->next = r->next; r->next->pre = first; delete r; length--; return data; } //前端元素 template<class T> T Deque<T>::top() const{ if(first->next == end) throw DequeOverFlowException(); return first->next->data; } //插入双端队列的尾端 template<class T> void Deque<T>::inject(T x){ Node<T> *r = new Node<T>; r->next = NULL; r->pre = end; end->data = x; end->next = r; end = r; length++; } //从双端队列尾端删除并返回 template<class T> T Deque<T>::eject(){ if(first->next == end) throw DequeOverFlowException(); Node<T> *r = end->pre; int data = r->data; end->pre = r->pre; r->pre->next = end; delete r; length--; return data; } //尾端元素 template<class T> T Deque<T>::last() const{ if(first->next == end) throw DequeOverFlowException(); return end->pre->data; } template<class T> int Deque<T>::size() const{ return length; } template<class T> void Deque<T>::printDeque() const{ std::cout<<"["; Node<T> *r = first->next; while(r != end){ std::cout<<r->data<<" "; r = r->next; } std::cout<<"]"<<std::endl; } template<class T> void Deque<T>::freeDeque(){ Node<T> *r = first->next,*t; while(r != end){ t = r; r = r->next; delete t; } delete first; delete end; }
dsexceptions.h
#ifndef DSEXCEPTIONS_H #define DSEXCEPTIONS_H class DequeOverFlowException{ public: const char* what() const throw() { return "deque over flow exception, the size<=0 !\n"; } }; #endif
main.cpp
#include <iostream> #include "deque.cpp" using namespace std; int main(){ Deque<int> d; cout<<"前端操作:"<<endl; d.push(1); d.push(2); d.push(3); d.printDeque(); cout<<d.size()<<endl; cout<<d.top()<<endl; d.pop(); cout<<d.top()<<endl; cout<<"后端操作:"<<endl; d.inject(5); d.inject(6); d.inject(7); d.printDeque(); cout<<d.size()<<endl; cout<<d.last()<<endl; d.eject(); cout<<d.last()<<endl; d.printDeque(); }
b.无头尾结点实现
queue.h
//链表实现队列,不含有头尾结点 #ifndef QUEUE_H #define QUEUE_H template<class T> struct Node{ Node* next; T data; }; template<class T> class Queue{ public: Queue(); Queue(T a[], int n); ~Queue(); bool empty() const; //对是否为空 void enQueue(T x); //进队 T deQueue(); //出队 T queueFront() const; //返回队头元素 T queueRear() const; //返回队尾元素 int size() const; //队列大小 void printQueue() const;//打印队列 private: Node<T>* front; //队头,允许删除的一端 Node<T>* rear; //队尾,允许插入的一端 int length; //队长度 void freeQueue(); //释放队列 }; #endif
queue.cpp
#include <iostream> #include "queue.h" #include "dsexceptions.h" template<class T> Queue<T>::Queue(){ front = new Node<T>; front->next = NULL; rear = front; length = 0; } template<class T> Queue<T>::Queue(T a[], int n){ if(n == 0) Queue(); else{ front = new Node<T>; front->data = a[0]; front->next = NULL; rear = front; for(int i=1; i<n; i++){ Node<T>* r = new Node<T>; r->data = a[i]; rear->next = r; rear = r; } rear->next = NULL; length = n; } } template<class T> Queue<T>::~Queue(){ freeQueue(); } template<class T> bool Queue<T>::empty() const{ if(length == 0) return true; return false; } template<class T> void Queue<T>::enQueue(T x){ //注意不能使用rear == front判断,这样当队列为空,插入的元素始终在第一个位置 if(length == 0) front->data = x;//不含有队头队尾,故而都要存储元素 else{ Node<T>* r = new Node<T>; r->data = x; r->next = NULL; rear->next = r; rear = r; } length++; } template<class T> T Queue<T>::deQueue(){ T data; if(length == 0){ throw QueueEmptyException(); }else{ data = front->data; //当为1的时候front==rear,我们不能将其删除,要保留front rear if(length == 1){ front->data = 0; }else{ Node<T>* r = front; front = r->next; delete r; } length--; } return data; } template<class T> T Queue<T>::queueFront() const{ if(length == 0){ throw QueueEmptyException(); }else{ return front->data; } } template<class T> T Queue<T>::queueRear() const{ if(length == 0){ throw QueueEmptyException(); }else{ return rear->data; } } template<class T> int Queue<T>::size() const{ return length; } template<class T> void Queue<T>::printQueue() const{ Node<T>* r = front; std::cout<<"["; while(r){ //当front==rear的时候还有可能是空,此时没有删除front,rear if(length == 0) break; std::cout<<r->data<<" "; r = r->next; } std::cout<<"]"<<std::endl; } template<class T> void Queue<T>::freeQueue(){ Node<T>* r = front, *t; while(r){ t = r; r = r->next; delete t; } }
esexceptions.h
#ifndef DSEXCEPTIONS_H #define DSEXCEPTIONS_H class QueueEmptyException{ public: const char* what() const throw() { return "queue empty exception, the size<=0 !\n"; } }; #endif
main.cpp
#include <iostream> #include "queue.cpp" using namespace std; int main(){ try{ Queue<int> q; cout<<q.empty()<<endl; cout<<q.size()<<endl; q.printQueue(); q.enQueue(1); q.enQueue(2); cout<<q.size()<<endl; cout<<"出队"<<q.deQueue()<<endl; cout<<q.size()<<endl; q.printQueue(); cout<<"出队"<<q.deQueue()<<endl; cout<<q.size()<<endl; //q.deQueue(); int a[] = {1,2,3,4,5}; Queue<int> p(a, 5); cout<<p.empty()<<endl; cout<<p.size()<<endl; p.printQueue(); p.deQueue(); p.deQueue(); p.deQueue(); p.enQueue(6); p.printQueue(); cout<<p.size()<<endl; cout<<"出队"<<p.deQueue()<<endl; cout<<p.size()<<endl; p.printQueue(); }catch(QueueEmptyException &e){ cout<<e.what(); } return 0; }
c.循环队列实现
queue.h
//链表实现队列,不含有头尾结点 #ifndef QUEUE_H #define QUEUE_H template<class T> class Queue{ public: Queue(int n); Queue(T a[], int n, int length); ~Queue(); bool empty() const; //对是否为空 void enQueue(T x); //进队 T deQueue(); //出队 T queueFront() const; //返回队头元素 T queueRear() const; //返回队尾元素 int size() const; //队列大小 void printQueue() const;//打印队列 private: int front; //队头,允许删除的一端 int rear; //队尾,允许插入的一端 int max; //队列固定长度 int length; //队长度 T* array; //队列数组 }; #endif
queue.cpp
#include <iostream> #include "queue.h" #include "dsexceptions.h" template<class T> Queue<T>::Queue(int n){ array = new T[n]; length = 0; max = n; rear = front = -1; } template<class T> Queue<T>::Queue(T a[], int n, int len){ if(n>= len) throw QueueOverFlowException(); array = new T[len]; for(int i=0; i<n; i++) array[i] = a[i]; length = n; max = len; front = 0; rear = n-1; } template<class T> Queue<T>::~Queue(){ delete[] array; } template<class T> bool Queue<T>::empty() const{ if(length == 0) return true; return false; } template<class T> void Queue<T>::enQueue(T x){ if(length == max) //1.队满 throw QueueOverFlowException(); if(length == 0){ //2.队空 rear++; if(rear > max-1) rear %= max; array[rear] = x; front++;//此时队不空,front和rear指向同一个位置 } else{ //3.其他 rear ++; if(rear > max-1) rear %= max; array[rear] = x; } length++; } template<class T> T Queue<T>::deQueue(){ T data; if(length == 0){ throw QueueEmptyException(); }else{ data = array[front]; if(length == 1) front = rear = -1; //将front,rear置为-1表示为空 front++; if(front > max-1) front %= max; length--; } return data; } template<class T> T Queue<T>::queueFront() const{ if(length == 0){ throw QueueEmptyException(); }else{ return array[front]; } } template<class T> T Queue<T>::queueRear() const{ if(length == 0){ throw QueueEmptyException(); }else{ return array[rear]; } } template<class T> int Queue<T>::size() const{ return length; } template<class T> void Queue<T>::printQueue() const{ int a = front, b = length; std::cout<<"["; while(b){ b--; std::cout<<array[a++]<<" "; if(a > max-1) a %= max; } std::cout<<"]"<<std::endl; }
dsexceptions.h
#ifndef DSEXCEPTIONS_H #define DSEXCEPTIONS_H class QueueEmptyException{ public: const char* what() const throw() { return "queue empty exception, the size<=0 !\n"; } }; class QueueOverFlowException{ public: const char* what() const throw() { return "queue over flow exception, the size over the capacity !\n"; } }; #endif
main.cpp
#include <iostream> #include "queue.cpp" using namespace std; int main(){ try{ int a[] = {1,2,3,4,5}; Queue<int> p(a, 5, 7); cout<<p.empty()<<endl; cout<<p.size()<<endl; p.printQueue(); p.deQueue(); p.enQueue(6); p.enQueue(7); p.enQueue(8); //p.enQueue(9);//入队超出capacity p.printQueue(); cout<<p.size()<<endl; cout<<"出队"<<p.deQueue()<<endl; cout<<p.size()<<endl; p.printQueue(); }catch(QueueEmptyException &e){ cout<<e.what(); }catch(QueueOverFlowException &e){ cout<<e.what(); } return 0; }
发表评论
-
排序方法总结
2012-08-12 11:34 1133这里面包含了所有常见的排序操作 1.性能等比较分析 2 ... -
常见字符串操作大全
2012-08-12 11:34 14181.常见的字符串操作 如计算长度,求子串等都是考验基本功的, ... -
KMP算法解析
2012-08-12 11:35 2774一.理论基础 1.什么 ... -
二叉堆的实现
2012-08-12 11:35 11741.堆的概念 这里只需要注意两点: a.堆的存储方式:就是 ... -
set和map的简单实现
2012-08-10 11:35 12761.Set的简单实现 set是利用二叉查找树来实现的,而且为 ... -
红黑树的插入总结
2012-08-10 11:25 9071.红黑树 这个在july的博客中有详尽的说明,我就不在赘述 ... -
B-树实现
2012-08-10 11:03 15871.什么是B-树? 这个在我的前一篇博客中已经详细的阐释过: ... -
平衡二叉树
2012-08-10 10:39 27941.问题描述 什么是平衡 ... -
二叉排序树
2012-08-10 10:25 14171.基本概念 二叉排 ... -
B-树
2012-07-04 22:48 56111.B-树的概念 是一种多 ... -
构造哈夫曼树
2012-07-04 10:40 11881.算法说明 就是建造哈夫曼树树,从而使得构造出的树带权路径 ... -
线索二叉树
2012-07-04 09:20 12371.算法描述 就是简单的线索二叉树的建立,遍历,查找等基本操 ... -
二叉树基本操作大全
2012-07-03 18:22 25551.二叉树的基本操作 这里我有一个疑问: 在使用构造 ... -
栈的各种实现
2012-06-28 16:34 10751.算法描述 a.实现二个栈,在一个数组里面,除非没有任何空 ... -
中缀表达式转换为后缀
2012-06-28 11:10 17511.算法描述 例如a+b*c这是常见的中缀表达式,但是 ... -
后缀表达式的值
2012-06-27 16:33 12891.算法描述 计算后缀表达式的值 2.事例 如:( ... -
Josephus问题
2012-06-21 15:30 9541.算法描述 简单的游戏:有N个人坐成一圈,编号1-N、从编 ... -
关于最长递增子序列的实际应用--动态规划
2012-06-07 11:35 1788参考链接: a.http://www.programfan. ... -
线性查找二维数组
2012-06-05 17:23 10001.算法描述 有序(行有序,列有序,且每行从左至右递增 ... -
整数的随机置换
2012-06-05 15:10 2231算法描述:生成前N个整 ...
相关推荐
链表 链表_使用Python基于链表实现的多种队列数据结构比较
(3) 撰写实验报告,给出算法思路或流程图和具体实现(源程序)、算法分析结果(包括时间复杂度、空间复杂度以及算法优化设想)、输入数据及程序运行结果(必要时给出多种可能的输入数据和运行结果)。
基于mininet实现针对不同QoS 需求的多种队列调度机制;包括SFQ,PQ,LLQ等
邮件发送服务,文本、附件、模版多种实现,队列,线程定时任务功能
里面含有栈和队列的一些基本操作,和六种不同的方法表示杨辉三角!
例如车站候车、医院候诊、等候理发等各种排队现象都可以通过程序进行仿真,并由此预测客流等多种经营指标,为经办人的决策提供有价值的量化指标。队列结构有着其本身极其特殊的特点:先进先出(First in First out...
MQSeries 应用程序可使用多种编程语言和风格进行开发。程序化和面向对象的编程可 通过Visual Basic、C、C++、Java、以及COBOL 来实现。Microsoft Windows NT ActiveX/COM 技术也同样可对其进行支持。 无论多么庞大或...
数据结构实验 队列 c语言写的控制台程序 实现了对队列的多种基本操作
Laravel可配置多种队列驱动,包括 “sync”, “database”, “beanstalkd”, “sqs”, “redis”, “null”(具体参见app/config/queue.php) 其中sync为同步,database为使用数据库,后面三种为第三方队列服务,...
优先队列的实现方式有多种,其中基于堆的实现是最常见和最高效的。堆是一种特殊的完全二叉树,满足堆属性:对于最大堆,父节点的值总是大于或等于其子节点的值;对于最小堆,父节点的值总是小于或等于其子节点的值。...
以开沟机为背景,程序结合了队列、通知器、状态机等多种结构,实现了参数(两个模拟量、一个脉冲量)的采集、控制的输出(模拟量输出)以及数据的保存。版本已经改为8.6版,大家一同交流学习,共同进步!(In the ...
RabbitMQ是一个开源的AMQP实现,服务器端用Erlang语言编写,支持多种客户端,如:Python、Ruby、.NET、Java、JMS、C、PHP、ActionScript、XMPP、STOMP等,支持AJAX。用于在分布式系统中存储转发消息,在易用性、扩展...
RabbitMQ是由erlang语言开发,基于AMQP(Advanced Message Queue 高级消息队列协议)协议实现的消息队列,它是一种应用程序之间的通信方法,消息队列在分布式系统开发中应用非常广泛。 MQ 为Message Queue , 消息...
剑指Offer(Python多种思路实现):队列的最大值 面试59题: 题目:队列的最大值。 题目一:滑动窗口的最大值。 给定一个数组和滑动窗口的大小,请找出所有滑动窗口里的最大值。例如:如果输入数组为[2,3,4,2,6,2,5,1]...
2.支持多种消息类型,例如队列消息、主题消息、延时消息,还可以设置优先级。 3.系统体积小,整个系统才不到3M。 4.支持高并发。 ### 待优化 1.延迟消息BUG:延时消息基于jdk自带的delayQueue实现,系统宕机重启...
RabbitMQ是一个开源的AMQP实现,服务器端用Erlang语言编写,支持多种客户端,如:Python、Ruby、.NET、Java、JMS、C、PHP、ActionScript、XMPP、STOMP等,支持AJAX。用于在分布式系统中存储转发消息,在易用性、扩展...
在Python中有多种可以实现栈的数据结构。 1、list list是Python内置的列表数据结构,它支持栈的特性,有入栈和出栈操作。只不过用list实现栈性能不是特别好。 因为list内部是通过一个动态扩容的数组来实现的。当...
针对目前AMI复合通信网络对多种通信传输协议接入兼容性不佳,通信准确性和实时性难以兼顾的问题,设计了一种基于消息队列遥测传输(MQTT)协议族的AMI通信支撑平台,以实现在含电力线载波、RS485、GPRS和TCP/IP 的复合...
多种实现方式可能导致代码重复,缺陷和行为差异以及缩短上市时间。 此处的目标是将有用的通用队列功能整合到一个共享的库中,店面实现可轻松利用该库,从而提高质量并缩短需要队列的新功能的上市时间。 特征 将...