滴水逆向联盟

标题: VC++2012编程演练数据结构《1》循环双端队列 [打印本页]

作者: 大灰狼 时间: 2014-9-24 08:33
标题: VC++2012编程演练数据结构《1》循环双端队列
循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。
队列的操作特点是“先进先出”。前者主要是头指针、尾指针的使用，后者主要是理解循环队列提出的原因及其特点。两者都要掌握队列空与满的判定条件以及出队列、入队列操作的实现。

为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。

我们基于VC++2012 IDE来实现之。

启动IDE

首先建立工程

实现代码如下

[cpp] view plaincopy

#include "stdafx.h"
//循环双端队列顺序表示
#include <iostream>
#include <iomanip>
#include <assert.h>
using namespace std;
template <class T> class DoubleQueue
{ int end1,end2;//end1和end2为端点
T *data;
int size;
public:
DoubleQueue(int sz=10);
~DoubleQueue(){delete[] data;}
void Enqueue(T item,int end);
void Dequeue(int end);
int IsEmpty(){return end1==end2;}
int IsFull(){return (end1+1)%size==end2;}
void list(int end);
};
//循环双端队列操作
template <class T>
DoubleQueue <T>::DoubleQueue(int sz):
end1(0),end2(0),size(sz){
data=new T[size];assert(data!=0);
}
//循环双端队列插入新元素操作
template <class T>
void DoubleQueue <T>::Enqueue(T item,int end)
{ assert(!IsFull());
if(end==1){
end1=(end1+1)%size;
data[end1]=item;}
else{
data[end2]=item;
end2=(end2-1+size)%size;}
}
// 循环双端队列删除操作
template <class T>
void DoubleQueue <T>::Dequeue(int end)
{ assert(!IsEmpty());
if(end==1){
end1=(end1+size-1)%size;}
else{
end2=(end2+1)%size;}
}
// 循环双端队列输出操作
template <class T>
void DoubleQueue <T>::list(int end)
{ if(end==1){
for(T p=(end2+1)%size;p<=end1;p=(p+1)%size)
cout<<setw(3)<<data[p];
cout<<endl;}
else{
for(T p=end1;p!=end2;p=(p+size-1)%size)
cout<<setw(3)<<data[p];
cout<<endl;}
}
//循环双端队列的测试
void main()
{
DoubleQueue <int> Q;
cout<<"运行结果:\n";
//向队列end1插入4,5,6,7,8 三个元素
Q.Enqueue(4,1);
Q.Enqueue(5,1);
Q.Enqueue(6,1);
Q.Enqueue(7,1);
Q.Enqueue(8,1);
cout<<"输出向队列end1插入4,5,6,7,8三个元素后情况:\n";
Q.list(1);
// 删除最后插入的2个元素
Q.Dequeue(1);
Q.Dequeue(1);
cout<<"输出删除最后2个元素后的队列end1的情况:\n";
Q.list(1);
//向队列end2插入7,8,9,10,11 三个元素
Q.Enqueue(7,2);
Q.Enqueue(8,2);
Q.Enqueue(9,2);
Q.Enqueue(10,2);
Q.Enqueue(11,2);
cout<<"输出向队列end2插入7,8,9,10,11三个元素后情况:\n";
Q.list(2);
cin.get();
}

欢迎光临滴水逆向联盟 (http://www.dtdebug.com/)