4.2.2 - FoDS (Queues)

Question 1

What type of data structure is a Queue, and what does the term used to describe it mean

Answer 1

FIFO (First in First out)
- Meaning the first item to enter the queue is the first to leave the queue

Question 2

What are the three different types of queues

Answer 2

• Linear
• Circular
• Priority

Question 3

What are the features of a linear queue

Answer 3

• elements are added at the rear and removed from the front

Question 4

What is the disadvantage of linear queues

Answer 4

• Inefficient as space is wasted when elements are dequeued.

Question 5

What are the features of a circular queue

Answer 5

• Queue where the last position connects to the first, allowing space reuse. Prevents wasted space from dequeued elements.

Question 6

What is the advantage of circular queues

Answer 6

• allows space reuse when items are dequeued

Question 7

What are the features of a priority queue

Answer 7

Elements are dequeued based on priority instead of arrival order.

Question 8

How many pointers do queues have and where are they placed

Answer 8

• 2 placed at the front and back of the queue

Question 9

How do you remove an item in the middle of a queue

Answer 9

• You must first remove all of the items preceding it in the queue

Question 10

What are the 4 key functions of a queue

Answer 10

• Add
• Remove
• Check if empty
• Check if Full

Question 11

How do you add items to the back of the queue

Answer 11

• First check to see that the queue is not full
• If full report an error and stop
• Increment the back pointer and stop
• Insert new data into the location pointed to by the back pointer

Question 12

How do you remove items from the front of the queue

Answer 12

• First check to see that the queue is not empty
• If empty report an error and stop
• Copy the data pointed by the front pointer (item to be deleted)
• Increment the front pointer and stop

Question 13

When a circular queue is empty where do the front and back pointer point

Answer 13

To the same memory location

Question 14

What is distinct about circular queues

Answer 14

When data items are added only the back pointer is modified

Question 15

When is a circular queue full

Answer 15

When the back pointer points to the data location one less than the front pointer

Question 16

When items in a priority queue have the same priority how are they treated

Answer 16

• The same as in a normal linear queue