【精品数据结构】Queue.pptVIP

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 Sample queues front rear front rear front rear A B C B C B C D 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 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 the queue size =rear+1; an empty queue has rear=-1 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 A B C … B C … B C D … 6.3formula-based representation Figure 6.4 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 front0 At these times the queue is not full,there is space at the left end of it 6.3 Formula-based representation Another way is to use a circular array to represent a queue 6.3 Formula-based representation deletion 6.3 Formula-base