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