《数据结构》读书笔记 第三章 非循环顺序队列2

比起第一个顺序非循环队列,这个是浪费空间,节约时间版本~

Queue.h:定义了队列的基本操作

#include <iostream>

enum {OK=0,WRONG=-1};
enum {QIS=10,QI=2};

typedef int Elem;
typedef int Status;
typedef struct
{
 Elem *base;
 int front;
 int rear;
 int qsize;
}Queue;

Status InitQueue(Queue &Q)
{
 Q.base=new Elem[QIS];
 if(Q.base==NULL)
  return WRONG;
 Q.front=Q.rear=0;
 Q.qsize=QIS;
 return OK;
}

void DestroyQueue(Queue &Q)
{
 delete Q.base;
 Q.base=NULL;
 Q.front=Q.qsize=Q.rear=0;
}

void ClearQueue(Queue &Q)
{
 Q.front=Q.rear=0;
}

bool QueueEmpty(Queue Q)
{
 return Q.rear-Q.front==0;
}

int QueueLen(Queue Q)
{
 return Q.rear-Q.front;
}

Status GetHead(Queue Q,Elem &e)
{
 if(QueueLen(Q)==0)
  return WRONG;
 e=Q.base[Q.front];
 return OK;
}

Status EnQueue(Queue &Q,Elem e)
{
 if(QueueLen(Q)>=Q.qsize)
 {
  Elem *p;
  p=new Elem[Q.qsize+QI];
  if(p==NULL)
   return WRONG;
  memcpy(p,Q.base,Q.qsize*sizeof(Elem));
  delete Q.base;
  Q.base=p;
  Q.qsize+=QI;
 }
 Q.base[Q.rear++]=e;
 return OK;
}

Status DeQueue(Queue &Q,Elem &e)
{
 if(QueueLen(Q)==0)
  return WRONG;
 e=Q.base[Q.front++];
 return OK;
}

void QueueTraverse(Queue Q,void(*vi)(Elem e))
{
 int i=Q.front,len=QueueLen(Q);
 while(i!=Q.rear)
 {
  vi(Q.base[i]);
  i++;
 }
}

 

Main.cpp:主程序

#include "Queue.h"

using namespace std;

void print(Elem e)
{
 cout<<e<<" ";
}

int main()
{
 Queue Q;
 InitQueue(Q);
 int i,k=7,tmp;
 for(i=1;i<=k;i++)
  EnQueue(Q,i);
 cout<<"入队<<k<<个元素\n遍历:";
 QueueTraverse(Q,print);
 cout<<endl;
 if(DeQueue(Q,tmp)==OK)
  cout<<"出队一个元素,值为"<<tmp<<endl;
 cout<<"遍历\n";
 QueueTraverse(Q,print);
 if(GetHead(Q,tmp)==OK)
  cout<<endl<<"队列的第一号是"<<tmp;
 cout<<endl<<"队列长度是"<<QueueLen(Q);
 cout<<endl<<"清空队列!";
 ClearQueue(Q);
 cout<<endl<<"队列是否为空(1为空,0为非空)"<<QueueEmpty(Q);
 cout<<endl;
 return 0;
}

Leave a Reply

Your email address will not be published.