模板类的练习——队列

类别:编程语言 点击:0 评论:0 推荐:

队列的练习,单链队列、循环队列以及队列的各种基本操作。
#pragma once
#include <stdlib.h>
#include <malloc.h>
#define MAXQSIZE 10

template<class T>
class CQueue
{
public :
 CQueue();
 ~CQueue();
 //----------单链队列-------队列的链式存储结构
 typedef  struct _tagQNode
 {
  T data;
  struct _tagQNode* next;
 }QNode,*QueuePtr;

 static struct _tagQueue
 {
  QueuePtr front; //队头指针
  QueuePtr rear; //队尾指针
 };
 //----------循环队列-------队列的顺序存储结构
 static struct _tagSqQueue
 {
  T* base;
  int front;
  int rear;
 };

private:
 typedef _tagQueue LinkQueue,*LQueuePtr;
 typedef _tagSqQueue SqQueue;

public:
 // 初始化单链队列
 bool InitQueue(LinkQueue& q);
 void DestroyQueue(LinkQueue& q);
 void ClearQueue(LinkQueue& q);
 int  QueueEmpty(LinkQueue q);
 int  QueueLength(LinkQueue q);
 T GetHead(LinkQueue q);
 T GetRear(LinkQueue q);
 bool EnQueue(LinkQueue& q,T e);
 bool DeQueue(LinkQueue& q,T& e);
 //有待完成
 bool QueueTraverse(LinkQueue& q);
 //初始化循环队列
 bool InitSqQueue(SqQueue& q);
 void DestroySqQueue(SqQueue& q);
 void ClearSqQueue(SqQueue& q);
 int  SqQueueEmpty(SqQueue q);
 int  SqQueueLength(SqQueue q);
 T GetSqQueueHead(SqQueue q);
 T GetSqQueueRear(SqQueue q);
 bool EnSqQueue(SqQueue& q,T e);
 bool DeSqQueue(SqQueue& q,T& e);
 //有待完成
 bool SqQueueTraverse(SqQueue& q);
};

template<typename T>
CQueue<T>::CQueue()
{
}
template<typename T>
CQueue<T>::~CQueue()
{
}
template<class T>
bool CQueue<T>::InitQueue(LinkQueue& q)
{
 q.front = q.rear = new QNode;
 if(q.front == NULL)
  return false;
 q.front->next = NULL;
 return true;
}
template<class T>
bool CQueue<T>::InitSqQueue(SqQueue& q)
{
 q.base = new T[MAXQSIZE];
 if(q.base == NULL)
  return false;
 q.front = q.rear = 0;
 return true;
}
template<class T>
void CQueue<T>::DestroyQueue(LinkQueue& q)
{
 while(q.front)
 {
  q.rear = q.front -> next;
  free(q.front);
  q.front = q.rear;
 }
}
template<class T>
void CQueue<T>::DestroySqQueue(SqQueue& q)
{
 if( q.base != NULL)
  delete[] q.base;
}

template<class T>
void CQueue<T>::ClearQueue(LinkQueue& q)
{
 q.front = q.rear = NULL;
}
template<class T>
int CQueue<T>::QueueEmpty(LinkQueue q)
{
 if(q.front -> next !=null)
  return 0;
 return 1;
}
template<class T>
int CQueue<T>::SqQueueEmpty(SqQueue q)
{
 if(q.front != q.rear)
  return 0;
 return 1;
}
template<class T>
int CQueue<T>::SqQueueLength(SqQueue q)
{
 return (q.rear - q.front +MAXQSIZE ) % MAXQSIZE;
}
template<class T>
T CQueue<T>::GetHead(LinkQueue q)
{
 T e;
 e = q.front -> next->data;
 return e;
}
template<class T>
T CQueue<T>::GetSqQueueHead(SqQueue q)
{
 T e;
 e = *(q.base+q.front);
 return e;
}
template<class T>
T CQueue<T>::GetSqQueueRear(SqQueue q)
{
 T e;
 e = *(q.base+q.rear-1);
 return e;
}
template<class T>
T CQueue<T>::GetRear(LinkQueue q)
{
 T e=0;
 e = q.rear->data;
 return e;
}
template<class T>
bool CQueue<T>::EnQueue(LinkQueue& q,T e)
{
 QueuePtr tmp = new QNode;
 if(tmp == NULL)
  return false;
 tmp->data = e;
 tmp->next = NULL;
 
 q.rear->next = tmp;
 q.rear = tmp;
 return true;
}
template<class T>
bool CQueue<T>::EnSqQueue(SqQueue& q,T e)
{
 if((q.rear + 1)% MAXQSIZE == q.front)
  return false;
 *(q.base + q.rear ) = e;
 q.rear = (q.rear + 1) % MAXQSIZE;
 return true;
}

template<class T>
bool CQueue<T>::DeQueue(LinkQueue& q,T& e)
{
 QueuePtr temp = new QNode;
 if(temp == NULL)
 {
  return false;
 }
 else
 {
  temp = q.front -> next;
  e = temp -> data;
  q.front->next =temp->next;
  delete temp;
 }
 return true;
}
template<class T>
bool CQueue<T>::DeSqQueue(SqQueue& q,T& e)
{
 if( q.front == q.rear )
  return false;
 e = * (q.base + q.front);
 q.front = (q.front + 1)% MAXQSIZE;
 return true;
}

本文地址:http://com.8s8s.com/it/it25254.htm