QUEUE

UPASANA TALUKDAR
CSE
QUEUE

• A queue is an ordered list in which insertions are done at one end (rear) and deletions
are done at other end (front). The first element to be inserted is the first one to be
deleted. Hence, it is called First in First out (FIFO) or Last in Last out (LILO) list.
• Example
• line at a reservation counter

• Operations:
• Enqueue: When an element is inserted in a queue, the concept is called EnQueue.
• DeQueue: When an element is removed from the queue, the concept is called DeQueue.
ARRAY REPRESENTATION OF QUEUE (INSERTION)

• [QUEUE already filled?]

If REAR=N, then Print:OVERFLOW, and Return
• If FRONT=NULL, then: [Queue initially empty]
Set FRONT=1 and REAR=1
Else : REAR:= REAR+1
• Set QUEUE[REAR]:=ITEM
• Return
ARRAY REPRESENTATION OF QUEUE (DELETION)

• If FRONT:=NULL, then Print:UNDERFLOW, and Return

• Set ITEM:=QUEUE[FRONT]
• [Find new value of FRONT]
If FRONT:=REAR, then [Queue has only one element to start]
Set FRONT:=NULL and REAR:=NULL
Else : FRONT:= FRONT+1
• Return
LINKED REPRESENTATION OF QUEUE (INSERTION)

• [OVERFLOW?], Write:OVERFLOW and Exit.

[Remove first node from AVAIL list]
• Set NEW:=AVAIL and AVAIL:=LINK[AVAIL]
• Set INFO[NEW]:=ITEM and LINK[NEW]=NULL [Copies new data into new node]
• If (FRONT=NULL) then FRONT=REAR=NEW [If Q is empty then ITEM is the first element
in the queue)
Else set LINK[REAR]:=NEW and REAR=NEW
• EXIT
LINKED REPRESENTATION OF QUEUE (DELETION)

• [UNDERFLOW?], Write:UNDERFLOW and Exit. (FRONT=NULL)

• Set TEMP:=FRONT
• Set ITEM:=INFO[TEMP]
• FRONT=LINK[TEMP]
• Set LINK[TEMP]:=AVAIL and AVAIL:=TEMP [Return deleted node to AVAIL list]
• EXIT
ARRAY REPRESENTATION

void insert()
{
int add_item;
if (rear == MAX - 1)
printf("Queue Overflow \n");
else
{
if (front == - 1)
/*If queue is initially empty */
front = 0;
printf("Insert the element in queue : ");
scanf("%d", &add_item);
rear = rear + 1;
queue_array[rear] = add_item;
}}
ARRAY REPRESENTATION

void delete()
{
if (front == - 1)
{
printf("Queue Underflow \n");
return ;
}
else
{
printf("Element deleted from queue is : %d\n", queue_array[front]);
front = front + 1;
}
}
 LINKED REPRESENTATION

void enqueue(int value)

{ struct node *ptr;
ptr = (struct node *)malloc(sizeof(struct node));
ptr->data = value;
ptr->next = NULL;
if ((front == NULL) && (rear == NULL))
{ front = rear = ptr; }
else { rear->next = ptr; rear = ptr; }
printf("Node is Inserted\n\n"); }
}

LINKED REPRESENTATION

int dequeue()
{ if (front == NULL)
{ printf("\nUnderflow\n"); return -1; }
else
{ struct node *temp = front;
int temp_data = front->data;
front = front->next; free(temp);
return temp_data; } }
DEQUE

• A list in which elements can be added or removed at either end but not in the middle.
• The term deque is a contraction of the name double-ended queue.
• Two variations:
• Input restricted: allows insertion only at one end and deletion at both ends
• Output restricted: allows insertion at both the ends and insertion only at one end.
 ARRAY REPRESENTATION

void insert_right()
{ int added_item;
if((left == 0 && right == MAX-1))
{ printf("Queue Overflow\n"); return;}
if (left == -1)
{ left = 0; right = 0;}
else if(right == MAX-1)
right = 0;
else right = right+1;
printf("Input the element for adding in queue : ");
scanf("%d", &added_item);
deque_arr[right] = added_item ; }
ARRAY REPRESENTATION

void insert_left()
{ int added_item;
if((left == 0 && right == MAX-1))
{ printf("Queue Overflow \n"); return; }
if (left == -1)
{ left = 0; right = 0; }
else if(left== 0)
left=MAX-1;
else left=left-1;
printf("Input the element for adding in queue : ");
scanf("%d", &added_item);
deque_arr[left] = added_item ; }
ARRAY REPRESENTATION

void delete_left()
void delete_right()
{ if (left == -1) {if (left == -1)
{ printf("Queue Underflow\n"); return ; } {printf("Queue Underflow\n"); return ; }
printf("Element deleted from queue is : %d\n",deque_arr[right]);
printf("Element deleted from queue is : if(left == right)
%d\n",deque_arr[left]); { left = -1; right=-1; }
if(left == right) /*Queue has only one else if(right == 0) right=MAX-1;
element */ else right=right-1; }

{ left = -1; right=-1; }

else if(left == MAX-1) left = 0;
else left = left+1; }
CIRCULAR QUEUE

• Limitations of Linear Queue

• A circular queue is a linear data structure that follows FIFO principle. In circular queue,
the last node is connected back to the first node to make a circle.
 CIRCULAR ARRAY

• An array is called circular if we consider the first element as next of the last element. Circular
arrays are used to implement queue.
An example problem :
Suppose n people are sitting at a circular table with names A, B, C, D, … Given a name, we need to
print all n people (in order) starting from the given name.

For example, consider 6 people A B C D E F and given name as ‘D’.

People sitting in a circular manner starting from D are D E F A B C.
A simple solution is to create an auxiliary array of size 2*n and store it in another array.
A B C D E FA B C D E F
Now for any given index, we simply print n elements starting from it. For example, we prin
A B C D E FA B C D E F
CIRCULAR ARRAY

• An efficient solution is to deal with circular arrays using the same array. If a careful
observation is run through the array, then after n-th index, the next index always starts
from 0 so using the mod operator, we can easily access the elements of the circular list,
if we use (i)%n and run the loop from i-th index to n+i-th index. and apply mod we can
do the traversal in a circular array within the given array without using any extra space
CIRCULAR QUEUE (INSERTION)

procedure INSERT_CIRCQ(IRC_Q,FRONT,REAR,n, ITEM)

Check for overflow condition;
REAR=(REAR+1) mod n;
CIRCQ[REAR]=ITEM;
end
CIRCULAR QUEUE (DELETION)

procedure DELETE_CIRCQ(CIRC_Q,FRONT,REAR,n, ITEM)

FRONT=(FRONT+1) mod n;
ITEM=CIRCQ[FRONT];
end
ARRAY REPRESENTATION

void enqueue(int item)

{ if(isFull())
{ printf("Queue Overflow\n");
exit(1); }
if(front == -1)
{ front=0; }
rear=(rear+1)%N; // rear is incremented
cq[rear]=item;
}
}

ARRAY REPRESENTATION

int dequeue()
{
int deleted_item;
if(isEmpty())
{ printf("Queue Underflow\n");
exit(1);
}
deleted_item = cq[front];
if(front==rear)
{ front=-1; rear=-1; }
else {
front = (front + 1)%N;
}
return deleted_item
}
EXAMPLE

• Consider the following queue of characters, where QUEUE is a circular array which is
allocated six memory cells:
FRONT=2, REAR=4. QUEUE:____,A,C,D, __,______. Describe the QUEUE as the
following operations take place:
a. F is added to QUEUE
b. Two letters are deleted
c. K, L, M are added to QUEUE.
d. Two letters are deleted.
e. R is added
PROBLEMS

• A programming language provides two functions ALLOCATE (X) and FREE (X) for the
maintenance of linked list structures. ALLOCATE(X) allots a node with address X for use
in the linked list structure and FREE(X) frees the node with address X used in the
application to the AVAIL list. Assuming the AVAIL list to be maintained as a linked stack,
write procedures to implement the functions ALLOCATE and FREE.
PROBLEMS

• Translate by inspection and hand, each infix expression to postfix expression

• (A-B)*(D/E)
• (A+B^D)/E-F*(G+H/K)
PROBLEMS

• Evaluate the following

12,7,3,-,/,2,1,5,+,*,+
PROBLEMS

• Consider the following queue of characters, where QUEUE is a circular array which is allocated six
memory cells:
FRONT=2, REAR=4. QUEUE:____,A,C,D, __,______. After the following operations take place, let
the QUEUE is described as QUEUE: L,M,R, __,______,K.
F is added to QUEUE, Two letters are deleted, K, L, M are added to QUEUE, Two letters are deleted, R is
added
Describe the QUEUE as the following operations take place:
a. Two letters are deleted
b. S is added
c. Two letters are deleted
d. One letter is deleted
e. One letter is deleted