hao3100590
- 浏览: 131462 次
- 性别:
- 来自: 成都
-
最新评论
-
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 1176这里面包含了所有常见的排序操作 1.性能等比较分析 2 ... -
常见字符串操作大全
2012-08-12 11:34 14601.常见的字符串操作 如计算长度，求子串等都是考验基本功的， ... -
KMP算法解析
2012-08-12 11:35 2835一.理论基础 1.什么 ... -
二叉堆的实现
2012-08-12 11:35 12101.堆的概念 这里只需要注意两点： a.堆的存储方式：就是 ... -
set和map的简单实现
2012-08-10 11:35 13161.Set的简单实现 set是利用二叉查找树来实现的,而且为 ... -
红黑树的插入总结
2012-08-10 11:25 14051.红黑树 这个在july的博客中有详尽的说明，我就不在赘述 ... -
B-树实现
2012-08-10 11:03 16241.什么是B-树？ 这个在我的前一篇博客中已经详细的阐释过： ... -
平衡二叉树
2012-08-10 10:39 28481.问题描述 什么是平衡 ... -
二叉排序树
2012-08-10 10:25 14751.基本概念 二叉排 ... -
B-树
2012-07-04 22:48 56661.B-树的概念 是一种多 ... -
构造哈夫曼树
2012-07-04 10:40 12301.算法说明 就是建造哈夫曼树树，从而使得构造出的树带权路径 ... -
线索二叉树
2012-07-04 09:20 12731.算法描述 就是简单的线索二叉树的建立，遍历，查找等基本操 ... -
二叉树基本操作大全
2012-07-03 18:22 26031.二叉树的基本操作 这里我有一个疑问： 在使用构造 ... -
栈的各种实现
2012-06-28 16:34 11091.算法描述 a.实现二个栈，在一个数组里面，除非没有任何空 ... -
中缀表达式转换为后缀
2012-06-28 11:10 18251.算法描述 例如a+b*c这是常见的中缀表达式，但是 ... -
后缀表达式的值
2012-06-27 16:33 13321.算法描述 计算后缀表达式的值 2.事例 如：（ ... -
Josephus问题
2012-06-21 15:30 9961.算法描述 简单的游戏：有N个人坐成一圈，编号1-N、从编 ... -
关于最长递增子序列的实际应用--动态规划
2012-06-07 11:35 1830参考链接： a.http://www.programfan. ... -
线性查找二维数组
2012-06-05 17:23 10301.算法描述 有序（行有序，列有序，且每行从左至右递增 ... -
整数的随机置换
2012-06-05 15:10 2318算法描述:生成前N个整 ...
相关推荐
在实际开发中，Java集合框架提供了多种队列实现，如`ArrayDeque`（适用于高性能的随机访问）、`PriorityQueue`（根据元素的自然排序或自定义比较器进行排序）等，可以根据具体需求选择合适的数据结构。此外，Java...
3. 高级数据结构实现：如Java的`java.util.Queue`接口，提供了多种队列实现，如`ArrayDeque`（基于数组的双端队列）、`LinkedList`（链表实现）等。 队列的应用场景： 1. 打印机任务调度：新任务入队，完成的任务出...
具体实现上，Java提供了多种队列实现，如`ArrayDeque`、`LinkedList`或`PriorityQueue`等。在排队叫号系统中，我们可能选择`LinkedBlockingQueue`，因为它是一个线程安全的队列，特别适合多线程环境。`...
### 数据结构：队列实现详解 #### 一、队列概念与特性 在计算机科学领域，**队列**是一种常见的线性数据结构，遵循先进先出（First In First Out, FIFO）的原则。也就是说，最早添加到队列中的元素将是最先被移除的...
- Java 提供了多种队列实现，如 `LinkedList`、`ArrayDeque` 和并发类 `ConcurrentLinkedQueue`、`LinkedBlockingQueue` 等。其中，`ConcurrentLinkedQueue` 是一个非阻塞的线程安全队列，而 `LinkedBlockingQueue`...
然而，这里提到的“消息队列实现”可能是指自定义实现的消息队列，而非Windows内建的消息系统。在VC中，可以使用多种数据结构，如链表或队列，来实现一个自定义的消息队列。消息通常包含一个消息类型标识和相关的...
它可能包含了上述某一种或多种队列的实现，例如用C++、Java或其他编程语言实现的简单队列、阻塞队列、并发队列等。具体的实现细节需要查看源代码才能得知。 在实际应用中，队列常被用于任务调度、消息传递、网络...
Java提供了多种队列实现，但它们都基于两个主要的接口：`Queue` 和 `Deque`。`Queue` 是基本的队列接口，而 `Deque`（双端队列）提供了更丰富的功能，包括在两端添加和删除元素。`LinkedList` 类实现了这两个接口，...
在这个“用消息队列实现的简单聊天程序”中，我们可以探讨以下几个关键知识点： 1. **消息队列的概念**：消息队列是一种存储和转发的机制，它在不同的进程或系统之间作为数据传输的桥梁。当一个进程生成消息时，它...
Java提供了多种队列实现，如ArrayDeque、LinkedList（通过其offer、poll方法）等。特别地，PriorityQueue允许根据优先级处理元素。 6. **二叉搜索树**：二叉搜索树是一种特殊的二叉树，其中每个节点的左子树只包含...
`java.util.Queue` 提供了多种队列实现，如 `ArrayBlockingQueue`, `LinkedBlockingQueue` 和 `PriorityQueue`。队列可以在多线程环境下安全地添加和移除元素，通常与 `ExecutorService` 结合使用，作为任务的提交和...
在这个Java队列实现的数据结构作业练习中，我们将会探讨如何使用Java来创建一个简单的队列，并分析`Queue.java`和`Node.java`这两个文件可能包含的内容。 首先，`Queue.java`很可能是实现队列接口或类的文件。在...
Java提供了多种内置数据结构，如LinkedList和ArrayDeque，来实现队列操作。然而，手动模拟队列可以帮助开发者更直观地理解其内部机制。 2 队列的Java实现 在Java中，队列的实现通常涉及以下核心操作： - 插入元素...
Java中的`java.util.Queue`接口提供了多种队列实现，如`ArrayDeque`、`LinkedList`和`PriorityQueue`。队列可以用于任务调度，例如，`ExecutorService`的`submit`方法将任务放入内部队列，由线程池按顺序处理。此外...
综上所述，多级反馈队列调度算法在操作系统中扮演着重要角色，它结合了多种调度策略，以适应不同类型的进程需求。通过理解其原理和实现细节，我们可以更好地设计和优化操作系统调度器，从而提高系统的整体效率。
提供的示例程序是一个简单的队列实现，使用了基本的数组结构。这种实现方式简单易懂，但在实际应用中可能需要考虑更多的情况，比如队列溢出或下溢等问题。为了更好地理解和实现队列，还需要了解以下几点： - **队列...
标题"**C#实现进程间通信（使用消息队列实现）**"主要探讨的是如何使用C#语言通过消息队列来实现在不同进程之间的通信。这种方法适用于那些需要进程独立性和消息缓冲的应用场景。 在C#中，我们可以使用System....
本资料包“链表-使用Python基于链表实现的多种队列数据结构比较”着重探讨了如何利用Python语言来实现不同类型的队列数据结构，其中队列是一种先进先出（FIFO）的数据结构，常用于任务调度、缓冲区管理和多线程通信...
在Java中，`java.util`包提供了多种队列实现，包括： 1. **LinkedList**：`java.util.LinkedList` 是一个双向链表，同时实现了`Deque`接口，可以作为队列使用。插入和删除操作的时间复杂度为O(1)，但在随机访问元素...
在编程中，很多编程语言提供了内置的队列实现，如C++中的`std::queue`容器，Java的`java.util.Queue`接口，Python的`collections.deque`等。不过，了解底层的实现原理可以帮助我们更好地理解和优化代码。 总的来说...