Algorithms & Data Structures - Queue

Definition

• Queue is an ordered collection of items.
• These items may be deleted at one end (called the HEAD of the queue) and inserted at other end (called the TAIL of the queue).
• Example, to withdraw money at ATM
• Also known as FIFO – first in first out

Array and linked list implementation



Operations of Queue

• Dequeue
• Enqueue
• QueueEmpty
• QueueFull

Enqueue

• Enqueue is the shortened version of "entering a queue".
• It refers to a situation where a new item is inserted to the queue.
• After a new insertion is made, the new item becomes the tail of the queue.

Dequeue

• Dequeue is a shortened version of "deleting from a queue".
• This is a situation where the data element at the head of the queue will be deleted.

Array implementation

• Using array to implement the queue
• Will create a problem when the queue is full – memory space are fixed.

Problem solution

• Create a circular queue. (using linked list)
• Circular queue wraps around to the beginning whenever the Head or the Tail reaches the end of the queue.

Linked list implementation
* Enqueue




Enqueue- Implementation
void Enqueue(QUEUENODEPTR *tailPtr, QUEUENODEPTR *headPtr, char Value)
{
QUEUENODEPTR newPtr;
newPtr = malloc(sizeof(LISTNODE)); //Create a new node
if (newPtr != NULL)
{
newPtr->data = Value;
newPtr->nextPtr = NULL;
(*tailPtr)->nextPtr = newPtr;
(*tailPtr) = (*tailPtr)->nextPtr;
if (*headPtr == NULL)
*headPtr = *tailPtr;
}


Dequeue - Implementation
char Dequeue(QUEUENODEPTR *headPtr)
{
char value;
QUEUENODEPTR tempPtr;
if (*headPtr != NULL)
{
tempPtr = *headPtr;
(*headPtr) = (*headPtr)->nextPtr;
value = tempPtr->data;
free(tempPtr);
return value;
{
else
printf(“Queue is empty”);
}


Application of queue

• Scheduling system
  • Advantages
• Support print spooling
• Information packet