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
Delete A Add 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
A B C ……
Queue:
front rear Maxsize-1
[0] [1] [2] [n-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
… 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 rear=maxsize-1
and front>0
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
C
B
A
front
rear
D
Addtion
C
B
A
front
rear
6.3 Formula-based representation
deletion
deletion
C
B
A
front
D
rear
C
B
front
rear
D
A
6.3 Formula-based representation
In a circular queue:
front points to one position before the first
element in the queue
A queue is empty iff front= =rear
The initial condition front=rear=0 defines an
initially empty queue
6.3 Formula-based representation
How can we distinguish between an empty
queue and a full queue?
? The max number of elements in a queue
actually is maxsize
? A queue is full iff (rear+1)%maxsize= =front
? A queue if empty iff front= =rear
6.3 Formula-based representation
Formula-based class queue(program 6.1)
template<class T>
class Queue{
//FIFO objects
public:
Queue(int MaxQueueSize=10);
~Queue(){delete[]queue;}
bool IsEmpty()const{return front==rear;}
bool IsFull()const{return
(((rear+1)%MaxSize==front)?1:0);}
6.3 Formula-based representation
T First()const;//return front element
T Last()const;//return last element
Queue<T>&Add(const T&x);
Queue<T>&Delete(T& x);
Private:
int front; //one counterclockwise from first
int rear; // last element
int maxsize;//size of array queue
T* queue; //element array;
};
6.3 Formula-based representation
1)constructor(program 6.2)
template<class T>
Queue<T>::Queue(int MaxQueueSize)
{//create an empty queue whose capacity is MaxQueueSize
MaxSize=MaxQueueSize+1;
queue=new T[MaxSize];
front=rear=0;
}
6.3 Formula-based representation
2)Add(x) (program 6.3)
Template<class T>
Queue<T>& Queue<T>::Add(const T&x)
{//Add x to the rear of the queue.Throw NoMem
exception if the queue is full
if(IsFull())throw NoMem();
rear=(rear+1)%MaxSize;
queue[rear]=x;
return *this;
}
6.3 Formula-based representation
3)Delete(x) (program 6.3)
Template<class T>
Queue<T>& Queue<T>::Delete(T& x)
{//delete first element and put it in x,Throw
OutOfBounds exception if queue is empty
if(IsEmpty())throw OutOfBounds();
front=(front+1)%MaxSize;
x=queue[front];
return *this;
}
6.4 Linked Representation
Linked queues
^
data link
front rear
…
…
a1 a2 an
6.4 Linked Representation
Class definition for a linked queue(program 6.4)
template<class T>
class LinkedQueue{
//FIFO objects
public:
LinkedQueue(){front=rear=0;}
~LinkedQueue();
6.4 Linked Representation
bool IsEmpty()const{return ((front)?false:true);}
bool IsFull()const;
T First()const;
T Last()const;
LinkedQueue<T>&Add(const T& x);
LinkedQueue<T>& Delete(T& x);
privarte:
Node<T>*front;
Node<T>*rear;
};
6.4 Linked Representation
1)destructor
template<class T>
LinkedQueue<T>::~LinkedQueue()
{//Queue destructor, Delete all nodes
Node<T>*next;
while(front){
next=front?link;
delete front;
front=next;
}
}
6.4 Linked Representation
2)Add(x) (program 6.6)
template<class T>
LinkedQueue<T>& LinkedQueue<T>::Add(const T&x)
{//Add x to rear of the queue.Do not catch possible
NoMem exception thrown by new.
//create node for new element
Node<T>*p=new Node<T>;
p?data=x;
p?link=0;
6.4 Linked Representation
//add new node to rear of queue
if(front) rear?link=p;
else front=p;
rear=p;
return *this;
}
6.4 Linked Representation
3)Delete(x) (program 6.6)
template<class T>
LinkedQueue<T>& LinkedQueue<T>::Delete(T& x)
{//Delete first element and put it in x.Throw
OutOfBounds exception if the queue is empty
if(IsEmpty())throw OutOfBounds();
//save element in first node
x=front?data;
6.4 Linked Representation
//delete first node
Node<T>* p=front;
front=front?link;
delete p;
return *this;
}
6.5 Application
1) Print the coefficients of the binomial expansion
(a+b)i
a
b
a
b
3 2
2 1
1 1 2
2 1 2 b
2 3 4 8
5 6 7 8
6 7 8
a