Computing - Queues
What is a queue?
A dynamic data structure in which items join at the back and leave at the front.
Why is a queue a dynamic data structure?
Because it can contain a variable amount of data.
What variables are needed for a queue using a dynamic array?
- A pointer to the start
- A pointer to the next space
When implementing a queue using a dynamic array, what one thing do you do to dequeue?
Increment the pointer to the start of the queue.
When implementing a queue using a dynamic array, what two things do you do to enqueue?
Store the data in the next space and increment the next space pointer.
What is the main advantage of a dynamic array implementation of queue?
Easy to implement.
What is the main disadvantage of a dynamic array implementation of a queue?
Memory is never freed up
What variables are needed for a queue using a static array?
- A pointer to the front
- A pointer to the rear
- A variable holding the amount of items in the queue
When implementing a queue using a static array, what two things do you do to dequeue?
- Increment the pointer to the front of the queue
- Decrement the variable holding the amount of items in the queue
When implementing a queue using a static array, what three things do you do to enqueue?
- Increment the pointer to the rear of the queue
- Store the data
- Increment the variable holding the amount of items in the queue
What operation do you perform when a static array-based queue runs out of space?
A shuffle.
What is a shuffle operation in a static array-based queue?
Moving everything back into the unused space at the front of the queue.
What is the main advantage of a static array implementation of a queue?
Memory is reused.
What is the main disadvantage of a static array implementation of a queue?
The shuffle operation may be expensive.
What variables are needed for a circular queue?
- A pointer to the front
- A pointer to the rear
- A variable holding the amount of items in the queue
When implementing a circular queue, what two things do you do to dequeue?
- Increment the pointer to the front of the queue
- Decrement the variable holding the amount of items in the queue
When implementing a circular queue, what three things do you do to enqueue when there’s still space left in the array?
- Increment the pointer to the rear of the queue
- Store the data
- Increment the variable holding the amount of items in the queue
When implementing a circular queue, what three things do you do to enqueue when there’s no more space left at the end of the array?
- Redefine the rear of the queue pointer to the start of the array
- Store the data
- Increment the variable holding the amount of items in the queue
When implementing a circular queue, what one thing do you need to do when you dequeue the last space in the array?
- Reset the front of the queue pointer to the start of the array
How can you tell you can’t add any more data in a circular queue?
The amount of data in the queue matches the length of the array.
What are the two representations for a linear queue?
- A dynamic array
- A static array