数据结构：循环队列(C语言实现).doc

(完整word)数据结构：循环队列(C语言实现)数据结构:循环队列（C语言实现）生活中有很多队列的影子，比如打饭排队，买火车票排队问题等，可以说与时间相关的问题，一般都会涉及到队列问题；从生活中，可以抽象出队列的概念，队列就是一个能够实现“先进先出”的存储结构。队列分为链式队列和静态队列;静态队列一般用数组来实现，但此时的队列必须是循环队列，否则会造成巨大的内存浪费；链式队列是用链表来实现队列的。这里讲的是循环队列，首先我们必须明白下面几个问题一、循环队列的基础知识1。循环队列需要几个参数来确定循环队列需要2个参数，front和rear2。循环队列各个参数的含义（1）队列初始化时，front和rear值都为零;(2）当队列不为空时，front指向队列的第一个元素，rear指向队列最后一个元素的下一个位置；（3)当队列为空时，front与rear的值相等，但不一定为零;3.循环队列入队的伪算法(1）把值存在rear所在的位置；（2）rear=（rear+1）%maxsize ，其中maxsize代表数组的长度;程序代码:cppview plaincopy1. boolEnqueue（PQUEUEQ，intval)2. 3. if(FullQueue（Q)）4. returnfalse；5. else6. 7. Q-pBaseQrear=val；8. Qrear=(Qrear+1)Q-maxsize;9. returntrue;10. 11. 4。循环队列出队的伪算法（1）先保存出队的值；（2）front=（front+1)maxsize ，其中maxsize代表数组的长度；程序代码：cppview plaincopy1. boolDequeue（PQUEUEQ,intval）2. 3. if（EmptyQueue（Q)）4. 5. returnfalse；6. 7. else8. 9. val=QpBaseQfront;10. Qfront=(Q-front+1）%Qmaxsize；11. returntrue；12. 13. 5。如何判断循环队列是否为空if（front=rear）队列空；else 队列不空；cppview plaincopy1. boolEmptyQueue(PQUEUEQ)2. 3. if(Qfront=Q-rear)/判断是否为空4. returntrue;5. else6. returnfalse;7. 6.如何判断循环队列是否为满 这个问题比较复杂,假设数组的存数空间为7，此时已经存放1,a，5，7,22，90六个元素了,如果在往数组中添加一个元素,则rear=front;此时，队列满与队列空的判断条件front=rear相同,这样的话我们就不能判断队列到底是空还是满了；解决这个问题有两个办法:一是增加一个参数，用来记录数组中当前元素的个数;第二个办法是,少用一个存储空间，也就是数组的最后一个存数空间不用，当(rear+1）maxsiz=front时，队列满；cppview plaincopy1. boolFullQueue(PQUEUEQ）2. 3. if（Q-front=(Q-rear+1）%Qmaxsize）/判断循环链表是否满,留一个预留空间不用4. returntrue；5. else6. returnfalse；7. 附录：queue。h文件代码：cppview plaincopy1. #ifndef_QUEUE_H_2. #define_QUEUE_H_3. typedefstructqueue4. 5. intpBase；6. intfront;/指向队列第一个元素7. intrear;/指向队列最后一个元素的下一个元素8. intmaxsize;/循环队列的最大存储空间9. QUEUE，PQUEUE；10. 11. voidCreateQueue（PQUEUEQ，intmaxsize）;12. voidTraverseQueue（PQUEUEQ）;13. boolFullQueue（PQUEUEQ)；14. boolEmptyQueue（PQUEUEQ)；15. boolEnqueue（PQUEUEQ,intval);16. boolDequeue（PQUEUEQ,int*val）;17. endifqueue。c文件代码:cppview plaincopy1. includestdio。h2. #includepBase=(int）malloc(sizeof(int)maxsize）；11. if(NULL=QpBase)12. 13. printf（”Memoryallocationfailure”)；14. exit(-1);/退出程序15. 16. Q-front=0；/初始化参数17. Q-rear=0；18. Q-maxsize=maxsize;19. 20. /*21. Function:Printthestackelement;22. */23. voidTraverseQueue(PQUEUEQ)24. 25. inti=Qfront；26. printf（队中的元素是：n）；27. while（i%Qmaxsize!=Qrear）28. 29. printf（”%d”,QpBasei）;30. i+；31. 32. printf(n”）;33. 34. boolFullQueue（PQUEUEQ）35. 36. if(Qfront=(Q-rear+1)Qmaxsize)/判断循环链表是否满，留一个预留空间不用37. returntrue；38. else39. returnfalse；40. 41. boolEmptyQueue(PQUEUEQ）42. 43. if（Q-front=Q-rear）/判断是否为空44. returntrue;45. else46. returnfalse;47. 48. boolEnqueue(PQUEUEQ，intval)49. 50. if(FullQueue（Q）51. returnfalse；52. else53. 54. QpBaseQrear=val;55. Qrear=（Q-rear+1）%Q-maxsize;56. returntrue;57. 58. 59. 60. boolDequeue(PQUEUEQ，int*val)61. 62. if(EmptyQueue(Q）63. 64. returnfalse;65. 66. else67. 68. *val=QpBaseQfront;69. Q-front=（Qfront+1）Q-maxsize;70. returntrue;71. 72.