Friday, February 27, 2009

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