Queues

Question 1

What is a queue?

Answer 1

An abstract data structure based on an array often referred to as a first in first out abstract data structure.

Question 2

How do you enqueue to a linear queue?

Answer 2

1. Check is the queue is full.
2. If full, report overflow error.
3. If not full, increase rear pointer and QueueSize by one.
4. Insert new item in position indicated by rear pointer.

Question 3

How do you dequeue from a linear queue?

Answer 3

1. Check if the queue is empty.
2. If empty, report underflow error.
3. If not, return the item in position indicated by front pointer.
4. Increase front pointer by one and decrease QueueSize by one.

Question 4

What is the limitation of a linear queue?

Answer 4

Once an item is dequeued, its memory location cannot be reused.

Question 5

What is a circular queue?

Answer 5

A queue where when a pointer moves past the end of the queue, it wraps around to the start index.

Question 6

How do you enqueue to a circular queue?

Answer 6

1. Check if the queue is full, if so report an over flow error.
2. If not, increase rear pointer by one.
3. If the index of the rear pointer is greater then the max index, set the rear pointer to zero.
4. Insert a new item in position indicated by rear pointer.
5. Increase QueueSize by one.

Question 7

How do you dequeue from a circular queue?

Answer 7

1. Check if queue is empty, if so report an underflow error.
2. If not, return the item in the position indicated by the front pointer.
3. Increase the front pointer by 1.
4. If the index of the front pointer is greater than the maximum index, set the front pointer to 0.
5. Decrease the QueueSize by one.

Question 8

What is a priority queue?

Answer 8

Items are assigned a priority.
Higher priority items are dequeued before lower priority items.
If multiple items have the same priority, items are removed in FIFO order.

A high priority item will be added at the back of all of the other high priority items, but before the medium items, which themselves are before the low priority items.