Programming Concepts: Queues

PAPER 1 - ⇑ Fundamentals of data structures ⇑
← Fields records and files	Queues	Stacks →

A queue is a first-in first-out (FIFO) abstract data type that is heavily used in computing. Uses for queues involve anything where you want things to happen in the order that they were called, but where the computer can't keep up to speed. For example:

Keyboard Buffer - you want the letters to appear on the screen in the order you press them. You might notice that when your computer is busy the keys you press don't appear on the screen until a little while after you press them. When they do appear they appear in the order you press them.
Printer Queue - you want print jobs to complete in the order you sent them, i.e. page 1, page 2, page 3, page 4 etc. When you are sharing a printer several people may send a print job to the printer and the printer can't print things instantly, so you have to wait a little while, but the items output will be in the order you sent them.

There are several different types of queues such as the ones described below:

Linear

In this queue form, elements are able to join the queue at one end and can exit from the queue at the other end. First In First Out (FIFO).

A real life example of this would be queuing to pay at the supermarket. The first person into the queue is the first person to be served. And if you join the queue last you are going to be served last (no pushing!). However, there is one difference, in a supermarket queue once the first person has been served the rest of the queue shuffles forward, making the previously second person now first, this is possible in a computer but very costly in terms of processing. The linear queue you are about to see 'crawls' through memory, devouring everything it comes across.

The most basic implementation of a linear queue would work its way through its allotted memory, without reusing memory. The front and end pointers can only move forwards and sooner or later would reach the end of the allotted memory - at this point, no more items could be added to the queue. Take a look at this example and the values of the two pointers storing the front of the queue (FrontPtr) and the next free memory location (NextFree).

State 1

State 2

State 3

State 4

State 5

State 6

start state

H joins queue

Start is served

J joins queue

Start is served

P joins queue

1	2	3	4	5
D	G	A

 FrontPtr = 1
 NextFree = 4

1	2	3	4	5
D	G	A	H

 FrontPtr = 1
 NextFree = 5

1	2	3	4	5
D	G	A	H

 FrontPtr = 2
 NextFree = 5
 Output = D

Note that no data is
'deleted', but the
pointers changed

1	2	3	4	5
D	G	A	H	J

 FrontPtr = 2
 NextFree = 6

1	2	3	4	5
D	G	A	H	J

 FrontPtr = 3
 NextFree = 6
 Output = G

1	2	3	4	5	6
D	G	A	H	J	P

 FrontPtr = 3
 NextFree = 7

Even though slots before 3
are no longer needed, no
more data can be added as
NextFree has gone beyond
the last slot

A better implementation would reuse memory by shifting each item one to the left, each time an item is removed from the front. However, if there are many items in the queue this could become very slow. See below (note that we no longer need a front pointer as item 1 is always the front):

State 1

State 2

State 3

State 4

State 5

State 6

start state

H joins queue

Start is served

J joins queue

Start is served

P joins queue

1	2	3	4	5
D	G	A

 NextFree = 4

1	2	3	4	5
D	G	A	H

 NextFree = 5

1	2	3	4	5
G	A	H

 NextFree = 4
 Output = D

D is removed, other
items are shifted
to the left

1	2	3	4	5
G	A	H	J

 NextFree = 5

1	2	3	4	5
A	H	J

 NextFree = 4
 Output = G

1	2	3	4	5
A	H	J	P

 NextFree = 5

Fast to implement, with simple code

However:

Removing items from the front of the queue can be slow

Circular

Unlike linear queues Circular queues allow for memory to be re-used:

Generally, a circular buffer requires three pointers:

one to the actual buffer in memory
one to point to the start of valid data
one to point to the end of valid data

The following example shows a partially-full fixed length buffer and how it handles additions and deletions from a queue. Take particular care to note the pointers.

Diagram	StartPtr	EndPtr
	3	5
Data is specified as being between the StartPtr and the EndPtr
	3	6
Adding another element to the queue moves the EndPtr up one
	4	6
Deleting an element from the front of the queue is achieved by increasing the StartPtr by one
	4	7
Adding another element to the queue moves the EndPtr up one, it is now at the end of the buffer
	4	1
Adding another element to the queue makes the EndPtr loop around to the free space at the beginning of the buffer
	4	2
Adding another element to the queue moves the EndPtr up one, it is now closing in the on the StartPtr
	4	3
Adding another element to the queue moves the EndPtr up one, it is now closing in the on the StartPtr. If we tried to add another element to the circular queue we couldn't without first removing something from the front of the queue

Circular queues are very common in computer science and they are used to store things, they have the following benefits

They reuse memory space, meaning they won't overwrite data or run out of memory (within limits)

and drawbacks:

Involve storing pointers as well as data, taking up more space than linear queues

Limited by the amount of data available in the buffer (array)

Priority

This is based on the order of priority of the elements in the queue. In other words, each element of this type of queue has different level of priority attached to it; e.g., high priority or low priority.

A real world example of this would be an Accident and Emergency Department waiting room, someone who had fallen over, would probably be low priority compared with someone who had cut their head open, and as such even if the head injury patient came in later they would probably jump the queue.

State 1	State 2	State 3
1. broken arm 2. grazed knee	1. heart attack 2. broken arm 3. grazed knee	1. heart attack 2. severe concussion 3. broken arm 4. grazed knee
initial queue	heart attack top priority jumps the queue	severe concussion less important than heart attack, so moves to second

In a computer we use priority queues to handle the execution of processes. Each process will have a priority attached to it, with the more important processes jumping ahead of the less important for the processor's attention when they require it. For example:

Process	Priority
Web Browser	Normal
Media Player	Below Normal
OS Security	High
Scheduled Virus Scanner	Low
Printer Queue	Low
Word Processor	Normal

Extension Scheduling Algorithms

There are several methods we can use to handle processor scheduling, each have their own benefits and drawbacks:

Scheduling algorithm	CPU Utilization	Throughput	Turnaround time	Response time
First In First Out	Low	Low	High	Low
Shortest Job First	Medium	High	Medium	Medium
Priority based scheduling	Medium	Low	High	High
Round-robin scheduling	High	Medium	Medium	High
Multilevel Queue scheduling	High	High	Medium	Medium

Exercise: Queues

Why would you use a circular queue over a linear queue?

Answer:

A circular queue uses a fixed amount of memory and reuses memory as it moves through the queue. A linear queue does not reuse memory and can waste memory.

Name three pointers used in implementing a circular queue

Answer:

one to the actual buffer in memory
one to point to the start of valid data (StartPtr)
one to point to the end of valid data (EndPtr)

What happens in a priority queue when a task of higher priority wants the processor's attention?

Answer:

The lower priority task is queued and the higher priority task is given the processors attention

For what would be the value of the pointers when Monkey and Snake are added, the first item removed and then Bear added to the following queue:

1	2	3	4	5
Badger	Ferret	Weasel

If it were a circular queue?

Answer:

1	2	3	4	5
Bear	Ferret	Weasel	Monkey	Snake

StartPtr = 2
EndPtr = 1

If it were a linear queue?

Answer:

This would break, as there is no more space left in the queue!

Describe the functioning of a queue:

Answer:

A first in first out data type

Name two uses for a queue in a computer:

Answer:

keyboard buffer
printer queue