Queues

Question 1

What type of data structure is a queue?

Answer 1

It’s a FIFO data structure

First in First out

Question 2

What are some real life examples of a queue being used?

Answer 2

• Characters typed into a keyboard are held in a queue in a keyboard buffer
• Output waiting to be printed is stored in a queue on disk. The output is then printed on a first served basis when the printer is free.

Question 3

How many pointers does a queue data structure have?

Answer 3

It has 2 pointers, the front and the rear

Question 4

What happens in the queue data structure when items are added/removed?

Answer 4

The front pointer moves. None of the elements move.

Question 5

What are the 4 operations that can be carried out on a queue?

Answer 5

• enQueue(item)
• deQueue()
• IsEmpty()
• isFull()

Question 6

What does the enQueue(item) operation do?

Answer 6

Adds a new item to the rear of the queue

Question 7

What does the deQueue() operation do?

Answer 7

Removes the first item from the front of the queue and returns it

Question 8

What does the isEmpty() operation do?

Answer 8

Tests to see whether the queue is empty

Question 9

What does the isFull() operation do?

Answer 9

Tests to see whether the queue is full

Question 10

What is the heap?

Answer 10

A portion of memory from which space is automatically allocated and de-allocated as required

Question 11

What is a static data structure?

Answer 11

Where the size of the data structure is fixed once it is defined. For example an array

Question 12

What is a dynamic data structure?

Answer 12

Where the size of the data structure can grow or shrink

Question 13

Why are dynamic data structures useful?

Answer 13

They are useful for implementing data structures (queues) where the size of the data structure is not known in advance

Question 14

What is an advantage of using a static data structure?

Answer 14

No pointers or excess information about the data structure needs to be stored

Question 15

What is a disadvantage of using a static data structure?

Answer 15

Memory that has been allocated to the data structure cannot be reallocated even if most of it is unused

Question 16

What is one way to implement a linear queue in an array or list.

Answer 16

As items are removed, all the other items move up one space so the front of the queue is always the first element of the data structure

Question 17

How does a circular queue solve the limitations of a implementing a linear queue?

Answer 17

When the array fills up and the rear pointer points to the last element in the array (assuming it is empty) the rear pointer will be made to point to the first element in the array when another item is enqueued.

Question 18

How does a priority queue act?

Answer 18

It continues to act as a FIFO data structure, however items with a high priority can be added to the front of the queue instead of the rear.

Question 19

How could a priority queue be implemented?

Answer 19

• By checking the priority of each item in the queue
• starting at the front and moving along one item until an item with the same/lower priority if found
• At which point the item can be inserted