数据结构队列Queues.docx

数据结构队列Queues.docx

《数据结构队列Queues.docx》由会员分享，可在线阅读，更多相关《数据结构队列Queues.docx（5页珍藏版）》请在冰点文库上搜索。

数据结构队列Queues

Queues

ImportantpointstorememberaboutaQueue:

Queue–FIFO–First-In-First-OutDS

AQueueisaDataStructurewhereyoucaninsertfromoneendcalled“REAR”anddeletefromtheotherendcalled“FRONT”.

ImplementationofaQueue:

a）Asanarray–staticDS

i）LinearQueueusesLineararray

ii）CircularQueueusesCirculararray

b）AsaLinkedList–dynamicDS

a）Implementationofaqueue:

Asanarray

WhentheQueueisempty:

Front=-1

Rear=-1

WhentheQueuehasonlyoneitem:

Front=0

Rear=0

WhentheQueuehasmorethanoneitem:

Front=0

Rear>0

1.QueueOverflow:

TryingtoInsertanelementinaqueuewhenthequeueisFULL.

Thisconditionshouldnotarise.Toavoidthiserrorcondition,alwayscheckforthepositionofREARbeforeinsertinganewvalueinthequeue.IfREAR=max-1（thelastindexpositionofthearray）---->thismeanstheREARhasreachedthemaximumsizeofthearrayandthereisnomorespaceforthenewdata.

2.QueueUnderflow:

Tryingtodeleteanitemfromanemptyqueue.

InordertoavoidthiserrorsituationalwayscheckforFront=-1beforetryingtodeleteanyvalue.

AlgorithmforinsertingdatainaLinearQueue（asanarray）:

1.Ifrear=max-1

//maxisthemaximumsizeofthearrayandwecheckwithmax-1ifrearispointingtothelastpositioninthearray

Display“queuefull”

Exit

2.IfFront=Rear=-1//Qisempty

a.front=front+1

b.Gotostep3

3.Rear=Rear+1

//dataisinsertedattherear

4.Queue[rear]=newdata

Algorithmfordeletingdatafromalinearqueue（asanarray）:

1.iffront=-1

//thereisnodatainthequeue

Display“queueempty”

Exit

2.iffront=rear

front=rear=-1

3.deletethevalueatqueue[front]

4.front=front+1

Note:

Alwaysremember:

InaQueue

ForeveryInsert:

Rear=Rear+1

AftereveryDelete:

Front=Front+1

Thevaluesare‘neverdecremented’inthecaseofaninsertoradeleteinaqueue

Implementationofaqueueasacircularqueue（CQ）:

FortheemptyCQ:

Front=-1

Rear=-1

FortheCQwithonlyonedata:

Front=Rear

FortheCQtobefull:

Condition1:

Front=0andRear=max-1

OR

Condition2:

Front=rear+1

AlgorithmforinsertingdatainaQueue（asacircularqueue/array）:

1.If（Front=0ANDRear=Max-1）ORfront=rear+1

display“queuefull”

exit

2.iffront=-1//Qisempty

front=0

rear=0

gotostep5

//insertthe1stdataintheCQ

3.ifrear=max-1

setrear=0

gotostep5

4.rear=rear+1

5.Queue[rear]=newdata

AlgorithmfordeletingdatainaQueue（asacircularqueue/array）:

1.IfFront=-1//nodataintheQ

display“queueempty”

exit

2.Iffront=rear

//thereisonlyonedataintheCQueue

front=-1

rear=-1

exit

3.ifFront=max-1

//deletingthedatafromthelastindexpositionofthecirculararray

front=0

exit

4.front=front+1

ImplementationofaQUEUEasalinkedlist:

Ifthequeueisempty:

front=rear=null

Ifthereisonlyonenode:

front=rear

QueueOverflow:

ThisconditioncannotariseinaLinkedListasthereisnosizelimit.

Exception:

Memoryrunsout–thereisnoenoughspaceinthememorytostorethedata

QueueUnderflow:

toavoidthissituationalwayscheckfor‘Front=Null’（whichmeansthelistisempty）

AlgorithmforinsertinganewdatainaqueuewhichisaLinkedlist/LinkedQueue:

Thenewnodewillalwaysbeinsertedintheendofthelinkedlistasalastnode!

1.createnewnode

2.newnode.data=data

3.newnode.next=null

4.iffront=null//ifthequeueisempty

front=newnode

rear=newnode

5.rear.next=newnode

6.rear=newnode

AlgorithmfordeletingadatafromthequeueasaLinkedlist/LinkedQueue:

alwaysbeginsfromthe1stnodeofthelist

1.iffront=null//thequeueisempty

display“queueempty”

exit

2.iffront=rear//thereisonlyonenode

front=rear=null

exit

3.current=front

4.front=current.next

5.releasecurrent