Queues
Queues !?
Here's our Second data structure , which is called a queue . The most
important property of a queue , which makes it different from a
stack is that it's is "FIFO : First input
first output " , it's just like real life queues.
You can think of a queue as a special kind of lists , where items are
added from one end , and removed from the other end ; while the elements
order is preserved.
We've two types of queues :
(1)Linear queues : in case elements are read from the front , we
need to shift ... time delay.
(2)Circular queues : This's the one we're going to implement in
this course.
Notes.
There are two methods of implementing the queues :
_Approach one :
We here will initialize " Front = 0 " , and
" Rear = -1 " ; and the test for empty queue " Front = =
NextPosition(Rear) ? " . But `the main problem here is that this
condition also holds for a full queue .
Increase rear then put the value.
Front points to the first element.
Rear points to the last element.
_Approach two :
This is a better one , as we'll let " Front
= = Rear ?" indicate an empty queue .
Front points to a never used item , and real data starts from the next
position to the front .
Front must always points to an empty cell , and this means that we'll
lose a place in memory ( never used cell ) but on the other hand it's make
it easier to detect an empty queue .
Syntax.
< queue.h >
#include < iostream.h >
#include < stdlib.h >
#include < assert.h >
/* To use assertion in the programme */
const int MaxQueueSize=100 ;
typedef int QueueElemType ;
/* Define a new variable type called QueueElemType */
class Queue {
Public :
Queue( ) ;
void
EnQueue(QueueElemType) ;
Applications
(1)Operating systems and computer networks ... programmes or
messages are ordered in a queue to be
executed one by one.
(2)Simmulations of situations.
(
Prev
) (
Table of contents
) (
Next
)
Copyright (C) 2000 Tarek Amr Abdullah. All rights reserved. My Home Page