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; }