4.2.2 - FoDS (Queues)

Question 1

What type of data structure (FIFO OR LIFO) 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 is meant by a pointer

Answer 2

• A reference to the location of stored data items in stacks and queues

Question 3

What are the three different types of queues

Answer 3

• Linear
• Circular
• Priority

Question 4

What are the features of a linear queue

Answer 4

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

Question 5

What is the disadvantage of linear queues

Answer 5

• memory inefficient as, once the rear of the queue reaches the end of the array, no new elements can be added—even if there are empty spaces at the front—resulting in unused memory.

Question 6

What are the features of a circular queue

Answer 6

• Circular queues treat the array as a circle, so when the rear reaches the end, it wraps around to the front if space is available.

Question 7

What is the advantage of circular queues

Answer 7

• allows space reuse when items are dequeued

Question 8

What are the features of a priority queue

Answer 8

Elements are dequeued based on priority instead of arrival order.

Question 9

How many pointers do queues have and where are they placed

Answer 9

• 2 placed at the front and back of the queue

Question 10

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

Answer 10

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

Question 11

What are the 4 key functions of a queue

Answer 11

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

Question 12

How do you add items to the back of the queue

Answer 12

• 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 13

How do you remove items from the front of the queue

Answer 13

• 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 14

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

Answer 14

To the same memory location

Question 15

What is distinct about circular queues

Answer 15

When data items are added only the back pointer is modified

Question 16

When is a circular queue full

Answer 16

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

Question 17

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

Answer 17

• The same as in a normal linear queue