QUEUE

■ 1. A queue can be defined as an ordered list which enables insert operations to be

performed at one end called REAR and delete operations to be performed at
another end called FRONT.

■ 2. Queue is referred to be as First In First Out list.

■ 3. For example, people waiting in line for a rail ticket form a queue.
Applications of Queue
Due to the fact that queue performs actions on first in first out basis which is quite fair
for the ordering of actions.
There are various applications of queues discussed as below.
■ Queues are widely used as waiting lists for a single shared resource like printer,
disk, CPU.
■ Queues are used in asynchronous transfer of data (where data is not being
transferred at the same rate between two processes) for eg. pipes, file IO, sockets.
■ Queues are used as buffers in most of the applications like MP3 media player, CD
player, etc.
■ Queue are used to maintain the play list in media players in order to add and remove
the songs from the play-list.
■ Queues are used in operating systems for handling interrupts.
 Complexity

Space
Data
Time Complexity Complex
Structure
ity
Average Worst Worst

Access Search Insertion Deletion Access Search Insertion Deletion

Queue θ(n) θ(n) θ(1) θ(1) O(n) O(n) O(1) O(1) O(n)
What is the Queue?
■ A queue in the data structure can be considered similar to the queue in the real-
world.
■ A queue is a data structure in which whatever comes first will go out first.
■ It follows the FIFO (First-In-First-Out) policy.
■ In Queue, the insertion is done from one end known as the rear end or the tail of the
queue, whereas the deletion is done from another end known as the front end or the
head of the queue.
■ In other words, it can be defined as a list or a collection with a constraint that the
insertion can be performed at one end called as the rear end or tail of the queue
and deletion is performed on another end called as the front end or the head of the
queue.
Operations on Queue
■ Enqueue: The enqueue operation is used to insert the element at the rear end of the
queue. It returns void.
■ Dequeue: The dequeue operation performs the deletion from the front-end of the
queue. It also returns the element which has been removed from the front-end. It
returns an integer value. The dequeue operation can also be designed to void.
■ Peek: This is the third operation that returns the element, which is pointed by the
front pointer in the queue but does not delete it.
■ Queue overflow (isfull): When the Queue is completely full, then it shows the
overflow condition.
■ Queue underflow (isempty): When the Queue is empty, i.e., no elements are in the
Queue then it throws the underflow condition.
Types of Queue

Linear Queue
■ In Linear Queue, an insertion takes place from one end while the deletion occurs
from another end.
■ The end at which the insertion takes place is known as the rear end, and the end at
which the deletion takes place is known as front end.
■ It strictly follows the FIFO rule.
■ The linear Queue can be represented, as shown in the below figure:
■ The above figure shows that the elements are inserted from the rear end, and if we
insert more elements in a Queue, then the rear value gets incremented on every
insertion.
■ If we want to show the deletion, then it can be represented as:
■ In the above figure, we can observe that the front pointer points to the next element,
and the element which was previously pointed by the front pointer was deleted.
■ The major drawback of using a linear Queue is that insertion is done only from the
rear end.
■ If the first three elements are deleted from the Queue, we cannot insert more
elements even though the space is available in a Linear Queue.
■ In this case, the linear Queue shows the overflow condition as the rear is pointing to
the last element of the Queue.
Circular Queue
■ In Circular Queue, all the nodes are
represented as circular.
■ It is similar to the linear Queue except that the
last element of the queue is connected to the
first element.
■ It is also known as Ring Buffer as all the ends
are connected to another end.
■ The drawback that occurs in a linear queue is
overcome by using the circular queue.
■ If the empty space is available in a circular
queue, the new element can be added in an
empty space by simply incrementing the value
of rear.
Priority Queue
■ A priority queue is another special type of Queue data structure in which each
element has some priority associated with it.
■ Based on the priority of the element, the elements are arranged in a priority queue.
■ If the elements occur with the same priority, then they are served according to the
FIFO principle.
■ In priority Queue, the insertion takes place based on the arrival while the deletion
occurs based on the priority.
■ Deque
■ Both the Linear Queue and Deque are different as the linear queue follows the FIFO
principle whereas, deque does not follow the FIFO principle.
■ In Deque, the insertion and deletion can occur from both ends.
Implementation of Queue

There are two ways of implementing the Queue:

■ Sequential allocation: The sequential allocation in a Queue can be implemented
using an array.
■ Linked list allocation: The linked list allocation in a Queue can be implemented using
a linked list.
 ARRAY
REPRESENTATION OF
QUEUE
■ We can easily represent queue by using linear arrays.
■ There are two variables i.e. front and rear, that are implemented in the case of every
queue.
■ Front and rear variables point to the position from where insertions and deletions
are performed in a queue.
■ Initially, the value of front and queue is -1 which represents an empty queue.
■ Array representation of a queue containing 5 elements along with the respective
values of front and rear, is shown in the following figure.
■ The above figure shows the queue of characters forming the English word "HELLO".
Since,
■ No deletion is performed in the queue till now, therefore the value of front remains -1 .
■ However, the value of rear increases by one every time an insertion is performed in the
queue.
■ After inserting an element into the queue shown in the above figure, the queue will look
something like following.
■ The value of rear will become 5 while the value of front remains same.
■ After deleting an element, the value of front will increase from -1 to 0. however, the
queue will look something like following.
Algorithm to insert any element in a
queue
■ Check if the queue is already full by comparing rear to max - 1. if so, then return an
overflow error.
■ If the item is to be inserted as the first element in the list, in that case set the value
of front and rear to 0 and insert the element at the rear end.
■ Otherwise keep increasing the value of rear and insert each element one by one
having rear as the index.
Step 1: IF REAR = MAX - 1
Write OVERFLOW
Go to step
[END OF IF]

Step 2: IF FRONT = -1 and REAR = -1

SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]

Step 3: Set QUEUE[REAR] = NUM

Step 4: EXIT
Algorithm to delete an element from the
queue
■ If, the value of front is -1 or value of front is greater than rear , write an underflow
message and exit.
■ Otherwise, keep increasing the value of front and return the item stored at the front
end of the queue at each time.
Step 1: IF FRONT = -1 or FRONT > REAR
Write UNDERFLOW

ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]

Step 2: EXIT
#include<stdio.h> void main ()
#include<stdlib.h> {
#define maxsize 5 int choice;
void insert(); while(choice != 4)
void delete(); {
void display(); printf("\n*************************Main Menu***
int front = -1, rear = -1; **************************\n");

int queue[maxsize]; printf("\n=====================================

============================\n");
printf("\[Link] an element\[Link] an element\[Link]
lay the queue\[Link]\n");

printf("\nEnter your choice ?");

scanf("%d",&choice);
switch(choice)
{
case 4:
case 1:
exit(0);
insert();
break;
break;
default:
case 2:
delete(); printf("\nEnter valid choice??\n");

break; }

case 3: }

display(); }
break;
void insert()
if(front == -1 && rear == -1)
{
{
int item;
front = 0;
printf("\nEnter the element\n");
scanf("\n%d",&item); rear = 0;
}
if(rear == maxsize-1)
else
{
printf("\nOVERFLOW\n"); {
return; rear = rear+1;

} }
queue[rear] = item;
printf("\nValue inserted ");

}
void delete() if(front == rear)
{ {
int item;
front = -1;
if (front == -1 || front > rear)
rear = -1 ;
{
}
printf("\nUNDERFLOW\n");
else
return;
{
}
front = front + 1;
else
}
{
printf("\nvalue deleted ");
item = queue[front];
}
}
void display()
{
int i;
if(rear == -1)
{
printf("\nEmpty queue\n");
}
else
{ printf("\nprinting values .....\n");
for(i=front;i<=rear;i++)
{
printf("\n%d\n",queue[i]);
}
}
}
Drawback of array implementation
■ Although, the technique of creating a queue is easy, but there are some drawbacks
of using this technique to implement a queue.
Memory wastage :
■ The space of the array, which is used to store queue elements, can never be reused
to store the elements of that queue because the elements can only be inserted at
front end and the value of front might be so high so that, all the space before that,
can never be filled.
■ The above figure shows how the memory space is wasted in the array representation
of queue.
■ In the above figure, a queue of size 10 having 3 elements, is shown.
■ The value of the front variable is 5, therefore, we can not reinsert the values in the
place of already deleted element before the position of front.
■ That much space of the array is wasted and can not be used in the future (for this
queue).
Deciding the array size
■ On of the most common problem with array implementation is the size of the array
which requires to be declared in advance.
■ Due to the fact that, the queue can be extended at runtime depending upon the
problem, the extension in the array size is a time taking process and almost
impossible to be performed at runtime since a lot of reallocations take place.
■ Due to this reason, we can declare the array large enough so that we can store
queue elements as enough as possible but the main problem with this declaration is
that, most of the array slots (nearly half) can never be reused. It will again lead to
memory wastage.
 LINKED LIST
IMPLEMENTATION OF
QUEUE
■ Due to the drawbacks, the array implementation can not be used for the large scale
applications where the queues are implemented. One of the alternative of array
implementation is linked list implementation of queue.

■ The storage requirement of linked representation of a queue with n elements is o(n)

while the time requirement for operations is o(1).

■ In a linked queue, each node of the queue consists of two parts i.e. data part and
the link part. Each element of the queue points to its immediate next element in the
memory.
■ In the linked queue, there are two pointers maintained in the memory i.e. front
pointer and rear pointer.

■ The front pointer contains the address of the starting element of the queue while
the rear pointer contains the address of the last element of the queue.

■ Insertion and deletions are performed at rear and front end respectively. If front and
rear both are NULL, it indicates that the queue is empty.

■ The linked representation of queue is shown in the following figure.

Operation on Linked Queue

■ There are two basic operations which can be implemented on the linked queues.
The operations are Insertion and Deletion.
Insert operation

■ The insert operation append the queue by adding an element to the end of the
queue.
■ The new element will be the last element of the queue.
■ Firstly, allocate the memory for the new node ptr by using the following statement.
■ Ptr = (struct node *) malloc (sizeof(struct node));
■ There can be the two scenario of inserting this new node ptr into the linked queue.
■ In the first scenario, we insert element into an empty queue.
■ In this case, the condition front = NULL becomes true.
■ Now, the new element will be added as the only element of the queue and the next
pointer of front and rear pointer both, will point to NULL.
ptr -> data = item;
if(front == NULL)
{
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
■ In the second case, the queue contains more than one element.
■ The condition front = NULL becomes false.
■ In this scenario, we need to update the end pointer rear so that the next pointer of
rear will point to the new node ptr.
■ Since, this is a linked queue, hence we also need to make the rear pointer point to
the newly added node ptr.
■ We also need to make the next pointer of rear point to NULL.
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
■ In this way, the element is inserted into the queue.
Deletion

■ Deletion operation removes the element that is first inserted among all the queue
elements.
■ Firstly, we need to check either the list is empty or not.
■ The condition front == NULL becomes true if the list is empty, in this case , we
simply write underflow on the console and make exit.
■ Otherwise, we will delete the element that is pointed by the pointer front.
■ For this purpose, copy the node pointed by the front pointer into the pointer ptr.
■ Now, shift the front pointer, point to its next node and free the node pointed by the
node ptr.
■ This is done by using the following statements.
ptr = front;
front = front -> next;
free(ptr);
#include<stdio.h> void main ()
#include<stdlib.h> {
struct node int choice;
{ while(choice != 4)

int data; {

struct node *next; printf("\n*************************Main Menu********

*********************\n");
};
printf("\n=========================================
struct node *front;
========================\n");
struct node *rear;
printf("\[Link] an element\[Link] an element\[Link] the
void insert();
queue\[Link]\n");
void delete(); printf("\nEnter your choice ?");
void display(); scanf("%d",& choice);
switch(choice)
{
case 1:
case 3:
insert(); display();
break; break;
case 2: case 4:
delete(); exit(0);
break; break;
default:

printf("\nEnter valid choice??\n");

}
}
}
void insert()
{
struct node *ptr; if(front == NULL)
int item; {
front = ptr;
rear = ptr;
ptr = (struct node *) malloc (sizeof(struct node)); front -> next = NULL;
if(ptr == NULL) rear -> next = NULL;
}
{ else
printf("\nOVERFLOW\n"); {
return; rear -> next = ptr;
rear = ptr;
} rear->next = NULL;
else }
{ }
}
printf("\nEnter value?\n");
scanf("%d",&item);
ptr -> data = item;
void delete ()
{
struct node *ptr;
if(front == NULL)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
ptr = front;
front = front -> next;
free(ptr);
}
}
void display()
{ else
struct node *ptr; {
ptr = front; printf("\nprinting values .....\n");
if(front == NULL) while(ptr != NULL)

{ {

printf("\nEmpty queue\n"); printf("\n%d\n",ptr -> data);

} ptr = ptr -> next;

}
}
}
 POLISH
NOTATION
 Infix Expressions
■ Used in arithmetic
■ Operator is placed between the operands
■ Parentheses are used to denote the priority of the operation
■ Examples
– a+b
– (a + b) * (a - b)
– (a ^ b * (c + (d * e) - f ) ) / g

113
Infix Notation

■ To add A, B, we write
A+B
■ To multiply A, B, we write
A*B
■ The operators ('+' and '*') go in between the operands ('A' and 'B')
■ This is "Infix" notation.
 Prefix Expressions
■ Mathematical Notation
■ Operator is placed before all its operands
■ No need of parentheses
■ Easy to parse as compared to infix
■ Examples
Infix Expression Prefix Expressions
a+b +ab
(a + b) * (a - b) *+ab-ab
(a ^ b * (c + (d * e) - f ) ) / g /*^ab-+*decfg
115
Prefix Notation

■ Instead of saying "A plus B", we could say "add A,B " and write
+ AB
■ "Multiply A,B" would be written
* AB
■ This is Prefix notation.
 Postfix Expressions
■ Mathematical Notation
■ Operator is placed after all its operands
■ No need of parentheses
■ Easy to parse as compared to infix
■ Examples
Infix Expression Postfix Expressions
a+b ab+
(a + b) * (a - b) ab+ab-*
(a ^ b * (b + (d * e) - f ) ) / g ab^cde*+f-*g/
117
Postfix Notation

■ Another alternative is to put the operators after the operands as in

AB +
and
AB *
■ This is Postfix notation.
■ The terms infix, prefix, and postfix tell us whether the operators go between, before,
or after the operands.

Pre A In B Post
Parentheses

■ Evaluate 2+3*5.
■ + First:
(2+3)*5 = 5*5 = 25
■ * First:
2+(3*5) = 2+15 = 17
■ Infix notation requires Parentheses.
What about Prefix Notation?

■ +2*35=
=+2*35
= + 2 15 = 17
■ *+235=
=*+235
= * 5 5 = 25
■ No parentheses needed!
Postfix Notation

■ 235*+=
=235*+
= 2 15 + = 17
■ 23+5*=
=23+5*
= 5 5 * = 25
■ No parentheses needed here either!
 TRANSFORMING
INFIX EXPRESSIONS
INTO POSTFIX
EXPRESSIONS
■ The infix and postfix expressions can have the following operators: '+', '-', '%','*', '/'
and alphabets from a to z.
■ The precedence of the operators (+, -) is lesser than the precedence of operators (*,
/, %).
■ Parenthesis has the highest precedence and the expression inside it must be
converted first.
■ For performing the conversion, we use Stack data structure.
■ The stack is used to store the operators and parenthesis to enforce the precedence
Start parsing the expression from left to right.
Algorithm to convert Infix To Postfix

■ Let, X is an arithmetic expression written in infix notation. This algorithm finds the
equivalent postfix expression Y.
1. Push “(“onto Stack, and add “)” to the end of X.
2. Scan X from left to right and repeat Step 3 to 6 for each element of X until the Stack is
empty.
3. If an operand is encountered, add it to Y.
4. If a left parenthesis is encountered, push it onto Stack.
5. If an operator is encountered ,then:
1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) which
has the same precedence as or higher precedence than operator.
2. Add operator to Stack.
[End of If]
6. If a right parenthesis is encountered ,then:
1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a
left parenthesis is encountered.
2. Remove the left Parenthesis.
[End of If]
[End of If]
7. END.
■ Convert the (X - Y / (Z + U) * V) infix expression into postfix expression.
S.N. Input Operand Stack Postfix Expression
1 ( ( -
2 X ( X
3 - (- X
4 Y (- XY
5 / (-/ XY
6 ( (-/( XY
7 Z (-/( XYZ
8 + (-/(+ XYZ
9 U (-/(+ XYZU
10 ) (-/ XYZU+
11 * (-* XYZU+/
12 V (-* XYZU+/V
13 ) - XYZU+/V*-
■ Here, we have infix expression (( A * (B + D)/E) - F * (G + H / K))) to convert into its
equivalent postfix expression:
Label No. Symbol Scanned Stack Expression
1 ( (
2 ( ((
3 A (( A
4 * ((* A
5 ( ((*( A
6 B ((*( AB
7 + ((*(+ AB
8 D ((*(+ ABD
9 ) ((* ABD+
10 / ((*/ ABD+
11 E ((*/ ABD+E
12 ) ( ABD+E/*
13 - (- ABD+E/*
14 ( (-( ABD+E/*
15 F (-( ABD+E/*F
16 * (-(* ABD+E/*F
17 ( (-(*( ABD+E/*F
18 G (-(*( ABD+E/*FG
19 + (-(*(+ ABD+E/*FG
20 H (-(*(+ ABD+E/*FGH
21 / (-(*(+/ ABD+E/*FGH
22 K (-(*(+/ ABD+E/*FGHK
23 ) (-(* ABD+E/*FGHK/+
24 ) (- ABD+E/*FGHK/+*
25 ) ABD+E/*FGHK/+*-
■ Infix Expression: A+ (B*C-(D/E^F)*G)*H, where ^ is an exponential operator.
■ Infix Expression: A+ (B*C-(D/E^F)*G)*H, where ^ is an exponential operator.
Exercise

■ 5*(((9+8)+(4*6))-7)
■ ( ( ( A/ ( B / C ) ) +( D * E ) ) - ( A* C ) )
EVALUATION OF
POSTFIX
EXPRESSIONS
USING STACK
■ As Postfix expression is without parenthesis and can be evaluated as two operands and
an operator at a time, this becomes easier for the compiler and the computer to handle.

Evaluation rule of a Postfix Expression states:

■ While reading the expression from left to right, push the element in the stack if it is an
operand.
■ Pop the two operands from the stack, if the element is an operator and then evaluate it.
■ Push back the result of the evaluation. Repeat it till the end of the expression.
Algorithm

1) Add ) to postfix expression.

2) Read postfix expression Left to Right until ) encountered
3) If operand is encountered, push it onto Stack
[End If]
4) If operator is encountered, Pop two elements
i) A -> Top element
ii) B-> Next to Top element
iii) Evaluate B operator A
push B operator A onto Stack
5) Set result = pop
6) END
Expression: 456*+
Evaluating Postfix Expressions
Example 1 (a=5, b=3) Example 2(a=4, b=2, c=5, d=6, e=7, f=8,
g=3)
a b + a b - * a b ^ c d e * + f - * g /
5 3 + 5 3 - * 4 2 ^ 5 6 7 * + 8 - * 3 /
8 2 * 16 5 42 + 8 - * 3 /
8 2 * 16 5 42 + 8 - * 3 /
16 (Answer) 16 47 8 - * 3 /
16 47 8 - * 3 /
16 39 * 3 /
16 39 * 3 /
624 3 /
624 3 /
208 (Answer)
Ajit A. Diwan, Ganesh Ramakrishnan, and Deepak B. Phatak, IIT Bombay 139