UNIT-I

INTRODUCTION TO ALGORITHMS AND DATA STRUCTURES

Definition: - An algorithm is a Step By Step process to solve a problem, where each step
indicates an intermediate task. Algorithm contains finite number of steps that leads to the
solution of the problem.
Properties /Characteristics of an Algorithm:-
Algorithm has the following basic properties
 Input-Output:- Algorithm takes ‘0’ or more input and produces the required output.
This is the basic characteristic of an algorithm.
 Finiteness:- An algorithm must terminate in countable number of steps.
 Definiteness: Each step of an algorithm must be stated clearly and unambiguously.
 Effectiveness: Each and every step in an algorithm can be converted in to
programming language statement.
 Generality: Algorithm is generalized one. It works on all set of inputs and provides
the required output. In other words it is not restricted to a single input value.

Categories of Algorithm:
Based on the different types of steps in an Algorithm, it can be divided into three
categories, namely
 Sequence
 Selection and
 Iteration
Sequence: The steps described in an algorithm are performed successively one by one
without skipping any step. The sequence of steps defined in an algorithm should be simple
and easy to understand. Each instruction of such an algorithm is executed, because no
selection procedure or conditional branching exists in a sequence algorithm.
Example:
// adding two numbers
Step 1: start
Step 2: read a,b
Step 3: Sum=a+b
Step 4: write Sum
Step 5: stop
Selection: The sequence type of algorithms are not sufficient to solve the problems, which
involves decision and conditions. In order to solve the problem which involve decision
making or option selection, we go for Selection type of algorithm. The general format of
Selection type of statement is as shown below:
if(condition)
Statement-1;
else
Statement-2;
The above syntax specifies that if the condition is true, statement-1 will be executed
otherwise statement-2 will be executed. In case the operation is unsuccessful. Then
sequence of algorithm should be changed/ corrected in such a way that the system will re-
execute until the operation is successful.

1
Iteration: Iteration type algorithms are used in solving the problems which involves
repetition of statement. In this type of algorithms, a particular number of statements are
repeated ‘n’ no. of times.
Example1:

Step 1 : start
Step 2 : read n
Step 3 : repeat step 4 until n>0
Step 4 : (a) r=n mod 10
(b) s=s+r
(c) n=n/10
Step 5 : write s
Step 6 : stop
Performance Analysis an Algorithm:
The Efficiency of an Algorithm can be measured by the following metrics.
i. Time Complexity and
ii.Space Complexity.
i.Time Complexity:
The amount of time required for an algorithm to complete its execution is its time
complexity. An algorithm is said to be efficient if it takes the minimum (reasonable) amount
of time to complete its execution.
ii. Space Complexity:
The amount of space occupied by an algorithm is known as Space Complexity. An algorithm
is said to be efficient if it occupies less space and required the minimum amount of time to
complete its execution.

1. Write an algorithm for roots of a Quadratic Equation?

// Roots of a quadratic Equation
Step 1 : start
Step 2 : read a,b,c
Step 3 : if (a= 0) then step 4
else step 5
Step 4 : Write “ Given equation is a linear equation “
Step 5 : d=(b * b) _ (4 *a *c)
Step 6 : if ( d>0) then step 7 else step8
Step 7 : Write “ Roots are real and Distinct”
Step 8: if(d=0) then step 9 else step 10
Step 9: Write “Roots are real and equal”
Step 10: Write “ Roots are Imaginary”
Step 11: stop

2
2. Write an algorithm to find the largest among three different numbers entered by user
Step 1: Start
Step 2: Declare variables a,b and c.
Step 3: Read variables a,b and c.
Step 4: If a>b
If a>c
Display a is the largest number.
Else
Display c is the largest
number.
Else
If b>c
Display b is the largest number.
Else
Display c is the greatest
number.
Step 5: Stop

3.Write an algorithm to find the

factorial of a number entered by
user.
Step 1: Start
Step 2: Declare variables n,factorial and
i.
Step 3: Initialize variables
factorial←1
i←1
Step 4: Read value of n
Step 5: Repeat the steps until i=n
5.1: factorial←factorial*i
5.2: i←i+1
Step 6: Display factorial
Step 7: Stop

4.Write an algorithm
to find the Simple
Interest for given
Time and Rate of
Interest .
Step 1: Start
Step 2: Read P,R,S,T.
Step 3: Calculate S=(PTR)/100
Step 4: Print S
Step 5: Stop

ASYMPTOTIC NOTATIONS
Asymptotic analysis of an algorithm refers to defining the mathematical
boundation/framing of its run-time performance. Using asymptotic analysis, we can very
well conclude the best case, average case, and worst case scenario of an algorithm.
Asymptotic analysis is input bound i.e., if there's no input to the algorithm, it is concluded
to work in a constant time. Other than the "input"
3 all other factors are considered
constant.
Asymptotic analysis refers to computing the running time of any operation in mathematical
units of computation. For example, the running time of one operation is computed as f(n)
The time required by an algorithm falls under three types −
 Best Case − Minimum time required for program execution.
 Average Case − Average time required for program execution.
 Worst Case − Maximum time required for program execution.
Asymptotic Notations
Following are the commonly used asymptotic notations to calculate the running time
complexity of an algorithm.
 Ο Notation
 Ω Notation
 θ Notation
Big Oh Notation, Ο
The notation Ο(n) is the formal way to express the upper bound of an algorithm's running
time. It measures the worst case time complexity or the longest amount of time an
algorithm can possibly take to complete.

For example, for a function f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }
Omega Notation, Ω
The notation Ω(n) is the formal way to express the lower bound of an algorithm's running
time. It measures the best case time complexity or the best amount of time an algorithm
can possibly take to complete.

For example, for a function f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }
Theta Notation, θ
The notation θ(n) is the formal way to express both the lower bound and the upper bound
of an algorithm's running time. It is represented as follows −

4
θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }

DATA STRUCTURES
Data may be organized in many different ways logical or mathematical model of a program
particularly organization of data. This organized data is called “Data Structure”.
Or
The organized collection of data is called a ‘Data Structure’.
Data Structure=Organized data +Allowed operations

Data Structure involves two complementary goals. The first goal is to identify and develop
useful, mathematical entities and operations and to determine what class of problems can
be solved by using these entities and operations. The second goal is to determine
representation for those abstract entities to implement abstract operations on this concrete
representation.

Primitive Data structures are directly supported by the language ie; any operation is directly
performed in these data items.
Ex: integer, Character, Real numbers etc.
Non-primitive data types are not defined by the programming language, but are instead
created by the programmer.

5
 Linear data structures organize their data elements in a linear fashion, where data
elements are attached one after the other. Linear data structures are very easy to
implement, since the memory of the computer is also organized in a linear fashion. Some
commonly used linear data structures are arrays, linked lists, stacks and queues.
In nonlinear data structures, data elements are not organized in a sequential
fashion. Data structures like multidimensional arrays, trees, graphs, tables and
sets are some examples of widely used nonlinear data structures.
Operations on the Data Structures:
Following operations can be performed on the data structures:
1. Traversing
2. Searching
3. Inserting
4. Deleting
5. Sorting
6. Merging
7. Traversing- It is used to access each data item exactly once so that it can be processed.
8.Searching- It is used to find out the location of the data item if it exists in the given
collection of data items.
9. Inserting- It is used to add a new data item in the given collection of data items.
10.Deleting- It is used to delete an existing data item from the given collection of data items.
5. Sorting- It is used to arrange the data items in some order i.e. in ascending or descending
order in case of numerical data and in dictionary order in case of alphanumeric data.
6. Merging- It is used to combine the data items of two sorted files into single file in the
sorted form.

6
 UNIT-II
STACKS AND QUEUES
STACKS
A Stack is linear data structure. A stack is a list of elements in which
an element may be inserted or deleted only at one end, called the
top of the stack. Stack principle is LIFO (last in, first out). Which
element inserted last on to the stack that element deleted first from
the
stack.

As the items can be added or removed only from the top i.e. the last
item to be added to a stack is the first item to be removed.

Real life examples of stacks are:

Operations on stack:

The two basic operations associated with stacks are:

1. Push
2. Pop

While performing push and pop operations the following test must be conducted on the
stack.
a) Stack is empty or not b) stack is full or not

3.Push: Push operation is used to add new elements in to the stack. At the time of addition
first check the stack is full or not. If the stack is full it generates an error message "stack
overflow".

4.Pop: Pop operation is used to delete elements from the stack. At the time of deletion first
check the stack is empty or not. If the stack is empty it generates an error message "stack
underflow".

All insertions and deletions take place at the same end, so the last element added to
the stack will be the first element removed from the stack. When a stack is created, the
stack base remains fixed while the stack top changes as elements are added and removed.
The most accessible element is the top and the least accessible element is the bottom of the
stack.

7
Representation of Stack (or) Implementation of stack:
The stack should be represented in two ways:
1. Stack using array
2. Stack using linked list

1. Stack using array:

Let us consider a stack with 6 elements capacity. This is called as the
size of the stack. The number of elements to be added should not
exceed the maximum size of the stack. If we attempt to add new
element beyond the maximum size, we will encounter a stack
overflow condition. Similarly, you cannot remove elements beyond
the base of the stack. If such is the case, we will reach a stack
underflow condition.

1.push():When an element is added to a stack, the operation is performed by push(). Below

Figure shows the creation of a stack and addition of elements using push().

Initially top=-1, we can insert an element in to the stack, increment the top value i.e
top=top+1. We can insert an element in to the stack first check the condition is stack is full
or not. i.e top>=size-1. Otherwise add the element in to the stack.

void push() Algorithm: Procedure for push():

{
int x; Step 1: START
if(top >= n-1) Step 2: if top>=size-1 then
{ Write “ Stack is Overflow”
printf("\n\nStack
Overflow.."); Step 3: Otherwise
return; 1. : read data value ‘x’
} 2. : top=top+1;
else 3. : stack[top]=x;
{ Step 4: END
printf("\n\nEnter
data: "); scanf("%d", &x);
stack[top] = x;
top = top + 1;
printf("\n\nData Pushed into
the stack");
}
}

8
2.Pop(): When an element is taken off from the stack, the operation is performed by pop().
Below figure shows a stack initially with three elements and shows the deletion of elements
using pop().

We can insert an element from the stack, decrement the top value i.e top=top-1.
We can delete an element from the stack first check the condition is stack is empty or not.
i.e top==-1. Otherwise remove the element from the stack.

Void pop() Algorithm: procedure pop():

{ Step 1: START
If(top==-1) Step 2: if top==-1 then
{ Write “Stack is Underflow”
Printf(“Stack is Underflow”); Step 3: otherwise
} 3.1: print “deleted
else element” 3.2: top=top-1;
{ Step 4: END
printf(“Delete data %d”,stack[top]);
top=top-1;
}
}

3.display(): This operation performed display the elements in the stack. We display the
element in the stack check the condition is stack is empty or not i.e top==-1.Otherwise
display the list of elements in the stack.

9
 void display() Algorithm: procedure pop():
{ Step 1: START
If(top==-1) Step 2: if top==-1 then
{ Write “Stack is Underflow”
Printf(“Stack is Underflow”); Step 3: otherwise
} 3.1: print “Display
else elements are” 3.2: for top to 0
{ Print ‘stack[i]’
printf(“Display elements are:); Step 4: END
for(i=top;i>=0;i--)
printf(“%d”,stack[i]);
}
}

Source code for stack operations, using array:

#include<stdio.h>
#inlcude<conio.h
>
int stack[100],choice,n,top,x,i;
void push(void);
void pop(void);
void
display(void); int
main()
{
//clrscr();
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t ");
printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");
do
{
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();

break;
}
case 3: 10
{
 display();
break;
}
case 4:
{
printf("\n\t EXIT POINT ");
break;
}
default:
{
printf ("\n\t Please Enter
a Valid Choice(1/2/3/4)");
}

}
}
while(choice!=4);
return 0;
}
void push()
{
if(top>=n-1)
{
printf("\n\
tSTACK is over
flow");

}
else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
top++;
stack[top]=x;
}
}
void pop()
{
if(top<=-1)
{
printf("\n\t Stack is under flow");
}
else
{
printf("\n\t The popped elements is %d",stack[top]);
top--;
}
}
void display()
{
if(top>=0) 11
{
 printf("\n The elements in STACK \n");
for(i=top; i>=0; i--)
printf("\n%d",stack[i]);
printf("\n Press Next Choice");
}
else
{
printf("\n The STACK is
empty");
}

2. Stack using Linked List:

We can represent a stack as a linked list. In a stack push and pop operations are
performed at one end called top. We can perform similar operations at one end of list using
top pointer. The linked stack looks as shown in figure.

Applications of stack:
1. Stack is used to evaluate a postfix expression.
2. Stack is used to convert an infix expression into postfix/prefix form.
3.In recursion, all intermediate arguments and return values are stored on the processor’s
stack.
4.During a function call the return address and arguments are pushed onto a stack and on
return they are popped off.
5.Stack is used by compilers to check for balancing of parentheses, brackets and braces.
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.

12
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 as 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 as suffix notation and is
also referred to reverse polish notation.
Example: A B +
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.
b) If the scanned symbol is an operand, then place directly in the postfix expression
(output).
c) 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.
d) 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:
3. The operands maintain the same order as in the equivalent infix expression.
4. The parentheses are not needed to designate the expression unambiguously.
5. 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):

13
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.

14
15
 QUEUE
A queue is linear data structure and collection of elements. A queue is another special kind
of list, where items are inserted at one end called the rear and deleted at the other end
called the front. The principle of queue is a “FIFO” or “First-in-first-out”.
Queue is an abstract data structure. A queue is a useful data structure in programming. It is
similar to the ticket queue outside a cinema hall, where the first person entering the queue
is the first person who gets the ticket.
A real-world example of queue can be a single-lane one-way road, where the vehicle enters
first, exits first.

More real-world examples can be seen as queues at the ticket windows and bus-stops and
our college library.

The operations for a queue are analogues to those for a stack; the difference is that the
insertions go at the end of the list, rather than the beginning.
Operations on QUEUE:
A queue is an object or more specifically an abstract data structure (ADT) that allows the
following operations:
 Enqueue or insertion: which inserts an element at the end of the queue.
Dequeue or deletion: which deletes an element at the start of the queue.
Queue operations work as follows:
1. Two pointers called FRONT and REAR are used to keep track of the first and last
elements in the queue.
2. When initializing the queue, we set the value of FRONT and REAR to 0.
3. On enqueing an element, we increase the value of REAR index and place the new
element in the position pointed to by REAR.
4. On dequeueing an element, we return the value pointed to by FRONT and increase
the FRONT index.
5. Before enqueing, we check if queue is already full.
6. Before dequeuing, we check if queue is already empty.
7. When enqueing the first element, we set the value of FRONT to 1.
8. When dequeing the last element, we reset the values of FRONT and REAR to 0.

16
Representation of Queue (or) Implementation of Queue:
The queue can be represented in two ways:
1. Queue using Array
2. Queue using Linked List
1.Queue using Array:
Let us consider a queue, which can hold maximum of five elements. Initially the queue is
empty.

Now, insert 11 to the queue. Then queue status will be:

Next, insert 22 to the queue. Then the queue status is:

Again insert another element 33 to the queue. The status of the queue is:

Now, delete an element. The element deleted is the element at the front of the queue.So
the status of the queue is:

Again, delete an element. The element to be deleted is always pointed to by the FRONT
pointer. So, 22 is deleted. The queue status is as follows:

Now, insert new elements 44 and 55 into the queue. The queue status is:

17
Next insert another element, say 66 to the queue. We cannot insert 66 to the queue as the
rear crossed the maximum size of the queue (i.e., 5). There will be queue full signal. The
queue status is as follows:

Now it is not possible to insert an element 66 even though there are two vacant positions in
the linear queue. To overcome this problem the elements of the queue are to be shifted
towards the beginning of the queue so that it creates vacant position at the rear end. Then
the FRONT and REAR are to be adjusted properly. The element 66 can be inserted at the
rear end. After this operation, the queue status is as follows:

This difficulty can overcome if we treat queue position with index 0 as a position that comes
after position with index 4 i.e., we treat the queue as a circular queue.

Queue operations using array:

a.enqueue() or insertion():which inserts an element at the end of the queue.
void insertion() Algorithm: Procedure for insertion():
{ Step-1:START
if(rear==max) Step-2: if rear==max then
printf("\n Queue is Full"); Write ‘Queue is full’
else Step-3: otherwise
{ 3.1: read element ‘queue[rear]’
printf("\n Enter no Step-4:STOP
%d:",j++);
scanf("%d",&queue[rear++]);
}
}

b.dequeue() or deletion(): which deletes an element at the start of the queue.

void deletion() Algorithm: procedure for deletion():
{ Step-1:START
if(front==rear) Step-2: if front==rear then
{ Write’ Queue is empty’
printf("\n Queue is empty"); Step-3: otherwise
} 3.1: print deleted element
else Step-4:STOP
{
printf("\n Deleted Element is
%d",queue[front+
+]); x++;
}}

18
c.dispaly(): which displays an elements in the queue.
void deletion() Algorithm: procedure for deletion():
{ Step-1:START
if(front==rear) Step-2: if front==rear then
{ Write’ Queue is empty’
printf("\n Queue is empty"); Step-3: otherwise
} 3.1: for i=front to rear then 3.2:
else print ‘queue[i]’
{ Step-4:STOP
for(i=front; i<rear; i++)
{
printf("%d",queue[i])
; printf("\n");
}
}
}

2. Queue using Linked list:

We can represent a queue as a linked list. In a queue data is deleted from the front end and
inserted at the rear end. We can perform similar operations on the two ends of alist. We use
two pointers front and rear for our linked queue implementation.
The linked queue looks as shown in figure:

Applications of Queue:
1. It is used to schedule the jobs to be processed by the CPU.
2.When multiple users send print jobs to a printer, each printing job is kept in the printing
queue. Then the printer prints those jobs according to first in first out (FIFO) basis.
3. Breadth first search uses a queue data structure to find an element from a graph.

19
 CIRCULAR QUEUE
A more efficient queue representation is obtained by regarding the array Q[MAX] as
circular. Any number of items could be placed on the queue. This implementation of a
queue is called a circular queue because it uses its storage array as if it were a circle instead
of a linear list.
There are two problems associated with linear queue. They are:

 Time consuming: linear time to be spent in shifting the elements to the beginning of
the queue.
Signaling queue full: even if the queue is having vacant position.
For example, let us consider a linear queue status as follows:

Next insert another element, say 66 to the queue. We cannot insert 66 to the queue as the
rear crossed the maximum size of the queue (i.e., 5). There will be queue full signal. The
queue status is as follows:

This difficulty can be overcome if we treat queue position with index zero as a position that
comes after position with index four then we treat the queue as a circular queue.
In circular queue if we reach the end for inserting elements to it, it is possible to insert new
elements if the slots at the beginning of the circular queue are empty.
Representation of Circular Queue:
Let us consider a circular queue, which can hold maximum (MAX) of six elements. Initially
the queue is empty.

Now, insert 11 to the circular queue. Then circular queue status will be:

20
Insert new elements 22, 33, 44 and 55 into the circular queue. The circular queue status is:

Now, delete an element. The element deleted is the element at the front of the circular
queue. So, 11 is deleted. The circular queue status is as follows:

Again, delete an element. The element to be deleted is always pointed to by the FRONT
pointer. So, 22 is deleted. The circular queue status is as follows:

Again, insert another element 66 to the circular queue. The status of the circular queue is:

21
Now, insert new elements 77 and 88 into the circular queue. The circular queue status is:

Now, if we insert an element to the circular queue, as COUNT = MAX we cannot add the
element to circular queue. So, the circular queue is full.

Operations on Circular queue:

a.enqueue() or insertion():This function is used to insert an element into the circular queue.
In a circular queue, the new element is always inserted at Rear position.

void insertCQ() Algorithm: procedure of insertCQ():

{
int data; Step-1:START
if(count ==MAX) Step-2: if count==MAX then
{ Write “Circular queue is full”
printf("\n
Circular Queue Step-3:otherwise
is Full"); 1. : read the data element
} 2. : CQ[rear]=data
else 3. : rear=(rear+1)%MAX
{ 4.: count=count+1
printf("\n Enter data: "); Step-4:STOP
scanf("%d", &data);
CQ[rear] = data;
rear = (rear + 1) % MAX;
count ++;
printf("\n Data Inserted in the Circular
Queue ");
}
}

22
b.dequeue() or deletion():This function is used to delete an element from the circular
queue. In a circular queue, the element is always deleted from front position.
void deleteCQ() Algorithm: procedure of deleteCQ():
{
if(count ==0) Step-1:START
{ Step-2: if count==0 then
printf("\n\nCircular Queue is Empty.."); Write “Circular queue is empty”
} Step-3:otherwise
else 3.1: print the deleted
{
printf("\n Deleted element from Circular element 3.2:
Queue is %d ", CQ[front]); front=(front+1)%MAX
front = (front + 1) % MAX; 3.3: count=count-1
count --; Step-4:STOP
}
}

c.dispaly():This function is used to display the list of elements in the circular queue.
void displayCQ() Algorithm: procedure of displayCQ():
{
int i, j; Step-1:START
if(count ==0) Step-2: if count==0 then
{ Write “Circular queue is empty”
printf("\n\n\ Step-3:otherwise
t Circular 3.1: print the list of
Queue is elements 3.2: for i=front to
Empty "); j!=0
} 3.3: print CQ[i]
else 3.4: i=(i+1)%MAX
{ Step-4:STOP
printf("\n Elements in Circular Queue are:
");
j = count;
for(i = front; j != 0; j--)
{
printf("%d\t", CQ[i]);
i = (i + 1) % MAX;
}
}
}

Deque:
In the preceding section we saw that a queue in which we insert items at one end and from
which we remove items at the other end. In this section we examine an extension of the
queue, which provides a means to insert and remove items at both ends of the queue. This
data structure is a deque. The word deque is an acronym derived from double-ended queue.
Below figure shows the representation of a deque.

23
deque provides four operations. Below Figure shows the basic operations on a deque.
• enqueue_front: insert an element at front.
• dequeue_front: delete an element at front.
• enqueue_rear: insert element at rear.
• dequeue_rear: delete element at rear.

There are two variations of deque. They are:

• Input restricted deque (IRD)
• Output restricted deque (ORD)
An Input restricted deque is a deque, which allows insertions at one end but allows
deletions at both ends of the list.
An output restricted deque is a deque, which allows deletions at one end but allows
insertions at both ends of the list.
Priority Queue:
A priority queue is a collection of elements such that each element has been assigned a
priority. We can insert an element in priority queue at the rare position. We can delete an
element from the priority queue based on the elements priority and such that the order in
which elements are deleted and processed comes from the following rules:

1. An element of higher priority is processed before any element of lower priority.

2.Two elements with same priority are processed according to the order in which they were
added to the queue. It follows FIFO or FCFS(First Comes First serve) rules.

24
We always remove an element with the highest priority, which is given by the minimal
integer priority assigned.

A prototype of a priority queue is time sharing system: programs of high priority are
processed first, and programs with the same priority form a standard queue. An efficient
implementation for the Priority Queue is to use heap, which in turn can be used for sorting
purpose called heap sort

Priority queues are two types:

1. Ascending order priority queue
2. Descending order priority queue
3.Ascending order priority queue: It is Lower priority number to high priority number.
Examples: order is 1,2,3,4,5,6,7,8,9,10
4.Descending order priority queue: It is high priority number to lowest priority number.
Examples: Order is 10,9,8,7,6,5,4,3,2,1
Implementation of Priority Queue:
Implementation of priority queues are two types:
1. Through Queue(Using Array)
2. Through Sorted List(Using Linked List)
1. Through Queue (Using Array): In this case element is simply added at the rear end as
usual. For deletion, the element with highest priority is searched and then deleted.

2. Through sorted List (Using Linked List): In this case insertion is costly because the
element insert at the proper place in the list based on the priority. Here deletion is easy
since the element with highest priority will always be in the beginning of the list.

25
 1. Difference between stacks and Queues?
stacks Queues
1. A stack is a linear list of elements in which 1. A Queue is a linerar list of elements in which
the element may be inserted or deleted at the elements are added at one end and
one end. deletes the elements at another end.
2.. In Queue the element which is inserted
2.In stacks, elements which are inserted first is the element deleted first.
last is the first element to be deleted.
3.Queues are called FIFO (First In First
3.Stacks are called LIFO (Last In First Out)list.
Out)list
4.In Queue elements are removed in the
4.In stack elements are removed in reverse same order in which thy are inserted.
order in which thy are inserted.
5.Suppose the elements a,b,c,d,e are inserted
5.suppose the elements a,b,c,d,e are in the Queue, the deletion of elements will be
inserted in the stack, the deletion of in the same order in which thy are inserted.
elements will be e,d,c,b,a.
6.In Queue there are two pointers one for
6.In stack there is only one pointer to insert insertion called “Rear” and another for
and delete called “Top”. deletion called “Front”.
7. Initially top=-1 indicates a stack is empty. 7.Initially Rear=Front=-1 indicates a Queue is
empty.
8.Stack is full represented by the condition
TOP=MAX-1(if array index starts from ‘0’). 8.Queue is full represented by the condition
Rear=Max-1.
9.To push an element into a stack, Top is
incremented by one 9.To insert an element into Queue, Rear is
incremented by one.
10.To POP an element from stack,top is
decremented by one. 10. To delete an element from Queue,
Front is

26