UNIVERSITY INSTITUTE OF ENGINEERING
DEPARTMENT- ACADEMIC UNITS
FIRST YEAR ENGINEERING PROGRAMMES
Subject Name : Elementary Data Structures using C++
Subject Code: 23CSH-103
QUEUE DISCOVER . LEARN . EMPOWER
Elementary Data
Structure Using C++
Course Objectives
• To enable the students to understand various stages
and constructs of C++ programming language.
• To improve their ability to analyze and address
variety of problems in C++.
• To understand the concept of data structures and
various operations on them.
• To understand the properties of various data
structures and able to identify the strengths and
weaknesses of different data structures.
• To analyze and compare the efficiency of
algorithms and learn to design efficient algorithms
for solving computing problems
2
Course Outcomes
CO Course Outcome
Number
CO1 Understand the concepts of object-oriented programming including
programming process and compilation process.
CO2 Apply different techniques to decompose a problem and
programmed a solution with various concepts of object-oriented
programming language.
CO3 Analyse and explain the behaviour of linear data structure
operations using the programming addressed in the course.
CO4 Implement and evaluate the programs using the syntax and
semantics of object-oriented programming.
CO5 Design the solution of real-world problems in order to determine
that the program performs as expected.
3
ASSESSMENT PATTERN
The performance of students is evaluated as follows:
Theory Practical
Continuous Internal Semester End Continuous Internal Semester End
Components Assessment (CAE) Examination (SEE) Assessment (CAE) Examination (SEE)
Marks 40 60 60 40
Total Marks 100 100
4
Queues
• Like a stack, a queue is also a list. However, with a queue, insertion is done
at one end, while deletion is performed at the other end.
-- The insertion end is called rear
-- The deletion end is called front
Remove Insert
front rear
Queues
A queue is a data structure • A Queue is "an abstract data type in which
that stores data in such a way elements are added to the rear and removed
that the last piece of data from the front; a 'first in, first out' (FIFO)
stored, is the last one structure."
retrieved. It is also called First-
In, First-Out (FIFO).
Consider people standing in
line. They get service in the
order they arrive.
[Link]
6
Queues
• A Queue is a linear list of elements in which deletions can take place
only at one end, called the front, and insertions can take place only at
the other end, called the rear. The terms “front” and “rear” are used
in describing a linear list only when it is implemented as a queue.
• Queues are also called first-in first-out (FIFO) lists, since the first
element in a queue will be the first element out of the queue. In
other words, the order in which elements enter a queue is the order
in which they leave. This contrasts with stacks, which are Last-in First-
out (LIFO) lists.
Queue in everyday life
• The automobiles waiting to pass through an intersection form a
queue, in which the first car in line is the first car through.
• The people waiting in line at a bank form a queue, where the first
person in line is the first person to exit from the queue.
• An important example of a queue in computer science occurs in a
timesharing system, in which programs with the same priority form a
queue while waiting to be executed.
• Queue for printing purposes.
Queues
Figure (a) is a schematic diagram of a queue with 4 elements, where AAA is the front element and
DDD is the rear element. Observe that the front and rear elements of the queue are also,
respectively, the first and last elements of the list. Suppose an element is deleted from the queue.
Then it must be AAA. This yields the queue in figure (b), where BBB is now the front element. Next,
suppose EEE is added to the queue and then FFF is now the rear element. Now suppose another
element is deleted from the queue; then it must be BBB, to yield the queue in figure (d). And so on.
Observe that in such a data structure, EEE will be deleted before FFF because it has been placed in
the queue before FFF. However, EEE will have to wait until CCC and DDD are deleted.
LINKED REPRESENTATION OF QUEUE:
(a) AAA BBB CCC DDD
(b) BBB CCC DDD
(c) BBB CCC DDD EEE FFF
(d) CCC DDD EEE FFF
Array/Sequential representation of queue
When an element is deleted from the queue,
the value of FRONT is increased by 1; this can be
implemented by the assignment
FRONT := FRONT + 1
Similarly, whenever an element is added to the
queue, the value of REAR is increased by 1; this
can be implemented by the assignment
REAR := REAR + 1
Queues
• Enque
• operation to place a new item at the tail of the queue
• Dequeue
• operation to remove the next item from the head of the queue
Queue
start end
X A M
enqueue(F)
start end start end
X A M F A M F
item = dequeue()
item = X
Algorithm for Insertion into a Queue
1. If REAR=MAX then: write: Overflow & Exit
2. Read ITEM
If FRONT=0 then:
a) FRONT=FRONT+1
b) REAR=REAR+1
c) Q[REAR]=ITEM
else
REAR=REAR+1
Q[REAR]=ITEM
3. Exit QUEUE
(a) Initially empty : FRONT : 0
REAR : 0
1 2 3 4 5
(b) A, B and then C inserted: FRONT : 1 A B C
REAR : 3
(C) A deleted : FRONT : 2 B C
REAR : 3
(d) D and then E inserted : FRONT : 2
REAR : 5 B C D E
Algorithm for deletion from a Queue
• If FRONT=0 then: write: “UNDERFLOW and Exit”
• If FRONT=REAR, then:
Q[FRONT]=NULL
FRONT=0
REAR=0
else
Q[FRONT]=NULL
FRONT=FRONT+1
• Exit
Limitations of linear Queue
• When an element is removed from linear queue, the location remains
unused. Even if the queue is empty, new elements cannot be
inserted. To avoid this, consider queue as a circle, having the last
element immediately following the first element.
Circular Queue
• Circular queue is a linear data structure in which the operations are
performed based on FIFO (First In First Out) principle and the last
position is connected back to the first position to make a circle. It is
also called ‘Ring Buffer’.
16
• In a normal Queue, we can insert elements until queue becomes full.
But once queue becomes full, we can not insert the next element.
Where as in circular queue space of deleted elements can be utilized.
17
Operations on Circular Queue:
• Front: Get the front item from queue.
• Rear: Get the last item from queue.
• enQueue(value) 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.
[Queue already fill]
1. If FRONT=1 and REAR=N, or if FRONT=REAR+1, then : Write: Overflow, and Exit.
2. [Find new value of REAR]
If FRONT=NULL, then :[Queue initially empty]
Set FRONT:=1 and REAR:=1
Else if REAR =N then
Set REAR:=1
Else Set REAR:=REAR+1
[End of if structure]
3. Set QUEUE[REAR]:=ITEM [This inserts new element]
4. Exit.
18
deQueue() This function is used to delete an element from the circular
queue. In a circular queue, the element is always deleted from front
position.
1. [Queue already empty]
If FRONT=NULL, then Write: Underflow, and Exit.
2. Set ITEM=QUEUE[FRONT]
3. [Find new value of FRONT]
If FRONT=REAR, then [Queue has only one element to start]
Set FRONT=NULL and REAR=NULL
Else if FRONT =N then
Set FRONT =1
Else
Set FRONT = FRONT +1
[End of if structure]
4. Exit 19
EXAMPLE: Insertion & Deletion in a circular queue
Advantages of circular queue over linear queue
• In circular queue, the memory of the deleted process can be used by
some other new process.
• Rear insertion is denied in a linear queue even if the room is available.
Thus, even if the free memory is available, we cannot access these
memory locations. This is the major disadvantage of linear queue
which is overcome by circular queue.
• Time Complexity: Time complexity of enQueue(), deQueue()
operation is O(1) as there is no loop in any of the operation.
Applications of Queue
• Resource sharing among multiple consumers.
• Queues are useful in time sharing systems where many user jobs will be waiting in the system
queue for processing. These jobs may request the services of the CPU, main memory or external
devices such as printers, etc. All these jobs will be given a fixed time for processing and are
allowed to use one after the other. This is the case of an ordinary queue where priority is the
same for all the jobs & whichever job is submitted first, that job will be processed.
• Queues are used in designing CPU schedulers where jobs are dispatched to the CPU based on
priority of the job.
22
REFERENCES
• [Link]
• Data Structures with C/ schaum outline series/ volume 2
• [Link]
• [Link]
• [Link]
• Lipschutz, Seymour, “Data Structures”, Schaum's Outline Series, Tata McGraw Hill.
• Gilberg/Forouzan,” Data Structure with C ,Cengage Learning.
• Augenstein,Moshe J , Tanenbaum, Aaron M, “Data Structures using C and C++”, Prentice Hall of India.
• Goodrich, Michael T., Tamassia, Roberto, and Mount, David M., “Data Structures and Algorithms in C++”, Wiley Student
Edition.
• Aho, Alfred V., Ullman, Jeffrey D., Hopcroft ,John E. “Data Structures and Algorithms”, Addison Wesley
23
THANK YOU