Data Structures with C++ using STL 2E Chapter 8

《Data Structures with C++ using STL 2E Chapter 8》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1MainIndexContentsModelforaQueueTheQueueQueueADT(3slides)RadixSort(2slides)miniQueue()BoundedQueuePriorityQueuePriorityQueueADT(2slides)Chapter8–QueuesandPriorityQueuesRemovingItemsfromaHeapSummarySlides(5slides)12MainIndexContentsGroceryStoreCheckout:AModelforaQue

2、ue23MainIndexContentsTheQueueAQueueisaFIFO(FirstinFirstOut)DataStructure.ElementsareinsertedintheRearofthequeueandareremovedattheFront.34MainIndexContentsCLASSqueueConstructorqueue();Createanemptyqueue.CLASSqueueOperationsboolempty()const;Checkwhether

3、thequeueisempty.Returntrueifitisemptyandfalseotherwise.T&lfront();Returnareferencetothevalueoftheitematthefontofthequeue.Precondition:Thequeueisnotempty.45MainIndexContentsCLASSqueueOperationsconstT&front()const;Constantversionoffront().voidpop();Removetheit

4、emfromthefrontofthequeue.Precondition:Thequeueisnotempty.Postcondition:Theelementatthefrontofthequeueistheelementthatwasaddedimmediatelyaftertheelementjustpoppedorthequeueisempty.56MainIndexContentsCLASSqueueOperationsvoidpush(constT&item);Inserttheargumenti

5、tematthebackofthequeue.Postcondition:Thequeuehasanewitematthebackintsize()const;Returnthenumberofelementsinthequeue.67MainIndexContentsTheRadixSortOrderten2digitnumbersin10binsfromsmallestnumbertolargestnumber.Requires2callstothesortAlgorithm.InitialSequence:916851

6、59235302239Pass0:Distributethecardsintobinsaccordingtothe1'sdigit(100).78MainIndexContentsTheRadixSortFinalSequence:91685159235302239Pass1:Takethenewsequenceanddistributethecardsintobinsdeterminedbythe10'sdigit(101).89MainIndexContents910MainIndexContentsTheBounded

7、queue10PriorityQueueASpecialformofqueuefromwhichitemsareremovedaccordingtotheirdesignatedpriorityandnottheorderinwhichtheyentered.Itemsenteredthequeueinsequentialorderbutwillberemovedintheorder#2,#1,#4,#3.1112MainIndexContentsCLASSpriority_queueConstructorpr

8、iority_queue();Createanemptypriorityqueue.TypeTmustimplementtheoperator<.CLASSpriority_queueOperationsboolempty()const;Checkwhethertheprio