hao3100590
- 浏览: 128646 次
- 性别:
- 来自: 成都
-
最新评论
-
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 1131这里面包含了所有常见的排序操作 1.性能等比较分析 2 ... -
常见字符串操作大全
2012-08-12 11:34 14161.常见的字符串操作 如计算长度，求子串等都是考验基本功的， ... -
KMP算法解析
2012-08-12 11:35 2773一.理论基础 1.什么 ... -
二叉堆的实现
2012-08-12 11:35 11721.堆的概念 这里只需要注意两点： a.堆的存储方式：就是 ... -
set和map的简单实现
2012-08-10 11:35 12751.Set的简单实现 set是利用二叉查找树来实现的,而且为 ... -
红黑树的插入总结
2012-08-10 11:25 9051.红黑树 这个在july的博客中有详尽的说明，我就不在赘述 ... -
B-树实现
2012-08-10 11:03 15861.什么是B-树？ 这个在我的前一篇博客中已经详细的阐释过： ... -
平衡二叉树
2012-08-10 10:39 27931.问题描述 什么是平衡 ... -
二叉排序树
2012-08-10 10:25 14151.基本概念 二叉排 ... -
B-树
2012-07-04 22:48 56091.B-树的概念 是一种多 ... -
构造哈夫曼树
2012-07-04 10:40 11871.算法说明 就是建造哈夫曼树树，从而使得构造出的树带权路径 ... -
线索二叉树
2012-07-04 09:20 12371.算法描述 就是简单的线索二叉树的建立，遍历，查找等基本操 ... -
二叉树基本操作大全
2012-07-03 18:22 25541.二叉树的基本操作 这里我有一个疑问： 在使用构造 ... -
栈的各种实现
2012-06-28 16:34 10731.算法描述 a.实现二个栈，在一个数组里面，除非没有任何空 ... -
中缀表达式转换为后缀
2012-06-28 11:10 17501.算法描述 例如a+b*c这是常见的中缀表达式，但是 ... -
后缀表达式的值
2012-06-27 16:33 12891.算法描述 计算后缀表达式的值 2.事例 如：（ ... -
Josephus问题
2012-06-21 15:30 9531.算法描述 简单的游戏：有N个人坐成一圈，编号1-N、从编 ... -
关于最长递增子序列的实际应用--动态规划
2012-06-07 11:35 1788参考链接： a.http://www.programfan. ... -
线性查找二维数组
2012-06-05 17:23 9991.算法描述 有序（行有序，列有序，且每行从左至右递增 ... -
整数的随机置换
2012-06-05 15:10 2230算法描述:生成前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 的复合...
多种实现方式可能导致代码重复，缺陷和行为差异以及缩短上市时间。 此处的目标是将有用的通用队列功能整合到一个共享的库中，店面实现可轻松利用该库，从而提高质量并缩短需要队列的新功能的上市时间。 特征 将...