slide 1: Unit-III
Topics to be covered
Stacks and Queues: Introduction to stacks
applications of stacks
implementation and comparison of stack implementations.
Introduction to queues
applications of queues and implementations
Priority Queues and applications
S. Durga Devi CSECBIT
slide 2: Stacks
Definition - A stack is an ordered collection of homogeneous data
elements where the insertion and deletion takes place at one end
known as TOP.
The stack is also called LAST IN FIRST OUTLIFO
It means: the element which is inserted last must be deleted first
Example
1. pile of plates in cafeteria
2. stack of coins
S. Durga Devi CSECBIT
slide 3: Stack maintains a pointer called top which keeps track of the top
most element in the stack.
Any insertions or deletions should be based upon the value of top.
It works on the basis of LIFO Last in First out.
According to the definition new elements are inserted from top
and the elements are deleted from same end i.e again top.
This suggests that the element inserted most recently can only be
deleted.
In the stack the elements are removed in the reverse order of that
in which they were added to the stack i.e last element inserted is
to be deleted first.
So it is called last in first out.
Stack has structured with two operations
1. push- insertion\ adding elements on to a stack
2. Pop- deletion \ removing element from the stack
S. Durga Devi CSE CBIT
slide 4: Basic operations:
The basic operations are insertion deletion display.
In stacks special terms are given for insert and delete. i.e push
for insert and pop is for delete.
Push: inserting or adding element into the stack is called push.
Pop: deleting or removing element from the stack is called
pop.
S. Durga Devi CSECBIT
slide 5: Elements are inserted in the order as ABCDE
It represents the stack of 5 elements.
The top most element in the stack is E
If we want to delete element E has to be deleted first
S. Durga Devi CSECBIT
slide 6: Pop operation- delete element from the stack
S. Durga Devi CSECBIT
slide 7: Example :-
S. Durga Devi CSECBIT
slide 8: ADT For Stack
ADT for stack
int stack5top
void push
void pop
void display
int size
void isEmpty
void isFull
S. Durga Devi CSECBIT
slide 9: Applications of stacks
Balancing symbols
Parenthesis matching.
Evaluation of postfix expressions.
Infix to prefix conversions.
Infix to postfix conversions.
Implementing function callsRecursion
Web browser history
Undo operations in text editors
Matching tags in HTML and XML
Quick sort.
S. Durga Devi CSECBIT
slide 10: Implementing stack using arrays
Algorithm for inserting element into the stack:
Algorithm push
1. if topSIZE-1
then write ‘stack overflow’
else
2. read item or data
3. top←top+1
4. stacktop← item
5. stop
S. Durga Devi CSECBIT
slide 11: Explanation:
The stack is of size max. This procedure inserts an element
item on to the top of a stack which is represented by an
array stack.
The first step of this algorithm checks for an overflow
condition.
Overflow means inserting element into a stack which is
full.
If the top value reaches to maximum size of the stack then
elements cannot be inserted into the stack i.e. stack is full.
Otherwise top is incremented by one and element is
inserted into the stack.
S. Durga Devi CSECBIT
slide 12: Algorithm to delete elements from the stack:
Algorithm pop
1. if top-1
then write ‘stack underflow’
else
2. item ← stacktop
3. top ← top-1
S. Durga Devi CSECBIT
slide 13: Explanation:
This procedure deletes an element from the stack.
The first step of this algorithm checks for
underflow condition.
If the top value is -1 then stack is empty.
Empty stack is known as underflow.
Takeout the element from the location where the
top is pointing and then decrement top by one.
S. Durga Devi CSECBIT
slide 14: Display of stack:
Printing the contents of stack after push and pop
operations.
Algorithm print
1. if top-1
then write ‘stack empty’
2. Repeat for i ← top to 0
printstacki
3. stop
S. Durga Devi CSECBIT
slide 15: Space complexity
Time complexity of push popsize isEmpty isFull
will take O1.
Limitation in stack using array is that maximum size of the
stack must be pre defined and it cannot be changedfixed.
When trying to add elements in the stack when the stack is
full will rise the exception.
S. Durga Devi CSECBIT
slide 16: Consider size of the stack is 4
Insert following elements ABCD
Representing Stack with Dynamic array
S. Durga Devi CSECBIT
A
A B
A B C
A B C D
A B C D E
Stack is full when E is inserted create a new stack with double size
and copy all the old stack elements to new
stack and named it as old stack
slide 17: Disadvantage of using an array to implement a stack or queue
is the wastage of space.
Implementing stacks as linked lists provides a feasibility on
the number of nodes by dynamically growing stacks as a
linked list is a dynamic data structure.
The stack can grow or shrink as the program demands it to.
A variable top always points to top element of the stack.
top NULL specifies stack is empty.
Representing Stack with Linked List
S. Durga Devi CSECBIT
slide 18: In this representation first node in the list is last
inserted element hence top must points to the first
element on the stack
Last node in the list is the first inserted element in the
stack.
Thus push operation always adds the new element at
front of the list
And pop operation removes the element at front of
the list.
Size of the stack not required.
Test for overflow is not applicable in this case.
S. Durga Devi CSECBIT
slide 19: 10 NULL
1500
1800
1200
1400
20 1400
30 1200
40 1800
50 1500
1100
top
Example:
The following list consists of five cells each of which holds a data object
and a link to another cell.
A variable top holds the address of the first cell in the list.
S. Durga Devi CSECBIT
slide 20: / write a c program to implement stack using linked list /
includestdio.h includemalloc.h includestdlib.h
int push int pop int display
int choiceiitem
struct node
int data
struct node link
topnewptr
main topNULL
printf"\nSelect Menu\n"
while1
printf"\n1.Push \n2.Pop \n3.Display \n4.Exit\n5.Count"
printf"\n\nEnter ur choice: "
scanf"d"choice
switchchoice
case 1: push break
case 2: pop break
case 3: display break
case 4: exit0
case 5: count break
default: printf"\nWrong choice"
/ end of switch /
/ end of while /
/ end of main /
S. Durga Devi CSECBIT
slide 21: int push
newmallocsizeofstruct node
printf"\nEnter the item: "
scanf"d"item
new-dataitem
iftopNULL
new-linkNULL
else
new-linktop
topnew
return
/ end of insertion /
int pop
iftop NULL
printf"\n\nStack is empty"
return
//if
else
printf"\n\nThe deleted element
is: d"top-data
toptop-link
return
/ end of pop /
S. Durga Devi CSECBIT
slide 22: int display
ptrtop
iftop NULL
printf"\nThe list is empty"
return
printf"\nThe elements in the stact are: "
whileptrNULL
printf"\n d"ptr-data
ptrptr-link
/ end of while /
return
/ end of display /
int count
int count1
ptrtop
iftop NULL
printf"\nThe list is empty"
return
whileptr-linkNULL
++count
ptrptr-link
printf"\n\nThe number of elements in
the stack are: d"count
return
/ end of count /
S. Durga Devi CSECBIT
slide 23: Applications of stacks
Balancing symbols ””
Evaluation of postfix expressions.
Infix to postfix conversions.
Infix to prefix conversions.
Implementing function callsRecursion
Web browser history
Undo operations in text editors
Matching tags in HTML and XML
Quick sort.
S. Durga Devi CSECBIT
slide 24: 1.Parenthesis matching
The objective of this function is to check the
matching of parenthesis in an expression
i.e
In an expression the no of left parenthesis must be
equal to no: of right parenthesis.
Ex: A+BC
This is a valid expression because in this no of left
parenthesis 2 no: of right parenthesis 2.
S. Durga Devi CSECBIT
slide 25: Conversion of expressions
Arithmetic expressions can be represented in three ways:
Infix notation
Prefix notation
Postfix notation
1. Infix notation- In which operator should be placed in between the two operands.
Example- A+B C-D EF G/H.
2. Prefix notation polish notation-
• Operator preceded by the operand is called prefix notation
Examples
+AB -CD EF \GH.
3. Postfix notationreverse polish notation or suffix notation-
• Operator should be placed after operands.
AB+ CD- EF GH\
S. Durga Devi CSECBIT
slide 26: Notations – Conversions
Consider the infix expression: 2 + 3 5 – 7 / 9
Let us insert implicit parentheses
2 + 3 5 – 7 / 9
Transfer the operators to the beginning of parentheses
+ 2 / 3 – 5 7 9
Remove the parentheses: + 2 / 3 – 5 7 9
This is the equivalent prefix expression.
Transfer the operators to the end of parentheses
2 3 5 7 – 9 / +
Remove the parentheses: 2 3 5 7 – 9 / +
This is the equivalent postfix expression.
S. Durga Devi CSECBIT
slide 27: Examples
Infix
Expression
Prefix
Expression
Postfix
Expression
2 + 3 + 2 3 2 3 +
2 + 3 5 + 2 3 5 2 3 5 +
2 + 3 5 + 2 3 5 2 3 + 5
2 3 – 5 + 9
– 2 3 +
5 9
2 3 5 9 +
–
S. Durga Devi CSECBIT
slide 28: Infix to post fixRPN Conversion
Algorithm to convert infix expression to postfix expressionRPN:
1. Declare a stack and postfix arrayoutput : postfix expression
2. Repeat the following steps until the end of the infix expression is reached.
1. Get input token constant variable arithmetic operator left
parenthesis right parenthesis in the infix expression.
2. If the token is
2.1 A left parenthesis: Push it onto the stack.
2.2 A right parenthesis:
2.2.1 Pop the stack elements and add to postfix array until a left
parenthesis is on the top of the stack.
2.2.2 Pop the left parenthesis also but do not add to postfix array
2.3 An operator:
2.3.1 While the stack is nonempty and token has lower or equal
priority than stack top element pop and add to postfix array.
2.3.2 Push token onto the stack.
2.4 An operand: add to postfix array
3. When the end of the infix expression is reached pop the stack elements
and add to postfix array until the stack is empty.
Note: Left parenthesis in the stack has lowest priority
S. Durga Devi CSECBIT
slide 29: Note
• the lower precedence operator never placed on
top of the higher precedence.
• A-BD/E
S. Durga Devi CSECBIT
slide 30: Operator Precedence
S. Durga Devi CSECBIT
slide 31: Infix expression- A+BC-DE/F
Infix Stack Post fix
Empty
A A
+ + A
B + AB
Empty AB+
AB+
C AB+C
- - AB+C
- AB+C
D - AB+CD
- AB+CD
E - AB+CDE
- AB+CDE
/ -/ AB+CDE
F -/ AB+CDEF
Empty
AB+CDEF/-
S. Durga Devi CSE
slide 32: Postfix reverse polish notation expression
evaluation
• Algorithm
1.Scan expression from left to right and repeat steps 2 and 3 for each element
of expression.
2. If an operand is encountered push it on to stack.
3.If an operator op1 is encountered then
3.1 remove the top two elements of stack where A is the top and B is the next
top element.
3.2 evaluate B op1 A
3.3 push the result back on to the stack.
4. set the top value on stack.
5. stop
S. Durga Devi CSECBIT
slide 33: Evaluate the expression
•
Postfix:- 562+124/-
Symbol scanned stack content
5 5
6 5 6
2 5 6 2
+ 5 8
40
12 40 12
4 40 12 4
/ 40 3
- 40-3
37
S. Durga Devi CSECBIT
slide 34: Convert infix to postfix expression
1. A-BD/E
2. A+BD/E-F+G
3. AB+D/E-FG+H/K
4. A+BDE-F
5. A-B/D+EF
6. A+B/DE-FG
7. 12/7-3+21+5
8. 5+32-8/43+6
9. 6+23+9/3-45
10. 6+232-45
Evaluate the postfix expression
1. 53+2697-/-
2. 35+64-41-2+
3. 31+2741-2+5.-
S. Durga Devi CSECBIT
slide 35: includestdio.h
includectype.h
includestring.h
int prioritychar c
int pushchar c
int pop
static char str30
int top-1
void main
char in30post30ch
int ijl
printf"enter the string"
getsin
lstrlenin
Write a C program to convert infix to postfix evaluation
S. Durga Devi CSECBIT
slide 36: fori0j0ili++
ifisalphaini||isdigitini
postj++ini
else
ifini
pushini
else ifini
whilechpop
postj++ch
else
whilepriorityiniprioritystrtop
postj++pop
pushini
whiletop-1
postj++pop
postj\0
printf"\n equivalent infix to postfix
is:s"post
int priority char c
switchc
case+:
case-: return 1
case:
case/:
return 2
case:return 3
case :return 4
return 0
int pushchar c
str++topc
pop
returnstrtop--
S. Durga Devi CSECBIT
slide 37: A queue is a linear data structure in which insertion take place from one end called rear
end and deletions take place from other end called front end i.e insertion and deletion
take place from different ends.
The principle used to in queue is FIFO.First In First Out
FIFO- the element which is inserted First must be deleted First.
In a queue there are two variables one is the rear and other one is front.
the element must be always added at rear end and removed from the front.
Basic operations on queue:
The operations that can be performed on queue are
Insertion\ Enqueue
Deletion\ Dequeue
Display
Queues
Front
rear
S. Durga Devi CSECBIT
slide 38: Bus Stop
Queue
Bus
Stop
front
rear
rear rear rear rear
S. Durga Devi CSECBIT
slide 39: Bus Stop Queue
Bus
Stop
front
rear
rear rear
S. Durga Devi CSECBIT
slide 40: Bus Stop Queue
Bus
Stop
front
rear
rear
S. Durga Devi CSECBIT
slide 41: Bus Stop Queue
Bus
Stop
front
rear
rear
S. Durga Devi CSECBIT
slide 42: Front Rear
Front
Rear
Front
Rear
•A queue is like a line of people waiting for
• a bank teller. The queue has a front and a rear.
New people must enter the queue at the rear.
When an item is taken from the queue it always comes from the front.
S. Durga Devi CSECBIT
slide 43: Queue ADT
• basic queue operations:
– add enqueue: Add an element to the back.
– remove dequeue: Remove the front element.
– peek: Examine the element at the front.
– isEmpty: check whether queue is empty or not
– isFull : whether queue is full or not
S. Durga Devi CSECBIT
slide 44: • Different types of queues
1. Linear queue or queue
2. Circular queue
3. Doubly ended queue dequeue
4. Priority queue
S. Durga Devi CSECBIT
slide 45: Working of a linear queue using an array
i Initially frontrear -1. It indicates queue is empty.
0 1 2 3 4
frontrear-1
0 1 2 3 4
ii Add 10
10
front rear
0 2 3 4
iii Add 20
front rear
1
10
20
0 2 3 4
iv Add 30
front rear
1
10 20 30
0 2 3 4
v Add 40
front rear
1
10
20 30 40
S. Durga Devi CSECBIT
slide 46: 0 2 3 4
vi Add 50
front rear
1
10 20 30 40 50
0 2 3 4
vii Add 60 overflow
front rear
1
10 20 30 40 50
0 2 3 4
viii delete 10 is removed
front rear
1
20 30 40 50
0
front rear
1
30 40 50
ix delete 20 is removed
2
3
4
S. Durga Devi CSECBIT
slide 47: 0
front rear
1
40 50
x delete 30 is removed
2
3
4
0
front rear
1
50
xi delete 40 is removed
2
3
4
0
frontrear-1
1
ix delete underflow
2
3
4 0
frontrear-1
1
xii delete 50 is removed
2
3
4
S. Durga Devi CSECBIT
slide 48: Implementation of queue using array
Algorithm insert
1. If rear ≥ size-1
then write ‘overflow’
2. Read item
3. rear← rear + 1
4. queuerear← item
5. Iffront-1
6. front++
7. stop
Explanation:
This procedure adds an element item to the
queue.
First it checks for an overflow condition.
If the rear value reaches or exceeds size of the
queue
then elements cannot be inserted into the queue.
ie. Overflow.
Whenever element is inserted into the queue
rear is increment by one
and place the element in the location
where rear is pointing.
S. Durga Devi CSECBIT
slide 49: Algorithm to delete element from the queue
Algorithm delete
1. If front -1or front rear
then write ‘queue underflow’
item ← queue front
2. front ← front + 1
Explanation:
This procedure deletes an element from the queue.
The first step of this algorithm checks for underflow condition.
If the front value is -1or greater than rear then queue is empty.
Take out the element from the location where the front is pointing and
store it in the variable then increment front by one.
S. Durga Devi CSECBIT
slide 50: Algorithm to display elements in a queue
1. iffront-1||frontrear
1.1 print statck is Underflow
2. Else
2.1 repeat for i-front to rear
2.2. print queuei
Drawback in queue
In a queue when the rear pointer reaches to the end of the queue
insertion would be denied even if room is available at the front
one way to remove this is using the circular queue
S. Durga Devi CSECBIT
slide 51: Program: implementation of queue using array
include stdio.h
define size 4
void insertion
void deletion
void display
int front-1rear-1itemchoicequeuesize
void main
clrscr
while1
printf"\n MENU \n 1. INSERTION\n 2. DELETION\n
3.TRAVERSE\n 4. EXIT\n"
printf"enter your choice:"
scanf"d"choice
switchchoice
case 1:insertion
break
case 2:deletion
break
case 3:display
break
case 4:exit
default:printf" wrong choice \n"
S. Durga Devi CSECBIT
slide 52: void insertion
ifrearsize-1
printf" queue is full \n"
else
printf"enter item into queue:"
scanf"d"item
rear++
queuerearitem
iffront-1
front++
void deletion
iffront-1||frontrear
printf" queue is empty \n"
else
itemqueuefront
front++
printf"the deleted item from queue is
d\n"item
void display
int i
iffront-1||frontrear
printf" queue is empty \n"
else
printf"\n elements in queue:- "
forifrontireari++
printf"d "queuei
S. Durga Devi CSECBIT
slide 53: EMPTY QUEUE
Circular queues
Q0
Q1
Q2 Q3 QN
Delete element 5
S. Durga Devi CSECBIT
slide 54: rear
S. Durga Devi CSECBIT
slide 55: • How to test whether circular queue is empty or full
• The circular q is controlled by the MOD operation.
• Circular queue is empty
when front -1
rear-1
Circular queue is full
front rear+1 SIZE
S. Durga Devi CSECBIT
slide 56: Implementation of circular queue using array
• Algorithm for insertion
1.iffront 0 rear SIZE-1 || front rear+1size
2.printf"Queue Overflow \n"
return
3.if front -1 /If queue is empty /
3.1 front 0
3.2 rear 0
4.else
5.ifrear SIZE-1/rear is at last position of queue /
6.rear 0
7. else
8.rear rear+1
9.Read item
10.cqrear item
11.end
S. Durga Devi CSECBIT
slide 57: • Algorithm for deletion
• 1.if front -1
2.printf"Queue Underflow\n"
return
3.iffront rear / queue has only one element /
3.1front -1
3.2rear-1
4.else
5.iffront SIZE-1
• front 0
6.else
7.front front+1
8.Stop
S. Durga Devi CSECBIT
slide 58: int insert
int item
iffront 0 rear SIZE-1 || front rear+1
printf"Queue Overflow \n"
return
if front -1 /If queue is empty /
front 0
rear 0
else
ifrear SIZE-1/rear is at last position of queue /
rear 0
else
rear rear+1
printf"Input the element for insertion in queue : "
scanf"d" item
cqrear item
printf"the element d at d position and
frontdreard\n"cqrearrearfrontrear
return
/End of insert/
S. Durga Devi CSECBIT
slide 59: int del
if front -1
printf"Queue Underflow\n"
return
printf"Element deleted from queue is :
d\n"cqfront
iffront rear / queue has only one
element /
front -1
rear-1
else
iffront SIZE-1
front 0
else
front front+1
printf"frontdreard\n"frontrear
return
/End of del /
Deletion
S. Durga Devi CSECBIT
slide 60: display
int display
int front_pos frontrear_pos rear
iffront -1
printf"Queue is empty\n"
Return
printf"Queue elements :\n"
if front_pos rear_pos
whilefront_pos rear_pos
printf"d "cqfront_pos
front_pos++
else
whilefront_pos SIZE-1
printf"d "cqfront_pos
front_pos++
front_pos 0
whilefront_pos rear_pos
printf"d "cqfront_pos
front_pos++/End of else /
printf"\n"
return
/End of display /
S. Durga Devi CSECBIT
slide 61: Applications of queues
There are several applications of queues in computer science.
1. Implement various aspects of operating systems.
2. CPU scheduling in Multiprogramming environment- single CPU has to serve
more than one program simultaneously.
3. Round Robin CPU scheduling algorithm.
4. In operating System maintains a queue of processes that are ready to process or
that are waiting for particular event to occur.
5. Computer system maintains a buffer and is implemented as a queue.
6. Printer
7. Call waiting when you are attending other call
8. a file server in a computer network handles file access request from many clients
throughout the network. Servers have a limited capacity to service request from
clients. when that capacity is exceeded client requests wait in queues
9. This type of data structure is used in time sharing systems where many user jobs will
be waiting in the system queue for processing. These jobs may request the
services of CPU main memory or external devices such as printer.
10. Radix sort implemented using queue.
S. Durga Devi CSECBIT
slide 62: Queues in computer science
• Operating systems:
– queue of print jobs to send to the printer
– queue of programs / processes to be run
– queue of network data packets to send
• Programming:
– modeling a line of customers or clients
– storing a queue of computations to be performed in
order
• Real world examples:
– people on an escalator or waiting in a line
– cars at a gas station or on an assembly line
S. Durga Devi CSECBIT
slide 63: Radix sort
• This algorithm sorts the elements from least significant digit to
most significant digit
• As you know the numbers are formed with digits 0 to 9 so we need
10 buckets labelled 0 to 9 to sort the unsorted numbers.
• First find the largest number in the given unsorted elements and
count its digits.
• If largest number has n digits the algorithm could be completed in
n number of passes to sort the numbers in specified order.
• Number of passes bucket sort stages will depend on the number
of digits in the maximum value
slide 64: Example : 100 5435510243102875
0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
Take buckets numbered from 0 to 9
Take first number 100 has 0 in the 1
st
place so put that number in 0
th
bucket
54 has 4 in the 1
st
place so put that number in 4
th
bucket
0 1 2 3 4 5 6 7
8 9
slide 65: 0 1 2 3 4 5 6 7
8 9
0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
100
PASS-1
slide 66: 0 1 2 3 4 5 6 7
8 9
0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
100 54
slide 67: 0 1 2 3 4 5 6 7
8 9
0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
100 54
355
slide 68: 0 1 2 3 4 5 6 7
8 9
0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
100 54
355
102
slide 69: 0 1 2 3 4 5 6 7
8 9
0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
100 54
355
102
43
slide 70: 0 1 2 3 4 5 6 7
8 9
0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
100 54
355
102
43
10
slide 71: 0 1 2 3 4 5 6 7
8 9
0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
100 54
355
102
43
10
287
slide 72: 0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
0 1 2 3 4 5 6 7
8 9
100 54
355
102
43
10
287
5
Take out the elements from the buckets starts from 0
th
bucket to 9
th
bucket
Place it in an array
slide 73: 0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
0 1 2 3 4 5 6 7
8 9
100 54
355
102
43
10
287
5
Take out the elements from the buckets starts from 0
th
bucket to 9
th
bucket
Place it in an array
0 1 2 3 4 5 6 7
100
slide 74: 0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
0 1 2 3 4 5 6 7
8 9
54
355
102
43
10
287
5
Take out the elements from the buckets starts from 0
th
bucket to 9
th
bucket
Place it in an array
0 1 2 3 4 5 6 7
100
slide 75: 0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
0 1 2 3 4 5 6 7
8 9
54
355
102
43
287
5
Take out the elements from the buckets starts from 0
th
bucket to 9
th
bucket
Place it in an array
0 1 2 3 4 5 6 7
100 10
slide 76: 0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
0 1 2 3 4 5 6 7
8 9
54
355
102
43
287
5
Take out the elements from the buckets starts from 0
th
bucket to 9
th
bucket
Place it in an array
0 1 2 3 4 5 6 7
100 10 102
slide 77: 0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
0 1 2 3 4 5 6 7
8 9
54
355
43
287
5
Take out the elements from the buckets starts from 0
th
bucket to 9
th
bucket
Place it in an array
0 1 2 3 4 5 6 7
100 10 102
slide 78: 0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
0 1 2 3 4 5 6 7
8 9
54
355
43
287
5
Take out the elements from the buckets starts from 0
th
bucket to 9
th
bucket
Place it in an array
0 1 2 3 4 5 6 7
100 10 102 43
slide 79: 0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
0 1 2 3 4 5 6 7
8 9
54
355
287
5
Take out the elements from the buckets starts from 0
th
bucket to 9
th
bucket
Place it in an array
0 1 2 3 4 5 6 7
100 10 102 43
slide 80: 0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
0 1 2 3 4 5 6 7
8 9
54
355
287
5
Take out the elements from the buckets starts from 0
th
bucket to 9
th
bucket
Place it in an array
0 1 2 3 4 5 6 7
100 10 102 43 54
slide 81: 0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
0 1 2 3 4 5 6 7
8 9
355
287
5
Take out the elements from the buckets starts from 0
th
bucket to 9
th
bucket
Place it in an array
0 1 2 3 4 5 6 7
100 10 102 43 54
slide 82: 0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
0 1 2 3 4 5 6 7
8 9
355
287
5
Take out the elements from the buckets starts from 0
th
bucket to 9
th
bucket
Place it in an array
0 1 2 3 4 5 6 7
100 10 102 43 54 355
slide 83: 0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
0 1 2 3 4 5 6 7
8 9
287
5
Take out the elements from the buckets starts from 0
th
bucket to 9
th
bucket
Place it in an array
0 1 2 3 4 5 6 7
100 10 102 43 54 355
slide 84: 0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
0 1 2 3 4 5 6 7
8 9
287
5
Take out the elements from the buckets starts from 0
th
bucket to 9
th
bucket
Place it in an array
0 1 2 3 4 5 6 7
100 10 102 43 54 355 5
slide 85: 0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
0 1 2 3 4 5 6 7
8 9
287
Take out the elements from the buckets starts from 0
th
bucket to 9
th
bucket
Place it in an array
0 1 2 3 4 5 6 7
100 10 102 43 54 355 5
slide 86: 0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
0 1 2 3 4 5 6 7
8 9
287
Take out the elements from the buckets starts from 0
th
bucket to 9
th
bucket
Place it in an array
0 1 2 3 4 5 6 7
100 10 102 43 54 355 5 287
slide 87: 0 1 2 3 4 5 6 7
100 54 355 102 43 10 287 5
0 1 2 3 4 5 6 7
8 9
Take out the elements from the buckets starts from 0
th
bucket to 9
th
bucket
Place it in an array
0 1 2 3 4 5 6 7
100 10 102 43 54 355 5 287
PASS-1 completed
slide 88: 0 1 2 3 4 5 6 7
100 10 102 43 54 355 5 287
PASS-2
consider ten’s place and place it into its corresponding bucket number
100 has 0 in its ten’s place so put 100 in 0
th
bucket
0 1 2 3 4 5 6 7
8 9
100
slide 89: 0 1 2 3 4 5 6 7
100 10 102 43 54 355 5 287
0 1 2 3 4 5 6 7
8 9
100 10
slide 90: 0 1 2 3 4 5 6 7
100 10 102 43 54 355 5 287
0 1 2 3 4 5 6 7
8 9
100 10
102
slide 91: 0 1 2 3 4 5 6 7
100 10 102 43 54 355 5 287
0 1 2 3 4 5 6 7
8 9
100 10
102
43
slide 92: 0 1 2 3 4 5 6 7
100 10 102 43 54 355 5 287
0 1 2 3 4 5 6 7
8 9
100 10
102
43
54
slide 93: 0 1 2 3 4 5 6 7
100 10 102 43 54 355 5 287
0 1 2 3 4 5 6 7
8 9
100 10
102
43
54
355
slide 94: 0 1 2 3 4 5 6 7
100 10 102 43 54 355 5 287
0 1 2 3 4 5 6 7
8 9
100 10
102
43
54
355
05
slide 95: 0 1 2 3 4 5 6 7
100 10 102 43 54 355 5 287
0 1 2 3 4 5 6 7
8 9
100 10
102
43
54
355
05
287
slide 96: 0 1 2 3 4 5 6 7
100 10 102 43 54 355 5 287
0 1 2 3 4 5 6 7
8 9
100 10
102
43
54
355
05
287
0 1 2 3 4 5 6 7
100 102 05 10 43 54 355 287
PASS-2 completed
slide 97: 0 1 2 3 4 5 6 7
8 9
0 1 2 3 4 5 6 7
100 102 05 10 43 54 355 287
PASS-3
Now consider 100
th
place digit and put it in corresponding bucket
100 number has 1 in its hundred’s place so put it in bucket 1
100
slide 98: 0 1 2 3 4 5 6 7
8 9
0 1 2 3 4 5 6 7
100 102 05 10 43 54 355 287
100
102
slide 99: 0 1 2 3 4 5 6 7
8 9
0 1 2 3 4 5 6 7
100 102 05 10 43 54 355 287
100
102
005
slide 100: 0 1 2 3 4 5 6 7
8 9
0 1 2 3 4 5 6 7
100 102 05 10 43 54 355 287
100
102
005
010
slide 101: 0 1 2 3 4 5 6 7
8 9
0 1 2 3 4 5 6 7
100 102 05 10 43 54 355 287
100
102
005
010
043
slide 102: 0 1 2 3 4 5 6 7
8 9
0 1 2 3 4 5 6 7
100 102 05 10 43 54 355 287
100
102
005
010
043
054
slide 103: 0 1 2 3 4 5 6 7
8 9
0 1 2 3 4 5 6 7
100 102 05 10 43 54 355 287
100
102
005
010
043
054
355
slide 104: 0 1 2 3 4 5 6 7
8 9
0 1 2 3 4 5 6 7
100 102 05 10 43 54 355 287
100
102
005
010
043
054
355
287
slide 105: 0 1 2 3 4 5 6 7
8 9
0 1 2 3 4 5 6 7
100 102 05 10 43 54 355 287
100
102
005
010
043
054
355
287
0 1 2 3 4 5 6 7
5 10 43 54 100 102 287 355
slide 106: Exercise use Radix sort
12 58 37 64 52 36 99 63 18 9 20 88 47
slide 107: Circular queue using array
includestdio.h
includestdlib.h
define SIZE 4
int insert
int del
int display
int cqSIZE
int front -1
int rear -1
main
while1
printf"1.Insert\n"
printf"2.Delete\n"
printf"3.Display\n"
printf"4.Quit\n"
printf"Enter your choice : "
scanf"d"choice
switchchoice
case 1 :
insert
break
case 2 :
del
break
case 3:
display
break
case 4:
exit0
default:
printf"Wrong choice\n"
/End of switch/
/End of while /
/End of main/
slide 108: int insert
int item
iffront 0 rear SIZE-1 || front rear+1
printf"Queue Overflow \n"
return
if front -1 /If queue is empty /
front 0
rear 0
else
ifrear SIZE-1/rear is at last position of queue /
rear 0
else
rear rear+1
printf"Input the element for insertion in queue : "
scanf"d" item
cqrear item
printf"the element d at d position and
frontdreard\n"cqrearrearfrontrear
return
/End of insert/
slide 109: example
1.encqA
2.encqB
3.encqc
4. Encq D
5.Decq
6.encqE
7. Decq
8.encq F
9.Decq
10. Decq
11.Decq
12. Decq
slide 110: Dictionaries
6
9 2
4 1
8
slide 111: Dictionary ADT
• The dictionary ADT models a
searchable collection of key-
element entries
• The main operations of a
dictionary are searching inserting
and deleting items
• Multiple items with the same key
are allowed
• Applications:
– word-definition pairs
– credit card authorizations
– DNS mapping of host names e.g.
datastructures.net to internet IP
addresses e.g. 128.148.34.101
• Dictionary ADT methods:
– findk: if the dictionary has
an entry with key k returns
it else returns null
– findAllk: returns an
iterator of all entries with
key k
– insertk o: inserts and
returns the entry k o
– removee: remove the
entry e from the dictionary
– entries: returns an iterator
of the entries in the
dictionary
– size isEmpty
slide 112: Example
Operation Output Dictionary
insert5A 5A 5A
insert7B 7B 5A7B
insert2C 2C 5A7B2C
insert8D 8D 5A7B2C8D
insert2E 2E 5A7B2C8D2E
find7 7B 5A7B2C8D2E
find4 null 5A7B2C8D2E
find2 2C 5A7B2C8D2E
findAll2 2C2E 5A7B2C8D2E
size 5 5A7B2C8D2E
removefind5 5A 7B2C8D2E
find5 null 7B2C8D2E
slide 113: The findAllk Algorithm
Algorithm findAllk:
Input: A key k
Output: An iterator of entries with key equal to k
Create an initially-empty list L
B D.entries
while B.hasNext do
e B.next
if e.key k then
L.insertLaste
return L.elements
slide 114: The insert and remove Methods
Algorithm insertkv:
Input: A key k and value v
Output: The entry kv added to D
Create a new entry e kv
S.insertLaste S is unordered
return e
Algorithm removee:
Input: An entry e
Output: The removed entry e or null if e was not in D
We don’t assume here that e stores its location in S
B S.positions
while B.hasNext do
p B.next
if p.element e then
S.removep
return e
return null there is no entry e in D
slide 115: A List-Based Dictionary
• A log file or audit trail is a dictionary implemented by means of an
unsorted sequence
– We store the items of the dictionary in a sequence based on a doubly-
linked list or array in arbitrary order
• Performance:
– insert takes O1 time since we can insert the new item at the beginning
or at the end of the sequence
– find and remove take On time since in the worst case the item is not
found we traverse the entire sequence to look for an item with the given
key
• The log file is effective only for dictionaries of small size or for
dictionaries on which insertions are the most common operations
while searches and removals are rarely performed e.g. historical
record of logins to a workstation
slide 116: Hash Table Implementation
• We can also create a hash-table dictionary
implementation.
• If we use separate chaining to handle
collisions then each operation can be
delegated to a list-based dictionary stored at
each hash table cell.
slide 117: Linear\sequential Search
• linear\sequential search of a list/array begins
at the beginning of the list/array and
continues until the item is found or the entire
list/array has been searched
slide 118: Example: Successful Linear Search
slide 119: Example: Failed Linear Search
slide 120: Linear Search Implementation using non recursive method
include stdio.h
define SIZE 8
int linear_searchint a int target int size
void read_arrayint a int size
int mainvoid
int xSIZE target
int index
read_arrayx SIZE
printf"Enter Element to search for: "
scanf"d" target
index linear_searchx target SIZE
if index 0
printf"Target was found at index d\n" index
else
printf"Sorry target item was not found"
return 0
void read_array int a int size
int i
printf"Enter d integer numbers separated by
blanks\n " size
for i 0 i size ++i
scanf"d" ai
/ Searches for an target in an array using
Linear search
Returns index of target or -1 if not found /
int linear_searchint a int target int size
int iloc0
fori0iSIZEi++
iftargetai
return ++loc
else
loc++
return 0
slide 121: / C program that use recursive function to perform the Linear
Search for a Key value in a given list of integers/
includestdio.h define SIZE 5
int linearSearchint array int index int length int value
void main
int listSIZEelementitargetindex0
printf"\n\nEnter d integer elements: "SIZE
fori 0 i SIZE i++
scanf"d"listi
printf"\nEnter target element to be searched: "
scanf"d"target
element linearSearch listindexSIZEtarget
if element -1
printf"\nElement is found at d location "element+1
else
printf"Element is not found..."
slide 122: int linearSearchint array int indexint length int value
ifindexlength-1
return -1
else
if arrayindexvalue
return index
else
return linearSearch arrayindex+1length
value
slide 123: Search Algorithms
-All the array elements must be visited if search fails.
slide 124: Efficiency of Linear Search
• The efficiency of an algorithm is measured using the big O notation
O stands for order of
• Big O Notation
– Indicates the worst-case run time maximum time taken for
execution for an algorithm
– In other words how hard an algorithm has to work to solve a
problem
For Linear Search algorithm :On
slide 125: Binary Search: The search starts at middle of a sorted array if middle
is equal to target element search is successful otherwise it determines
which half to be continue to search on that basis.
The algorithm starts searching with the mid element.
midfirst + last/2
If the item is equal to mid then search is successful.
If the item is less than the mid element it starts over searching the first
half of the list.
If the item is greater than the mid element the search starts over the
second half of the list.
It then continues halving the list until the item is found.
Each iteration eliminates half of the remaining elements.
It is faster than the linear search.
It works only on SORTED array.
Thus there is a performance penalty for sorting the array.
The Time complexity of Binary Search is Olog N.
slide 127: / C program that use recursive function to perform the Binary Search
for a Key value in a given list of integers/
include stdio.h define SIZE 8
int binary_search int list int low int high int target
void main
int listSIZE target indexi
printf"Enter d elements in ascending or descending order: "SIZE
fori0iSIZEi++
scanf"d"listi
printf"Enter an element that is to be searched: "
scanf"d" target
index binary_searchlist 0 SIZE-1 target
if index -1
printf"\nTarget was found at index: d " index+1
else
printf"Sorry target item was not found"
slide 128: int binary_search int list int low int high int target
int middle
if low high
return -1
middle low + high/2
if listmiddle target
return middle
else
if listmiddle target
return binary_searchlistmiddle+1hightarget
else
return binary_searchlistlowmiddle-1target
slide 129: / C program that use non recursive function to perform the Binary
Search for a Key value in a given list of integers/
include stdio.h
define SIZE 8
int binary_search int list int low int high int target
void main
int listSIZE target indexi
printf“\nenter the array elements”
fori0iSIZEi++
scanf"d"listi
printf“\n enter the target element"
scanf"d" target
index binary_searchlist 0 SIZE-1 target
if index -1
printf"\nelement atlocation d " index+1
else
printf"Sorry target item was not found"
getch
slide 130: int binary_searchint aint low int high int target
int middle
whilelowhigh
middlelow+high/2
iftargetamiddle
highmiddle-1
else iftargetamiddle
lowmiddle+1
else
return middle
//while
return -1
//binary_search
slide 131: Static Hashing
slide 132: Why hashing
• Internet has grown to millions of users and terabytes of data every
data.
• It is impossible to find anything in the internet unless we develop a
new data structure to store and access the data very quickly.
• The amount of time required to look up an element in an array or
linked list is either Ologn or On based on the list is sorted or not.
• New data structure called Hashing used to store and retrieve any
entry with constant time O1.
• This technique is irrelevant to size of the list and order .
• To increase the search efficiency the items to be stored in such a way
as to make it easy to find them later .
slide 133: Hashing
- Hashing is a technique used to generate key where an element is to
be inserted or to be located from.
• Hash Table
- hash table is a data structure to store and retrieve data very fast.
- hash table consist of key and its value.
- Each location in the hash table is called cell or bucket.
- hash table is implemented using array.
- An element is accessed very fast if we know the key or its index.
Example- to store the Student record in hash table Student rollno is used
as a key
slide 134: Hash Function
- to map the key value into its corresponding index in hash table hash
function is used.
A hash function h transforms a key into an index in a hash table T0…m-1:
Where m is size of hash table.
-Use hash function to compute the index in the hash table for the given
key value.
-Hash function returns integer value which give the index value in the
hash table.
slide 135: Types of hash functions
1. Division method
2. Mid square
3. Digit folding
slide 136: 1. Division method
hkey recordM
where M is size of the hash table
Example:
store following records in hash table 34 20 67 8 23.
M is 10
use hash function to map them in hash table
0 20
1
2
3 23
4 34
5
6
7 67
8 8
9
3410 4
20100
67107
8108
23103
slide 137: Consider the following elements to be placed in the hash table of size 10
37904522174955
0
1
2
3
4
5
6
7
8
9 49
37
45
90
22
H
1
3737107
H
1
9090100
H
1
4545105
H
1
2222102
H
1
1717107
H
1
4949109
H
1
5555105
In above example 17 and 55 are hashed to
same location this condition is called collision
slide 138: 2. Mid square
- Square the key value and the middle or mid part of the result is used
as index.
- Example to place a record 3111 then
- Square of 3111 9678321
- If the hash table size is 1000 then consider the middle 3 digits 783.
K 3205 7148
k
2
10272025 51093904
Hk 72 93
slide 139: 3. Folding method
- Key value is divided into parts and add them
yields required hash address.
Key 3205 7148
Hkey 32+0537 71+4819
Note- the leading digit 1 in H7148 is ignored.
slide 140: Collision resolution techniques
• Two or more keys are mapping to same location in the hash table is
called collision.
Collision resolution techniques
• They are two broad ways of collision resolution techniques
1. Separate chaining: an array of linked list representation
2. Open addressing: array based implementation
i Linear probing linear search
ii Quadratic probing nonlinear search
iii Double hashing uses two hash functions
slide 141: Separate chaining
• Hash table is implemented as array of linked list.
• All the records which are mapped to same hash address are lined together to form a linked list.
• Example: Load the keys 23 13 21 14 7 8 and 15 in this order in a hash table of size 7 using separate chaining with the hash function: hkey key 7
h23 23 7 2
h13 13 7 6
h21 21 7 0
h14 14 7 0 collision
h7 7 7 0 collision
h8 8 7 1
h15 15 7 1 collision
slide 142: Linear probing linear search
• Idea is that when the collision occurs find the next available slot in
the hash table i.e probing
• The process wraps around to the beginning of the table
• Example 89 18 49 58 9 and hash table size is 10
0 1 2 3 4 5 6 7 8 9
89 18 49
58 9
89109
18108
49109
58108
9109
slide 143: 3. Quadratic probing
- It operates by taking hash value and adding successive values of an arbitrary
quadratic polynomial.
- Uses following formula
H
i
key Hashvalue+i
2
m
Where
m may be table size or any prime number
slide 144: Ex- 3799552211 174087
0 1 2 3 4 5 6 7 8 9
37107
37
99109
99
55105
55
22102
22
11101
11
17107 but already occupied
Consider i0 then
17+0
2
107
17+1
2
108
17
40100
40
87107 occupied
87+1
2
108 occupied
87+2
2
101 occupied
87+3
2
106
87
slide 145: 4. Double hashing
- Second hash function is applied when a collision is occurred.
- the resultant of second hash function is to get the number of positions from the
point of collision to insert.
H
1
key keyvaluetablesize
H
2
key M-key M
Where
M is prime number smaller than table size.
slide 146: Ex- 37904522174955
0 1 2 3 4 5 6 7 8 9
H
1
3737107
37
H
1
9090100
90
H
1
4545105
45
H
1
2222102
17
H
1
1717107
H
2
177-1774
Move 4 locations from collision
H
1
5555105
H
2
557-5571
Move one location from collision
H
1
4949109
49
55
22
slide 147: • https://www.codingbot.net/2013/02/radix-
sort-algorithm-and-c-code.html