循环队列存储空间传统扩充与动态扩充之优劣.doc

循环队列存储空间传统扩充与动态扩充之优劣摘要：循环队列在定义时总是事先规定一个最大值maxsize来确定队列的最大存储空间，在使用中若初始值maxsize太小会造成存储空间不够用的问题。一般的做法是停止程序的执行，修改maxsize的值。若maxsize太大则会造成存储空间的浪费，不能实现动态扩充的目的。在此提出了一种新的实现循环队列存储空间动态扩充的方法，解决了存储空间不够用的问题，同时也成功地避免了循环队列中存储空间的浪费问题。最后比较了此方法与传统方法的优劣。关键词：循环队列；存储空间；动态分配；自动扩充the advantages and disadvantages of the traditional expansion and dynamic expansion for circular queue storage spacezhang haixia(zhangye medical college,zhangye734000,china)abstract:the circular queue definition is always predetermined a maximum value of maxsize to determine the maximum storage space of the queue,use the initial value of maxsize is too small will cause the problem of not enough storage space.the general practice is to stop the implementation of the program,modify the value of maxsize.if maxsize is too large will result in a waste of storage space,can not achieve the purpose of dynamically expanding.put forward a new dynamically expanding circular queue storage space to solve the problem of not enough storage space,but also succeeded in avoiding the waste of storage space in the circular queue.finally,a comparison of the pros and cons of this method with the traditional method.keywords:circular queue;storage space;dynamically allocated;automatically expand在限定性线性表队列的顺序存储结构中，使用队列时都要将队列从逻辑上看成一个环即循环队列。这样是为了克服“假上溢”现象，节省计算机的存储空间。循环队列在定义时总是事先规定一个最大值maxsize来确定队列的最大存储空间，在使用中若初始值maxsize太小会造成存储空间不够用的问题。一般的做法是停止程序的执行，修改maxsize的值。若maxsize太大则会造成存储空间的浪费，不能实现动态扩充的目的。有没有方法能让队列在使用中想占用多少空间就占用多少空间，实现自动扩充，最大程度地避免对内存空间的浪费呢？以解决此问题为目的，本文提出了一种新的实现循环队列存储空间动态扩充的方法，解决了存储空间不够用的问题，同时也成功地避免了循环队列中存储空间的浪费问题。一、传统扩充方法循环队列的存储结构及基本操作定义如下：#define maxsize 50/循环队列的初始大小typedef structelemtype elemmaxsize； /循环队列的存储空间int front ，rear；/循环队列的队头和队尾指针 seqqueue；statusinitqueue(seqqueue *q) /循环队列初始化操作传统算法描述q-front=q-rear=0； return ok；statusenterqueue(seqqueue *q，elemtype e)/循环队列入队操作算法描述if(q-rear+1)%maxsize=q-front) /队满则不能入队return error；q-elemq-rear=e；q-rear=(q-rear+1)%maxsize；return ok；statusdeletequeue(seqqueue *q，elementtype *e)/循环队列出队操作算法描述if(q-rear=q-front)/队空不能出队return error；*e=q-elementq-front；q-front=(q-front+1)%maxsize；return ok；int queuelength(seqqueue q)/循环队列求队长操作算法描述return (q.rear-q.front+maxsize)%maxsize)；在循环队列的应用中，如果数据元素有进有出，且存储在队列中的元素个数始终小于maxsize时，上述的操作完全可以解决。但是若数据元素把空间都占满又有元素需要入队，那么上述算法就无法解决了，只能出现“溢出”，数据元素入队不成功。有人会认为可以在定义maxsize时将其放大到最大程度，但会发现maxsize越大，造成的空间浪费就越大；也有人会提出在空间不够用时，停止程序的执行，再将maxsize放大一些，但是在一些大型系统开发中，系统一旦投入运行，就很难停止下来。二、动态扩充方法针对上面的问题，可以将elemtype定义为指针类型*elem，而非数组，这样就不需要对循环队列设置最大值maxsize，而是给循环队列设置初始值queue_init_size，通过c语言提供的动态内存函数malloc，给该指针分配存储空间，且附设一个size来表示该空间的当前大小，若在程序执行中出现队满的情况，可以通过realloc函数将该空间进行扩充，使其增加increment个单元。其新的类型定义如下：#define queue_init_size 20/循环队列存储空间的初始分配量# define increment 5/循环队列存储空间的分配增量typedef structelemtype *elem；/存储空间基址int front，rear； /队头和队尾的当前位置int size； /当前分配的存储容量seqqueue；依照上述定义方法，在进行循环队列的初始化时，需要调用malloc函数开辟队列的初始空间。其描述如下：int initqueue(seqqueue *q)q-elem=(elemtype *)malloc(queue_init_size*sizeof(elemtype)；if(!q-elem)return error；q-front=q-rear=0；q-size=queue_init_size；return ok；研究队列的基本操作会发现，只有在数据元素入队时才会出现存储空间不够用的问题。若循环队列中数据元素不足q-size-1个，则按常规操作让元素入队。否则，若循环队列中已有q-size-1个元素，即q-rear的后面一个位置是q-front，则表示队满需拓展，这时可以通过realloc函数扩充队列的存储空间，扩充的具体方法为：首先通过realloc函数让q-elem所指的单元增加increment；若出现q-frontq-rear，此时需要把从q-front开始到q-size-1结束的cnt个数据元素移向q-size+increment-cnt-1到q-size+increment-1单元。最后再修改q-size的值为q-size+increment，修改q-front的值为q-front-cnt。这样队列得到自动扩充，再按传统方法进行入队。其算法描述如下：int enterqueue(seqqueue *q，elemtype e)int i，j，cnt；elemtype *newbase；if(q-rear+1)%q-size)=q-front)/队列已满，需要进行存储空间扩充newbase=(elemtype*)realloc(q-elem，(q-size+increment)*sizeof(elemtype)；if(!newbase)return error；q-elem=newbase；if(q-frontq-rear)for(i=q-size-1，j=q-size+increment-1；i=q-front；i-，j-)q-elemj=q-elemi；cnt=q-size-q-front；q-size=q-size+increment；q-front=q-size-cnt；elseq-size=q-size+increment；q-elemq-rear=e；q-rear=(q-rear+1)%q-size；return ok；上述方法其实质是将线性表链式存储结构中的空间动态分配操作应用到了循环队列中。当不能确定进入循环队列中的数据元素的最大个数时，可以用此种方法设置初值，再根据具体情况设置增量，这样就可以最大程度地避免对内存的浪费。此方法的出队、判空、求队长等操作同传统方法无异。只是将传统方法中用到的maxsize变为q-size，此处不再赘述。三、优劣性比较在循环队列的应用中，若需要存储在队列中元素个数有确定的上限，则完全可以用传统方法解决。将此上限作为循环队列的容量maxsize来用。通过以上分析论述，可以看到动态分配方法与传统方法