《数据结构的算法在C++中的应用》（英文版）Chapter 6 Queue

Chapter 6 Q ueue

Chapter 6 Queue

6.1 Definition Definition a queue is a linear list in which additions and deletions take place at different ends It is also called a first-in-first-out list The end at which new elements are added is called the rear The end from which old elements are deleted is called the front

6.1 Definition • Definition: A queue is a linear list in which additions and deletions take place at different ends. It is also called a first-in-first-out list. The end at which new elements are added is called the rear. The end from which old elements are deleted is called the front

6.1 Definition Sample queues front rear front rear front rear AB C B C B C D Delete a Add d

6.1 Definition • Sample queues front rear front rear front rear A B C B C B C D Delete A Add D

6.2 ADT AbstractData Type Queue Instances ordered list of elements one end is called the front the other is the rear operations Create(: Create an empty queue IsEmptyo: Return true if queue is empty, return false otherwise IsFullo return true if queue is full, return false otherwise

6.2 ADT AbstractDataType Queue{ instances ordered list of elements;one end is called the front; the other is the rear; operations Create():Create an empty queue; IsEmpty():Return true if queue is empty,return false otherwise; IsFull():return true if queue is full, return false otherwise;

6.2 ADT Firsto: return first element of the queue Lasto return last element of the queue Add (): add element x to the queue Delete(x): delete front element from the queue and put it in x;

6.2 ADT First():return first element of the queue; Last():return last element of the queue; Add(x):add element x to the queue; Delete(x):delete front element from the queue and put it in x; }

6.3formula-based representation front rear Q Maxsize -1 ueue ABC 0j[1][2] the queue size =rear+ an empty queue has rear--1

6.3formula-based representation the queue size =rear+1; an empty queue has rear=-1 A B C …… Queue: front rear Maxsize-1 [0] [1] [2] [n-1]

6.3formula-based representation To add an element rear-rear+l; queuerear=x; To delete an element: two methods 1)frontfront+1; O( 2)shift the queue one position left. O(n)

6.3formula-based representation To add an element: rear=rear+1; queue[rear]=x; To delete an element: two methods: 1) front=front+1; O(1) 2) shift the queue one position left. O(n)

6.3formula-based representation Figure 6.3 front rear front rear front rear ABC B BIC D

6.3formula-based representation Figure 6.3 front rear front rear front rear A B C … B C … B C D …

6.3formula-based representation Figure 6.4 front rear ABC p Free space

6.3formula-based representation Figure 6.4 … A B C D E Front rear Free space

6.3formula-based representation as the figure6. 4 shows each deletion causes front to move right by 1 So there will be times when rearmaxsize-1 and front>o At these times the queue is not full, there is space at the left end of it

6.3formula-based representation As the figure6.4 shows ,each deletion causes front to move right by 1 So,there will be times when rear=maxsize-1 and front>0 At these times the queue is not full,there is space at the left end of it