Data Structures

Unit 3 – Linear Data Structure

By – Dr. Jay B. Teraiya
 ● Array
● Stack
Agenda
● Queue
● Linked List

2
 ● Representation of arrays
● Array
● Sparse matrix and its
● Stack
Till now representation
● Queue
● Storage Structures for arrays
● Linked List
● Applications of arrays

3
 ● Stack definitions and concepts
● Array ● operations on stacks
● Stack ( push, pop, peep, change)
Till now
● Queue ● Polish Expressions and their
● Linked List compilation
● Tower of Hanoi

4
 ● Representation of queue
● Operations on queue ( insert,
● Array delete)
Up Next ● Stack ● Simple Queue
● Queue ● Circular Queue
● Linked List ● Double Ended Queue
● Priority queues
● Applications of Queue

5
 ● It is an ordered group of homogeneous items of
elements.
● Elements may be inserted at one end (the rear of the
queue) and deleted from other end (called the front
of the queue).
Queue / ● The first element to be added will be the first to be
Simple Queue: removed (FIFO: First In, First Out).

6
 ● One way to implement the queue is to have a data
structure where an array is used to store the
elements in the queue.

Array ● And variables called front and rear keeps the location
Implementation of corresponding element in the queue (array).
of the Queue

7
 ● Initialize the Queue

● Insert an item into the Queue

Basic Queue
● Delete an item from the Queue
Operations
● Is the Queue empty?

● Is the Queue full?

8
 ● Initialize the front and rear.

Initialize
Operation

9
 ● Insert an item at the rear position of Queue.

Insert
Operation

10
 ALGORITHM: QINSERT(Q,X)

1. [check for queue overflow]

if REAR == MAX -1
then Write(“queue overflow”)
Return
2. [update pointers]
qInsert(Q,X) if FRONT == -1 and REAR == -1
then SET FRONT = REAR = 0
else SET REAR = REAR + 1
3. [insert element]
Q[REAR] = X
4. [finished]
Return

11
 ● Delete an item from front position of the Queue.

Delete
Operation

12
 ALGORITHM: QDELETE(Q)

1. [check for underflow of the queue]

if FRONT == -1 OR FRONT > REAR
then Write(“queue underflow”)
Return
qDelete(Q) 2. [get front element of the queue]
Value = Q[FRONT]
3. [update pointers]
FRONT = FRONT + 1
4. [finished]
Return Value

13
 ● This operation is to read the front value of the queue
without removing it.

Peek
Operation

14
 ALGORITHM: QPEEK(Q)

1. [check for underflow of the queue]

if FRONT == -1 OR FRONT > REAR
then Write(“queue underflow”)
qPeek(Q) Return
2. [get front element of the queue]
Value = Q[FRONT]
3. [finished]
Return Value

15
 ● This operation is to change the existing value within
the queue.

Change
Operation

16
 ALGORITHM: QCHANGE(Q,POS,VAL)
1. [check for underflow of the queue]
if FRONT == -1 OR FRONT > REAR
then Write(“queue underflow”)
Return
qChange 2. [check for validity of POS and then update value]
(Q,POS,VAL) INDEX = FRONT + POS - 1
if INDEX >= FRONT AND INDEX <= REAR
then Q[INDEX] = VAL
else Write(“Invalid position”)
3. [finished]
Return

17
 ● Implement a queue of size 10 which can store integer
Exercise
values.

18
 ● Consider Simple Queue of size 5.
● Perform below operations:
1. Insert 5 f= r=
2. Insert 6
f= r=
3. Insert 7
Simple Queue 4. delete f= r=

Example 5. Insert 8 f= r=
6. Insert 9
7. delete f= r=

8. Insert 10 f= r=

f= r=

f= r=

19
 ● Circular Queue

Circular
Queue

20
 ● Insert an item at the rear position of Circular Queue.

Insert
Operation

21
 ALGORITHM: CQINSERT(Q,X)
1. [check for queue overflow]
if (FRONT == 0 AND REAR == MAX - 1)
OR (FRONT == REAR + 1)
then Write(“queue overflow”)
Return
2. [update pointers]
cQInsert(Q,X) if FRONT == -1 and REAR == -1
then SET FRONT = REAR = 0
else SET REAR = (REAR +1) % MAX
3. [insert element]
Q[REAR] = X
4. [finished]
Return

22
 ● Delete an item from front position of the Circular
Queue.

Delete
Operation

23
 ALGORITHM: CQDELETE(Q)
1. [check for underflow of the queue]
if FRONT == -1 then Write(“queue underflow”)
Return
2. [get front element of the queue]
cQDelete(Q) Value = Q[FRONT]
3. [update pointers]
if FRONT == REAR then SET FRONT = REAR = -1
else SET FRONT = (FRONT + 1) % MAX
4. [finished]
Return Value

24
 ● This operation is to change the existing value within
the circular queue.

Change
Operation

25
 ALGORITHM: CQCHANGE(Q,POS,VAL)
1. [check for underflow of the queue]
if FRONT = -1 then Write(“queue underflow”)
Return
2. [check for validity of POS and then update value]
INDEX = (FRONT + POS - 1) % MAX
if (FRONT <= REAR AND INDEX >= Q->FRONT
cQChange
AND INDEX <= Q->REAR) then Q[INDEX]
(Q,POS,VAL) = VAL
else if (FRONT > REAR) AND ( (INDEX >= Q->FRONT
AND INDEX < MAX) OR (INDEX >= 0 AND
INDEX <= REAR) ) then Q[INDEX] = VAL
else Write(“Invalid position”)
3. [finished]
Return 26
 ● Implement a circular queue of size 10 which can store
Exercise
integer values.

27
 ● Consider Circular Queue of size 5 and given status:

f=2 r= 3 L M

● Perform below operations:

f= r=
Circular 1. Insert N
2. Insert O f= r=
Queue 3. Insert P
Example 4. delete
f= r=

5. delete f= r=

6. Insert Q f= r=
7. Insert R
f= r=

f= r=

28
 ● DEQUE: Double-Ended Queue

● Deque is sometimes written dequeue, but this use is

DEQUE
generally deprecated in technical literature or
technical writing because dequeue is also a verb
meaning "to remove from a queue".

29
 ● DeQue is a data structure in which elements may be
added to or deleted from the front or the rear.

● DeQue can behave like a queue and like a stack by

using limited functions.
DEQUE

30
 ● This differs from the QUEUE (FIFO), where elements
can only be added to one end and removed from the
other.
● This general data class has some possible sub-types:
DEQUE and 1. Input-restricted deque is one where deletion can be
its sub-types made from both ends, but insertion can only be made
at one end.
2. Output-restricted deque is one where insertion can be
made at both ends, but deletion can be made from
one end only.

31
 ● Insert entire string in the Input-restricted deque.

● Perform delete on both ends and compare those

characters.
DEQUE -
Palindrome
Checker

32
 ● A priority queue is an abstract data type which is like
a regular queue data structure, but where
additionally each element has a "priority" associated
with it.

Priority Queue Priority Queue

A B C D E
Data
Priority P1 P2 P3 P4 P5
FRONT
REAR

● It is possible that element ‘D’ may be deleted before

an element pointed out by FRONT.

33
 ● Rules

1. In a priority queue, an element with high priority is

Priority Queue served before an element with low priority.

2. If two elements have the same priority, they are

served according to their order in the queue.

34
 ● A separate queue for each priority is maintained.
● Example Data:
Data A B C D E F G

Priority 1 2 3 4 3 3 4

Priority Queue :
Array Priority Queue

Representation f= r=
f= r=
f= r=
f= r=

35
 ● Every node in a list will contain Data as well as
Priority and nodes are sorted in descending order of
priority value.

Priority Queue : ● Example Data:

Linked Data A B C D E F G
Representation Priority 1 2 3 4 3 3 4

36
 ● Widely used as waiting lists for single shared
resource like printer, disk, CPU.
● Queues are used as buffers on MP3 players and
Applications portable CD players.
● Computer systems must often provide a “holding
of Queue
area” for messages between two processes, two
programs, or even two systems.
● This holding area is usually called a “buffer” and is
often implemented as a queue.

37
 ● Representation of queue
● Operations on queue ( insert,
● Array delete)
Review ● Stack ● Simple Queue
● Queue ● Circular Queue
● Linked List ● Double Ended Queue
● Priority queues
● Applications of Queue

38
 ● Linked list Understanding and
their Operations
● Array
● Singly Linked List
● Stack
Up Next ● Doubly Linked List
● Queue
● Circular Linked List
● Linked List
● Circular Doubly Linked
● Applications of Linked List

39
Thank
You

40