Flashcards in Queues Deck (19)
What type of data structure is a queue?
It's a FIFO data structure
(First in First out)
What are some real life examples of a queue being used?
- 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.
How many pointers does a queue data structure have?
It has 2 pointers, the front and the rear
What happens in the queue data structure when items are added/removed?
The front pointer moves. None of the elements move.
What are the 4 operations that can be carried out on a queue?
What does the enQueue(item) operation do?
Adds a new item to the rear of the queue
What does the deQueue() operation do?
Removes the first item from the front of the queue and returns it
What does the isEmpty() operation do?
Tests to see whether the queue is empty
What does the isFull() operation do?
Tests to see whether the queue is full
What is the heap?
A portion of memory from which space is automatically allocated and de-allocated as required
What is a static data structure?
Where the size of the data structure is fixed once it is defined. For example an array
What is a dynamic data structure?
Where the size of the data structure can grow or shrink
Why are dynamic data structures useful?
They are useful for implementing data structures (queues) where the size of the data structure is not known in advance
What is an advantage of using a static data structure?
No pointers or excess information about the data structure needs to be stored
What is a disadvantage of using a static data structure?
Memory that has been allocated to the data structure cannot be reallocated even if most of it is unused
What is one way to implement a linear queue in an array or list.
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
How does a circular queue solve the limitations of a implementing a linear queue?
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.
How does a priority queue act?
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.