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

循环队列存储空间传统扩充与动态扩充之优劣 摘要：循环队列在定义时总是事先规定一个最大值maxsize来确定队列的最大存储空间，在使用中若初始值maxsize太小会造成存储空间不够用的问题。一般的做法是停止程序的执行，修改maxsize的值。若maxsize太大则会造成存储空间的浪费，不能实现动态扩充的目的。在此提出了一种新的实现循环队列存储空间动态扩充的方法，解决了存储空间不够用的问题，同时也成功地避免了循环队列中存储空间的浪费问题。最后比较了此方法与传统方法的优劣。 关键词：循环队列；存储空间；动态分配；自动扩充 the advantages and disadvantages of the traditional expansion and dynamic expansion for circular queue storage space zhang 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 struct { elemtype elem[maxsize]； //循环队列的存储空间 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-elem[q-rear]=e； q-rear=(q-rear+1)%maxsize； return ok； } statusdeletequ