Data Structure and
Algorithms
(Queues)
UKZN
ENEL2DSH2
2016
,Broad classification
Broadly classified as linear or non-linear
• Linear DS
§ Arrays (Covered in lecture_4)
§ Linked list (Covered in lecture_5)
§ Stacks (Covered in lecture_6-1)
§ Queues
§ Hash tables
• Non-linear DS
§ Trees
§ Graphs
,Introduction
Queue is a “waiting list” such as :
1. A line of persons waiting to check out at the supermarke
2. A line of vehicles at a toll booth.
3. A queue of planes waiting to land at an airport.
4. A queue of jobs in a computer system waiting for output
device such as printer.
, Introduction
Cont.
• The first item in the queue is the first to be served.
• A queue is a First-In-First-Out (FIFO) structure
• Also considered as a First-Come-First-Served (FCFS) structur
• Is a special kind of list in which the basic insert and delete operatio
are restricted to the ends of the list.
• Items are removed from a queue at one end, called front (head) of
queue, and elements are added only at the other end called back (re
or tail).
Algorithms
(Queues)
UKZN
ENEL2DSH2
2016
,Broad classification
Broadly classified as linear or non-linear
• Linear DS
§ Arrays (Covered in lecture_4)
§ Linked list (Covered in lecture_5)
§ Stacks (Covered in lecture_6-1)
§ Queues
§ Hash tables
• Non-linear DS
§ Trees
§ Graphs
,Introduction
Queue is a “waiting list” such as :
1. A line of persons waiting to check out at the supermarke
2. A line of vehicles at a toll booth.
3. A queue of planes waiting to land at an airport.
4. A queue of jobs in a computer system waiting for output
device such as printer.
, Introduction
Cont.
• The first item in the queue is the first to be served.
• A queue is a First-In-First-Out (FIFO) structure
• Also considered as a First-Come-First-Served (FCFS) structur
• Is a special kind of list in which the basic insert and delete operatio
are restricted to the ends of the list.
• Items are removed from a queue at one end, called front (head) of
queue, and elements are added only at the other end called back (re
or tail).
