Algorithms‎ > ‎Data Structures‎ > ‎

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