当前位置:编程学习 > VC++ >>

VC++2012编程演练数据结构循环双端队列

循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。因此,无法通过条件front==rear来判别队列是"空"还是"满"。
队列的操作特点是“先进先出”。前者主要是头指针、尾指针的使用,后者主要是理解循环队列提出的原因及其特点。两者都要掌握队列空与满的判定条件以及出队列、入队列操作的实现。
为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。
我们基于VC++2012  IDE来实现之。
首先建立工程


实现代码如下

 

[cpp] 
#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(); 
 
 
 


补充:软件开发 , Vc ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,