Page 87 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms Anil Sharma, Lovely Professional University

Notes Unit 4: Queues

CONTENTS

Objectives
Introduction
4.1 Queue Model
4.2 Array Implementation
4.2.1 Array-based Implementation

4.2.2 Pointer-based Implementation
4.3 Applications of Queues
4.4 Summary
4.5 Keywords

4.6 Self Assessment
4.7 Review Questions
4.8 Further Readings

Objectives

After studying this unit, you will be able to:
Describe queue model

Know array implementation
Describe various applications of queues

Introduction

The queue abstract data type is also a widely used one with applications very common in real
life. An example comes from the operating system software where the scheduler picks up the
next process to be executed on the system from a queue data structure. In this unit, we would
study the various properties of queues, their operations and implementation strategies.
4.1 Queue Model

A queue is a list of elements in which insertions are made at one end-called the rear and deletions
are made from the other end-called the front. This means, in particular, that elements are removed
from a queue in the same order as that in which they were inserted into the queue. Thus, a queue
exhibits the FIFO (First In First Out) property.
The following are the allowed operations on a queue Q:

1. insert(Q, e): This inserts an element e into the queue Q.
2. delete(Q) Æ e: This deletes an element from the queue Q and stores it into e.
3. empty(Q) Æ true/false: This checks whether a queue is empty or not.

82 LOVELY PROFESSIONAL UNIVERSITY