Page 136 - DCAP407_DATA_STRUCTURE

Sarabjit Kumar, Lovely Professional University Unit 8: Queues

Unit 8: Queues

CONTENTS
Objectives
Introduction
8.1 Fundamentals of Queues
8.2 Basic Operations of Queue

8.2.1 Insert at Rear End
8.2.2 Delete from the Front End
8.3 Representing Queue in Memory
8.4 Types of Queue
8.4.1 Double Ended Queue
8.4.2 Circular Queue
8.4.3 Priority Queue

8.5 Summary
8.6 Keywords
8.7 Self Assessment
8.8 Review Questions
8.9 Further Readings

Objectives
After studying this unit, you will be able to:
• Describe the fundamentals of queues

• Discuss the basic operations of queues
• Analyze representing queues in memory
• Explain the types of queues
Introduction

A queue is a linear list of elements that consists of two ends known as front and rear. We can delete
elements from the front end and insert elements at the rear end of a queue. A queue in an application is
used to maintain a list of items that are ordered not by their values but by their sequential value.

If the users of a particular website want to select a list of reports throughout the
day, and during idle time wants to print those reports. The website can be
designed in a way that information stored internally can be retrieved easily by
implementing the queue mechanism. If a user needs to find the name of the next
report to print, the information can be obtained from the top of the queue and
new addition of the reports get stored easily at the rear end.
8.1 Fundamentals of Queues

A queue is an ordered collection of items in which deletion takes place at one end, which is called the
front of the queue, and insertion at the other end, which is called the rear of the queue. The queue is a
‘First In First Out’ system (FIFO). In a time-sharing system, there can be many tasks waiting in the

LOVELY PROFESSIONAL UNIVERSITY 129