DATA

STRUCTURES
Data Structures

Data Structure is a way of organizing and

storing data efficiently in the computer’s
memory.
Two major categorization of Data Structures
are:
Static Data Structure
Dynamic Data Structures
 Differences
Static Data Structure Dynamic Data
Structure
Example: Array Example: Linked List,
[Link] is predetermined Tree
[Link] has to be allotted [Link] is not predetermined
well in advance [Link] is allotted as and
[Link] allocated cannot when it is required
be released when not in use [Link] allocated can be
[Link] of memory is in released when not in use
contiguous locations [Link] of memory is in
[Link] of data is random locations
sequential as well as random [Link] of data is
[Link] is faster through random mode only
[Link] and deletion [Link] is slower compared
operations are cumbersome to static data structure
[Link] and deletion
operations are easier
 Types of Data Structures

Data Structures can be of different types

such as : Stacks and Queues
Useful for manipulating large collections of
data
Each is defined by two basic operations:
insert a new item
remove an item.
What is a queue?
It is an ordered group of
homogeneous items.
Queues have two ends:
 Items are added at one end known as rear
 Items are removed from the other end

known as front
 FIFO

FIFO property: First In, First Out

The item added first is also removed first
 Queue Implementations

Array-based
Logically a queue is a FIFO structure
and physically it can be implemented
either as an array or as a linked list

Linked-list-based
 Queue as an Array

When a Queue is created as an array, the number

of elements must be declared before processing.
Initially, when an element is added for the first
time, the first position of the array (Queue)
becomes its front and rear.
Subsequently after addition of every new
element, the value of rear is increased by 1.
Similarly after every deletion, the value of front
is increased by 1.
Note: The decision to shift the elements after
every deletion operation, can be decided by the
programmer based on the size of the Queue.
 Size of a Queue

The front pointer points to the index of the

first element and the rear pointer points to
the index of the last element in the Queue.
The number of elements in a Queue at any
given time can be calculated from the values
of the front and the rear as follows:
 Count = rear – front +1;
OR
 (N-front+rear)%N
Enqueue Operation
(adding new elements)
Adds new Item to the rear of the queue.
Issues to be taken care of:
 Queue must be initialized
 Queue must not be full.
 Algorithm for inserting an element in a
Queue

 if rear = null then // checking if Queue is empty

 { rear=0
 front=0
 Que[rear]=n
}
 Else
 if rear = N- 1 then
 print “Queue full”
 else
 {
 rear=rear+1
 Que[rear]=n
 }
Dequeue Operation
(deleting an element)
Removes item from the front of the queue
and returns it.
Issues to be taken care of:
 Queue has been initialized and is not empty.
 Queue has only one element
 Algorithm for deleting an element in a
Queue

 if front = null then // checking if Queue is empty

 print “Queue is empty”
 Else
 if front=rear // if there is only one element
 {
 n=Que[front];
 front=null
 rear=null
 }
 Else
 {
 n=Que[front];
 front=front+1
 }
 Queue underflow

• The condition resulting from trying to remove

an element from an empty queue.
Disadvantages in Array-Queue
Implementations

Array-based implementation is simple

but:
 The size of the queue must be determined when
the queue object is declared.
 Space is wasted if we use less elements.
 Cannot "enqueue" (add) more elements than the
array can hold.
 Variations in Queue

Queues can be implemented in different ways

depending on the requirement of the
program.
Some of the variations are as follows:
 Circular Queues
 Double-ended Queues (also known as Deque)
 Input-restricted Deque
 Output-restricted Deque
 Circular Queue

A circular queue overcomes the drawback of a

standard queue.
In a standard queue the memory space is under-
utilized.
After a dequeue operation (ie., a deletion
operation),
the space occupied by the deleted element is not
allocated to the new element that is added. There
is
wastage of memory space.
This is overcome by connecting the last node (rear
end) of the queue to the front.
CIRCULAR QUEUES
 Double-ended Queues[Deque]

Elements can be added or removed at either

end but not in the middle.
2 variations:
An Input-restricted deque allows insertions at
only one end but allows deletions at both
ends of the list.
An Output-restricted deque allows deletions
at only one end but allows insertions at both
ends of the list.
 Applications of Queues

Queues are used to implement FIFO policy and so

they are used in situations that require FIFO
strategy
Telephone enquiries, Reservation requests etc.
In a multi-user / networking environment when
resources like printers are shared, the request for
a print job by the various computer systems, is put
in a queue and it is on a First-come-first serve basis
that the computers’ requests are processed.
Scheduling of processes in a multiuser environment
– it refers to allocation of CPU time to the processes
 Scheduling

In a multi-user environment, the memory

and CPU of the central computer (Unix/Linux
Server) are shared by the users sitting in the
various terminals.
A queue is maintained in which all the
processes that require the CPU time are
loaded one by one; processed and executed in
the same order.
 Algorithms

Write algorithms for adding and deleting

elements in a Circular Queue.
Write algorithms for counting the elements in
a Circular Queue.
Write algorithms for adding and deleting
elements in a Double-ended Queue.