UNIT - II

STACK AND QUEUE OPERATIONS

1. Explain Array (static) implementation of stack with example

STACK ADT
 A stack is a dynamic and ordered collection of elements in which the insertion and deletion
are restricted at only one end.
 The end from which the elements are added and deleted is referred as the ‘top’ of the stack.
 Stack is also referred as PILES or PUSH down list. The last element placed in the stack will
be at the top of the stack.
 The last element added to the stack is the first element to be removed. Hence stack are
referred as LAST IN FIRST OUT.

Operations:

Operations Axioms
Push Push is an operation to add new element at top in the stack.
Pop Pop is an operation to delete an element at top of the stack
Peak To display the element at top in the stack
Display To display the elements from top to 0 position in the stack

Representation of Stack
Stack can be represented using 2 ways:
 Static implementation of stack using array
 Dynamic implementation of stack using linked list

Static Implementation of Stack Using ARRAY

 The simplest way of representing a stack is single dimensional array. Both stack and array are
ordered collection of elements but array and stack are 2 different things:
 In array, the number of elements in the array is fixed so insertion and deletion is not possible.
 In stack, the size of the stack varies continuously when elements are pushed and popped.
 Since the stack is stored in part of array, an array can be declared large enough to hold
maximum number of elements of the stack.
 During the execution of the program, the stack size can be varied within the space reserved
for it.
 One end of the array (bottom of the sack) is fixed and the other end of the array (top of the
stack) is continuously changed depending upon the elements pushed or popped in the stack.
Basic Operations
 Push
 Pop
 Peak
 Display

1. PUSH
 Push is an operation used to add new element into the stack.
 While implementing the push operation, overflow condition of the stack is to be checked, to
avoid to push an element in the fully occupied stack.

Algorithm Push(stack, top, stack_size , value)

{
if top = stack_size -1then // Is stack Full ?
{
write "Stack is in overflow condition. Push operation is not possible.";
return;
}
// Is stack not Full ?
top = top + 1;
stack[top] = value;
}

Example: Pushing elements in Empty stack 9

8
7
top = -1 6
5
queue_size = 10
4
3
2
1
0

To push the value 101: stack

top = top + 1 => top = -1 + 1 => top =0

stack[top] = value => stack[0] = 101

 9
8
7
6
5
4
3
2
1
top 0 101
stack
To push the value 102:

top = top + 1 => top = 0 + 1 => top = 1

stack[top] = value => stack[1] = 102

9
8
7
6
5
4
3
2
top 1 102
0 101
stack
To push the value 103:

top = top + 1 => top = 1 + 1 => top = 2

stack[top] = value => stack[2] = 103

9
8
7
6
5
4
3
top 2 103
1 102
0 101
stack
To push the value 104:

top = top + 1 => top = 2 + 1 => top = 3

stack[top] = value => stack[3] = 104

9
8
7
6
5
4
top 3 104
2 103
1 102
0 101
stack
2. POP
 Pop is an operation used to remove an element from the top of the stack.
 While implementing the pop operation, underflow condition of stack is to be checked to
avoid top of an element from the empty stack.

Algorithm Pop(stack, top)

{
if top = -1 then // Is stack empty ?
{
write "Stack is underflow condition. Pop operation is not possible.";
return;
}
// Is stack not empty?
del_element = stack[top];
write del_element , “was deleted.",
top = top -1;
}

Example: Pop element in Non-empty stack

9
8
7
6
5
4
top 3 104
2 103
1 102
0 101
stack
top = top -1 => top = 3 – 1 = 2 => top = 2

9
8
7
6
5
4
3
top 2 103
1 102
0 101
stack

top = top -1 => top = 2 – 1 = 1 => top = 1

9
8
7
6
5
4
3
2
top 1 102
0 101
stack

top = top -1 => top = 1 – 1 = 0 => top = 0

9
8
7
6
5
4
3
2
1
top 0 101
stack

top = top -1 => top = 0 – 1 = -1 => top = -1

since stack becomes empty (top = -1) , pop operation is not possible
3.PEAK

 Peak operation is used to display the element from the stack pointed by top.
 While implementing the peak operation the underflow condition of the stack is to be checked
to peak an element from an empty stack.

Algorithm Peak( stack , top)

{
if top = -1 then // Is stack empty ?
{
write "Stack is in underflow condition. Peak operation is not possible.";
return;
}
// Is stack not empty?
write stack[top];
return;
}

Example: Peak element in Non-empty stack

9
8
7
6
5
4
top 3 104
2 103
1 102
0 101
stack

display stack[top] => display stack [3] => display 104

4.Display

 To display the element from the stack, traverse in the stack from top to 0 position.

 During implementation of the display operation, the underflow condition of the stack is to be
checked to avoid retrieving an element from empty stack.
Algorithm Display(stack , top)
{
if top = -1 then // Is stack empty ?
{
write "Stack is in underflow condition. Display operation is not possible.";
return;
}
// Is stack not empty ?
for i = top to step -1 do
{
write stack[top];
}
}
Example: Peak element in Non-empty stack

9
8
7
6
5
4
top 3 104
2 103
1 102
0 101
stack

Display elements from top to 0

display stack [3] => display 104

display stack [2] => display 103
display stack [1] => display 102
display stack [0] => display 101
2. Applications of stack
1. Stack is used by compilers to check for balancing of parentheses, brackets and braces.
2. Stack is used to evaluate a postfix expression.
3. Stack is used to convert an infix expression into postfix/prefix form.
4. In recursion, all intermediate arguments and return values are stored on the processor’s
stack.
5. During a function call the return address and arguments are pushed onto a stack
and on return they are popped off.
Converting and evaluating Algebraic expressions:
An algebraic expression is a legal combination of operators and operands. Operand is the
quantity on which a mathematical operation is performed. Operand may be a variable like x, y, z or
a constant like 5, 4, 6 etc. Operator is a symbol which signifies a mathematical or logical operation
between the operands. Examples of familiar operators include +, -, *, /, ^ etc. An algebraic
expression can be represented using three different notations. They are infix, postfix and prefix
notations:
Infix:
It is the form of an arithmetic expression in which we fix (place) the arithmetic operator in
between the two operands.
Example: A + B
Prefix:
It is the form of an arithmetic notation in which we fix (place) the arithmetic operator before
(pre) its two operands. The prefix notation is called polish notation.
Example: + A B
Postfix:
It is the form of an arithmetic expression in which we fix (place) the arithmetic operator after
(post) its two operands. The postfix notation is called suffix notation and is also referred to reverse
polish notation.
Example: A B +
i). Conversion from infix to postfix:
Procedure to convert from infix expression to postfix expression is as follows:
1. Scan the infix expression from left to right.
2. a) If the scanned symbol is left parenthesis, push it onto the stack.
a) If the scanned symbol is an operand, then place directly in the postfix expression
(output).
b) If the symbol scanned is a right parenthesis, then go on popping all the items from the
stack and place them in the postfix expression till we get the matching left parenthesis.
c) If the scanned symbol is an operator, then go on removing all the operators from the
stack and place them in the postfix expression, if and only if the precedence of the operator
which is on the top of the stack is greater than (or greater than or equal) to the precedence
of the scanned operator and push the scanned operator onto the stack otherwise, push the
scanned operator onto the stack.
The three important features of postfix expression are:
1. The operands maintain the same order as in the equivalent infix expression.
2. The parentheses are not needed to designate the expression unambiguously.
3. While evaluating the postfix expression the priority of the operators is no longer relevant.
We consider five binary operations: +, -, *, / and $ or ↑ (exponentiation). For these binary
operations, the following in the order of precedence (highest to lowest):
ii). Evaluation of postfix expression:
The postfix expression is evaluated easily by the use of a stack.
1. When a number is seen, it is pushed onto the stack;
2. When an operator is seen, the operator is applied to the two numbers that are
popped from the stack and the result is pushed onto the stack.
3. When an expression is given in postfix notation, there is no need to know any
precedence rules; this is our obvious advantage.

iii). Conversion from infix to prefix:

Step 1: Reverse the infix expression i.e A+B*C will become C*B+A. Note while
reversing each ‘(‘ will become ‘)’ and each ‘)’ becomes ‘(‘.
Step 2: Obtain the “nearly” postfix expression of the modified expression i.e
CB*A+.
Step 3: Reverse the postfix expression. Hence in our example prefix is +A*BC.
 Example

iv). Evaluation of Prefix Expression

Step 1: Start from the last element of the expression.
Step 2: check the current element.
Step 2.1: if it is an operand, push it to the stack.
Step 2.2: If it is an operator, pop two operands from the stack. Perform the operation and
push the elements back to the stack.
Step 3: Do this till all the elements of the expression are traversed and return the top of stack
which will be the result of the operation.
3. What is Queue ADT and explain various types of queue

Queue ADT
 Queue is a dynamic and ordered collection of elements in which insertion are made at one
end and deletion are made at another end.
 The end at which insertion are made is referred as rear end. The end from which deletion are
made is referred as front end.
 In a queue the first element is to be deleted , so that queue is known as “first in first out”.

Instance:

A stack is a dynamic and ordered collection of elements E1, E2,…, En of size n arranged in a
linear sequence where Ei refers to the ith element in the list.

Operations:

Operations Axioms
Enqueue Enqueue is an operation to add new element at rear end in the queue.
Dequeue Pop is an operation to delete an element at front end in the queue
Peak To display the element at front end in the queue
Display To display the elements from front to rear in the queue

Types of queue
1. Linear Queue
2. Circular Queue
3. Double ended queue

(i) Linear queue

 Linear queue is an ordered collection of elements in which insertion is made at one end
and deletion are made at another end.
 The end at which insertion are made is referred as rear end. The end from which deletion
are made is referred as front end.
 In a queue the first element is to be deleted, so that queue is known as “first in first out”.

(ii) Circular Queue

 Circular Queue is another form of linear queue in which last position is connected to the first
position of the queue. Circular queue also has two ends:-
1. Front
2. Rear
 The front end is where we delete element and the rear end is where we insert element. The next
position of the rear is front, then the queue is said to be fully occupied.
 (iii) Double Ended Queue
 In double ended queue, insertion and deletion are made at both rear and front end of the queue.
They are two variations of deque.
1. Input restricted deque
2. Output restricted deque
 In input restricted deque, insertion is restricted at one end only (it can be either front or rear
end). In output restricted deque, the deletion is restricted to one end only (it can be either front
or rear end).
Types of deque
1. Linear deque
2. Circular deque
Linear Deque
 It is similar to the linear queue except the following conditions:
 If the front pointer is in the first position (zeroth position), we can’t insert data at front end.
 If the rear is in the last position (queuesize-1) we can’t insert data at rear end.
Circular Deque
 Circular deque is similsr to circular queue except the following conditions:
 Insertion and deletion are made at front and rear end of the queue.Irrespective of the
position of the front and rear we can insert and delete

4. Explain Static implementation (Representation) of linear queue using Array

 One of the simplest ways of representing a queue is by means of single dimensional array. Both
queue & array are the ordered collection of elements but queue & array are different things.
 In array, the number of elements in the array is fixed so insertion and deletion is not possible.
 In queue, the size of the queue varies continuously when elements are enqueued and dequeued
 Since the queue is stored in part of array, an array can be declared large enough to hold maximum
number of elements of the queue.
 During the execution of the program, the queue size can be varied within the space reserved for it.
 One end of the array (front of the queue) is fixed and the other end of the array (rear of the queue)
is continuously changed within size of array depending upon the elements enqueued or dequeued
in the queue.

Basic operations
1. Enqueue
2. Dequeue
3. Peak
4. Display
 The rear pointer is in the last position (queue size-1) then queue is said to be fully occupied.
Initially the front end and the rear end are at the same position (-1). When you insert elements,
rear pointer moves one by one until the last position is reached.
 When we delete elements, the front pointer moves one by one until it reaches rear pointer.
 Beyond this we can’t insert the data, irrespective of position of front pointer; this is a main
disadvantage of linear queue which is overcome by circular queue.
1) Enqueue Operation

Enqueue is an operation used to add an element at rear end of the queue. While implementing enqueue
operation, overflow condition of the queue must be checked to avoid to enqueue an element in empty
queue

Algorithm Enqueue(queue , rear , front , queue_size , value)

{
if rear = queue_size-1 then // Is queue Full ?
{ write "queue is in overflow condition. Thus enqueue operation is not possble.";
return;
}
if rear = -1 and front = -1 then // Is queue Empty?
{
rear = 0;
front = 0;
}
else // Is queue not Empty?
{
rear=rear+1;
}
queue[rear] = value;
}

Example: Enqueue operation in Empty queue

0 1 2 3 4 5 6 7 8 9
queue :

queue_size = 10 front = -1 rear = -1

To enqueue value 101 (in empty queue)

front = 0
rear = 0
queue [rear] = value => queue [0] = 101

0 1 2 3 4 5 6 7 8 9
queue : 101

front rear
To enqueue value 102 (in non-empty queue)

rear = rear + 1 => rear = 0 + 1 => rear =1

queue [rear] = value => queue [1] = 102

0 1 2 3 4 5 6 7 8 9
queue : 101 102

front rear

To enqueue value 103 (in non-empty queue)

rear = rear + 1 => rear = 1 + 1 => rear = 2

queue [rear] = value => queue [2] = 103

0 1 2 3 4 5 6 7 8 9
queue : 101 102 103

front rear
To enqueue value 104 (in non-empty queue)

rear = rear + 1 => rear = 2 + 1 => rear = 3

queue [rear] = value => queue [3] = 104

0 1 2 3 4 5 6 7 8 9
queue : 101 102 103 104

front rear
2) Dequeue

Dequeue is an operation to delete an element at front end of the queue

Algorithm Dequeue(queue , rear , front , queuesize)

{
if rear = -1 and front = -1 then // Is queue Empty?
{
write "queue is in overflow condition. Thus dequeue opeation is not possble.";
return;
}
del_element = queue[front];
write del_element , “ was deleted”;
if rear = front then // Does queue contain one element?
{
rear = -1
front = -1;
}
else // Does queue contain more elements
{
front=front+1;
}
}

Example: Dequeue operation in non-empty queue

0 1 2 3 4 5 6 7 8 9
queue : 101 102 103 104

front rear

0 1 2 3 4 5 6 7 8 9
queue : 101 102 103 104

front rear

front = front + 1 => front = 0 + 1 = 1 => front =1

0 1 2 3 4 5 6 7 8 9
queue : 102 103 104

front rear
 front = front + 1 => front = 1 + 1 = 1 => front = 2

0 1 2 3 4 5 6 7 8 9
queue : 103 104

front rear

front = front + 1 => front = 2 + 1 = 1 => front = 3

0 1 2 3 4 5 6 7 8 9
queue : 104

front rear

front = front + 1 => front = 3 + 1 = 1 => front = 4

0 1 2 3 4 5 6 7 8 9
queue :

front = -1 rear = -1

since queue becomes empty(front = -1 and rear = -1), dequeue operation is not possible

3) Peak

Peak is an operation to display the element at front end of the queue

Algorithm display(queue,front,rear)
{
if front = -1 and rear = -1 then // Is queue Empty?
{
write "queue is in underflow condition. peak operation is not possible.";
return;
}
// Is queue not Empty?
write queue[front];

}
Example: Pear operation in non-empty queue
0 1 2 3 4 5 6 7 8 9
queue : 101 102 103 104

front rear

display queue[front] => display queue[0] => display 10

4) Display
Display is an operation to traverse queue to retrieve and display the elements in the queue from front to
rear

Algorithm display(queue , front , rear)

{
if front = -1 and rear = -1 then // Is queue Empty?
{
write "queue is in underflow condition. Display operation is not possible.";
return;
}
// Is queue Empty?
for i=front to rear do
{
write queue[i];
}

Example: Display operation in non-empty queue

0 1 2 3 4 5 6 7 8 9
queue : 101 102 103 104

front rear

Display elements from front to rear

display queue[0] => display 101

display queue[1] => display 102
display queue[2] => display 103
display queue[3] => display 104
5. Explain basic operations of circular queue in detail
 Circular Queue is the form of linear queue in which last position is connected to the first position
of the queue. Circular queue also has two ends:-
3. Front
4. Rear
 The front end is where we delete element and the rear end is where we insert element. The next
position of the rear is front, then the queue is said to be fully occupied.

Basic operations
1. Enqueue
2. Dequeue
3. Peak
4. Display

1) Enqueue Operation

Enqueue is an operation to add an element at rear end of the queue

Algorithm enqueue(queue , front , rear , queue_size , value)

{
if (rear+1) % queue_size = front then // Is queue Full?
{
write "queue is in overflow condition. Enqueue operation is not possible.";
return;
}

if front = -1 and rear = -1 then // Is queue Empty?

{
front = 0;
rear = 0;
}
else // Is queue not Empty?
{
rear = (rear+1) % queue_size;
}
queue[rear] = value;
}
Example: Enqueue operation in non-empty queue

queue_size = 10

queue
To enqueue the value 124

rear = (rear +1) % queue_size => rear = (9+1) % 10 => rear =10 % 10 => rear = 0

queue[rear] = value => queue[0] = 124

2) Dequeue

Dequeue is an operation to delete an element at front end of the queue

Algorithm Dequeue(queue, front, rear, queue-size)

{
if front=-1 and rear=-1then // Is queue Empty?
{
write "queue is in underflow condition. Dequeue operation is not possible.";
return;
}
// Is queue not Empty?
del_element = queue[front];
write del_element , “was deleted",
if front = rear then // Does queue contain one element?
{
front = -1;
rear=-1;
}
 else // Does queue contain more element?
{
front = (front+1) % queue-size;
}

Example: Dequeue operation in non-empty queue

queue_size = 10

queue

queue_size = 10

queue

front = (front +1) % queue_size => front = (3+1) % 10 => front = 4 % 10 => rear = 4
3) Peak

Peak is an operation to display the element at front end of the queue

Algorithm Peak(queue, front, rear)

{
if front=-1 and rear=-1 // Is queue Empty?
{
write "Queue is in underflow condition. Dequeue operation is not possible.";
return;
}
// Is queue not Empty
write queue[front];

}
Example: Peak operation in non-empty queue

queue_size = 10

queue

display queue[front] => display queue[3] => display 197

4) Display
Display is an operation to traverse queue to retrieve and display the elements in the queue from front to
rear

Algorithm display(queue, front, rear, queue_size)

{
if front=-1 and rear=-1 // Is queue Empty?
{
write "Queue is in underflow condition. Dequeue operation is not possible.";
return;
}
// Is queue not Empty?
i=front;
while(i!=rear)
{
write queue[i];
i=(i+1) % queue_size;
}
write queue[rear];

Example: Display operation in non-empty queue

queue_size = 10

queue

Display elements from front to rear

display queue[3] => display 197

display queue[4] => display 103
display queue[5] => display 104
display queue[6] => display 105
display queue[7] => display 111
display queue[8] => display 109
display queue[9] => display 11
6. Explain basic operations of Double Ended Queue (DEQUE)
In double ended queue, insertion and deletion are made at both rear and front end of the queue.
They are two variations of deque.
 Input restricted deque
 Output restricted deque
In input restricted deque, insertion is restricted at one end only (it can be either front or rear end).
In output restricted deque, the deletion is restricted to one end only (it can be either front or rear end).

Types of deque
 Linear deque
 Circular deque
Linear Deque
It is similar to the linear queue except the following conditions:
 If the front pointer is in the first position (zeroth position), we can’t insert data at front
end.
 If the rear is in the last position (queuesize-1) we can’t insert data at rear end.
Circular Deque
Circular deque is similsr to circular queue except the following conditions:
 Insertion and deletion are made at front and rear end of the queue.
 Irrespective of the position of the front and rear we can insert and delete he data.

Basic operations
1. Enqueue_front
2. Enqueue_rear
3. Dequeue_front
4. Dequeue_rear
1) Enqueue Operation

Enqueue is an operation to add an element at rear end of the queue

i) Enqueue - Front

Algorithm Eenqueue_front (queue , front , rear , queue_size , value)

{
if front = 0 then // Is queue full?
{
write "queue is in overflow condition. Enqueue is not possible.";
return;
}
if front = -1 and rear = -1then // Is queue Empty?
{
front = queue_size -1;
rear = queue_size - 1;
}
else // Is queue NOTEmpty?
{
front = front - 1;
}
queue[front] = value;
}

Example: Enqueue-front operation in empty queue

front = -1 rear = -1 queue_size = 10

0 1 2 3 4 5 6 7 8 9
queue :

To enqueue the value 101

rear = queue_size -1 => rear = 9

front = queue_size -1 => front = 9
queue [front] = value => queue[9] =101
0 1 2 3 4 5 6 7 8 9
queue : 101

front rear
To enqueue the value 102

front =front - 1 => front = 9 – 1 => front = 8

queue [front] = value => queue[8] =102

0 1 2 3 4 5 6 7 8 9
queue : 102 101

To enqueue the value 103 front rear

front =front - 1 => front = 8 – 1 => front = 7

queue [front] = value => queue[7] =103

0 1 2 3 4 5 6 7 8 9
queue : 103 102 101

To enqueue the value 104 front rear

front =front - 1 => front = 7 – 1 => front = 6

queue [front] = value => queue[6] =104

0 1 2 3 4 5 6 7 8 9
queue : 104 103 102 101

front rear
To enqueue the value 105

front =front - 1 => front = 6 – 1 => front = 5

queue [front] = value => queue[5] =104

0 1 2 3 4 5 6 7 8 9
queue : 105 104 103 102 101

front rear
ii) Enqueue - rear
Algorithm Enqueue_rear (queue , rear , front , queue_size , value)
{
if rear = queue_size-1 then // Is queue Full ?
{ write "queue is in overflow condition. Thus enqueue operation is not possble.";
return;
}
if rear=-1 and front=-1 then // Is queue Empty?
{
rear = 0;
front = 0;
}
else // Is queue not Empty?
{
rear=rear+1;
}
queue[rear] = value;
}
Example: Enqueue-rear operation in Empty queue

0 1 2 3 4 5 6 7 8 9
queue :

queue_size = 10 front = -1 rear = -1

To enqueue value 101 (in empty queue)

front = 0
rear = 0
queue [rear] = value => queue [0] = 101

0 1 2 3 4 5 6 7 8 9
queue : 101

front rear
 To enqueue value 102 (in non-empty queue)

rear = rear + 1 => rear = 0 + 1 => rear =1

queue [rear] = value => queue [1] = 102

0 1 2 3 4 5 6 7 8 9
queue : 101 102

front rear

To enqueue value 103 (in non-empty queue)

rear = rear + 1 => rear = 1 + 1 => rear = 2

queue [rear] = value => queue [2] = 103

0 1 2 3 4 5 6 7 8 9
queue : 101 102 103

front rear
To enqueue value 104 (in non-empty queue)

rear = rear + 1 => rear = 2 + 1 => rear = 3

queue [rear] = value => queue [3] = 104

0 1 2 3 4 5 6 7 8 9
queue : 101 102 103 104

front rear
2) Dequeue

Dequeue is an operation to delete an element at front end of the queue

i). Dequeue_front

Algorithm Dequeue_front (queue , rear , front)

{
if rear = -1 and front = -1 then // Is queue Empty?
{
write "queue is in overflow condition. Thus dequeue opeation is not possble.";
return;
}
// Is queue not Empty?
del_element = queue[front];
write del_element , “ was deleted”;
if rear = front then // Does queue contain one element?
{
rear = -1
front = -1;
}
else // Does queue contain more elements
{
front = front +1;
}
}

Example: Dequeue-front operation in non-empty queue

0 1 2 3 4 5 6 7 8 9
queue : 101 102 103 104

front rear

0 1 2 3 4 5 6 7 8 9
queue : 101 102 103 104

front rear

front = front + 1 => front = 0 + 1 = 1 => front =1

0 1 2 3 4 5 6 7 8 9
queue :
102 103 104

front rear
 front = front + 1 => front = 1 + 1 = 1 => front = 2

0 1 2 3 4 5 6 7 8 9
queue : 103 104

front rear

front = front + 1 => front = 2 + 1 = 1 => front = 3

0 1 2 3 4 5 6 7 8 9
queue : 104

front rear

front = front + 1 => front = 3 + 1 = 1 => front = 4

0 1 2 3 4 5 6 7 8 9
queue :

front = -1 rear = -1

since queue becomes empty(front = -1 and rear = -1), dequeue operation is not possible
ii). Dequeue_rear

Algorithm dequeue_rear (queue , front , rear)

{
if rear=-1 and front=-1 then // Is queue Empty?
{
write "queue is in underflow condition. Dequeue is not possible.";
return;
}
// Is queue not Empty?
del_element = queue[front];
write del_element , “ was deleted”;
if front=rear then
{ front=rear=-1; // Does queue contain one elements
}
else // Does queue contain more elements
{
rear = rear -1;
}
}

Example: Dequeue-rear operation in non-empty queue

0 1 2 3 4 5 6 7 8 9
queue : 104 103 102 101

front rear

0 1 2 3 4 5 6 7 8 9
queue : 104 103 102 101

front rear
rear = rear -1 => rear = 9 -1 => rear = 8

0 1 2 3 4 5 6 7 8 9
queue : 104 103 102

front rear
rear = rear -1 => rear = 9 -1 => rear = 8
 0 1 2 3 4 5 6 7 8 9
queue : 104 103

front rear
rear = rear -1 => rear = 8 -1 => rear = 7

0 1 2 3 4 5 6 7 8 9
queue : 104

front rear
rear = rear -1 => rear = 7 -1 => rear = 6

0 1 2 3 4 5 6 7 8 9
queue : 104

front rear
front = -1 rear = -1
since queue becomes empty(front = -1 and rear = -1) , dequeue operation is not possible

7. Discuss any one of the application of queue in detail (or) Application of queue
 Direct applications
o Access to shared resources (e.g., printer)
o Multiprogramming
 Indirect applications
o Priority queue
o Auxiliary data structure for algorithms
o Component of other data structures
Priority queue
 Priority queue is a data structure having collection of elements which are associated with specific
order. They are of two types:
1. Ascending Priority Queue
2. Descending Priority Queue
Ascending Priority Queue
 It is a collection of elements in which the insertion of element can be any order, but only the
smallest element can be removed.

Descending Priority Queue

 It is a collection of elements in which the insertion of element can be any order, but only the
largest element can be removed.
 In priority queue, elements are arranged in any order and out of which only the smallest or largest
element allowed to be deleted each time.
 The implementation of priority can be done by using array and linked list. The data structure heap
is used to implement priority queue efficiently.
 Basic Operations
 Enqueue
 Dequeue

1. Enqueue

Algorithm Enqueue_priority(queue , front , rear , queue_size , value)

{
if rear=queuesize-1; // Is queue Full?
{
write "Queue is in overflow condition. Enqueue is not possible.";
return;
}
if front=-1 and rear=-1 then // Is queue Empty?
{
front = 0;
rear = 0;
}
else // Is queue not Empty?
{
i = rear;
while(i>=front)and (value <= queue[i])
{
queue[i+1]=queue[i]; // Insertion of an element in
//appropriate position by right shift
i = i -1;
}
queue[i+1] = value;
rear = rear+1;

}
}

Example: Enqueue operation in non-empty queue

0 1 2 3 4 5 6 7 8 9
queue : 101 104 107 114

front rear
To enqueue the value 103

Find the appropriate position to insert the value 103 by traversing from rear to front

i = rear to front => i = 3 to 0

i=3
103 < queue[3]?

102 < 114 true => queue[i+1] =queue[i] => queue[4] = queue[3]

i = i – 1 => i = 3 – 1 => i = 2

0 1 2 3 4 5 6 7 8 9
queue : 101 104 107 114

front rear

i=2
103 < queue[2] ?

102 < 107 true => queue[i+1] =queue[i] => queue[3] = queue[2]

i= i–1 => i = 2 – 1 => i = 1

0 1 2 3 4 5 6 7 8 9
queue : 101 104 107 114

front rear

i=1

103 < queue[1]?

103 < 104 true => queue[i+1] =queue[i] => queue[2] = queue[1]

i = i – 1 => i = 1 – 1 => i = 0

0 1 2 3 4 5 6 7 8 9
queue : 101 104 107 114

front rear
 i=0

103 < queue[0]?

103 < 101 false => queue[i+1] =value => queue[1] = 103 => Insertion of the value
0 1 2 3 4 5 6 7 8 9
queue : 101 103 104 107 114

front rear

2) Dequeue

Dequeue is an operation to delete an element at front end of the queue

Algorithm Dequeue_priority (queue , rear , front)

{
if rear = -1 and front = -1 then // Is queue Empty?
{
write "queue is in overflow condition. Thus dequeue opeation is not possble.";
return;
}
// Is queue not Empty?
del_element = queue[front];
write del_element , “ was deleted”;
if rear = front then // Does queue contain one element?
{
rear = -1
front = -1;
}
else // Does queue contain more elements
{
front = front +1;
}
}
Example: Dequeue operation in non-empty queue

0 1 2 3 4 5 6 7 8 9
queue : 101 102 103 104

front rear

0 1 2 3 4 5 6 7 8 9
queue : 101 102 103 104

front rear

front = front + 1 => front = 0 + 1 = 1 => front =1

0 1 2 3 4 5 6 7 8 9
queue : 102 103 104

front rear

front = front + 1 => front = 1 + 1 = 1 => front = 2

0 1 2 3 4 5 6 7 8 9
queue : 103 104

front rear

front = front + 1 => front = 2 + 1 = 1 => front = 3

0 1 2 3 4 5 6 7 8 9
queue : 104

front rear

front = front + 1 => front = 3 + 1 = 1 => front = 4

 0 1 2 3 4 5 6 7 8 9
queue :

front = -1 rear = -1

since queue becomes empty(front = -1 and rear = -1), dequeue operation is not possible