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

终于是循环队列了,有点小麻烦,一定注意标红的几句不要忘记了!!

Queue.h:定义了基本操作

 

#include <iostream>

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

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)
{
 if(Q.base!=NULL)
  delete Q.base;
 Q.base=NULL;
 Q.front=Q.rear=0;
}

Status EnQueue(Queue &Q,Elem e)
{
 if((Q.rear+1)%Q.qsize==Q.front)
 {
  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;
  int i;

  //这个循环是把元素挪到高位,好为新元素入队腾出位置!

  for(i=Q.qsize-1;i>=Q.front;i–)
  {
   Q.base[i+QI]=Q.base[i];
  }
  Q.front+=QI;
  Q.qsize+=QI;
 }
 Q.base[Q.rear]=e;
 Q.rear=(Q.rear+1)%Q.qsize;

 return OK;
}

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

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

main.cpp:主程序

#include "Queue.h"

using namespace std;

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

int main()
{
 Queue Q;
 InitQueue(Q);
 int i,k=11,tmp;
 for(i=1;i<=k;i++)
 {
  if(EnQueue(Q,i)==OK)
   cout<<i<<" ";
 }

 DeQueue(Q,tmp);
 cout<<endl<<"遍历:";
 QueueTraverse(Q,print);
 return 0;
}

Leave a Reply

Your email address will not be published.