Queue
Queue
- A queue is an ordered list in which all insertions take place at one end and all deletions take place at the opposite end
- A queue Q = (a0; a1; : : : ; an-1)
- a0 is the front element
- an-1 is the rear element
- ai+1 is behind ai
- Also refered as First-In-First-Out(FIFO) list
Queue Implementation
Queue CreateQ(maxQueueSize) ::=
#define MAX_QUEUE_SIZE 100
typedef struct {
int key;
/* other fields */
} element;
element queue[MAX_QUEUE_SIZE];
int rear = -1;
int front = -1;
Boolean IsEmptyQ(queue) ::= front == rear
Boolean IsFullQ(queue) ::= rear == (MAX_QUEUE_SIZE-1)
void addq(int *rear, element item)
{
if ( *rear == MAX_QUEUE_SIZE - 1 )
{
queue_full();
returnn;
}
queue[++*rear] = item;
}
element deleteq(int *front, int rear)
{
if ( *front == rear )
return queue_empty();
return queue[++*front];
}
Circular Queue
- front and rear are initialized to 0 rather than -1
- The front index always points one position counterclockwise from the first element in the queue
- The rear index ponts to the current end of the queue
- Queue is empty if front=rear
- Addition to index are done modulo MAX QUEUE SIZE
Circular Queue Implementations
int rear = 0;
int front = 0;
Boolean IsEmptyCQ(queue) ::= front == rear
Boolean IsFullCQ(queue) ::= rear = (rear + 1) % MAX_QUEUE_SIZE; front == rear
void addcq(int front, int *rear, element item)
{
*rear = (*rear + 1) % MAX_QUEUE_SIZE;
if (front == *rear)
{
queue_full(rear);
return;
}
queue[*rear] = item;
}
element deletecq(int *front, int rear)
{
element item;
if ( *front == rear )
return queue_empty();
*front = (*front + 1) % MAX_QUEUE_SIZE;
return queue[*front];
}