Queues Flashcards
(21 cards)
On what kind of basis is data retrieved from a queue?
First-In-First-Out
What are the key operations of a queue?
- Add and item
- Remove an item
- Test for an empty queue
- Test for a full queue
What are queues comprised of?
- Sequence of items
- Rear pointer
- Front pointer
What are the uses of queues?
- Maintaining a queue of print jobs
- Managing an input buffer
- Handling multiple file downloads
- Maintaining a playlist of media
What is a linear queue?
A simple static and array based implementation of a queue
What are the advantages and disadvantages of linear queues?
+Simple to program
-Can lead to wasted capacity if elements at front of array are empty after dequeueing
-Process of shuffling data to solve issue of wasted capacity is inefficient
What is a circular queue?
A static array based implementation of a queue with “wrapping” front and rear pointers
What are the advantages and disadvantages of a circular queue?
+It avoids wasted space with no need of shuffling
- more complex to implement
(-Can still run out of storage space)
What are the different types of queues?
- Linear
- Circular
- Priority
How do you test if a linear queue is empty?
Check if the front pointer is greater than rear pointer
How do you test of a linear queue is full?
Check if the index indicated by rear pointer is equal to max size of queue -1
How do you enqueue items in a linear queue?
- Check if full
- Increment rear pointer
- Assign item to index indicated by rear pointer
How do you dequeue items in a linear queue?
- Check if empty
- Return value at the front pointer
- Increment front pointer
How do you peek a linear queue?
- Check if empty
- Return value at front pointer
How do you enqueue items in a circular queue?
- Check if queue is full
- Increment rear pointer and modulus it with the maximum size of the array
- Add items at index indicated by rear pointer
- Increment queue size
How do you dequeue items from a circular queue?
- Check if empty
- Store removed item
- Increment front pointer and modulus with maximum size of the array
- Decrement the queue size and return item
What area the differences between a circular and linear queue? (Structure only)
- Circular more efficient but also more complex
- Circular can wrap around memory locations
- No space is wasted after dequeueing
- Linear queues shuffle to avoid wasted space but this is inefficient
- Circular queues don’t need to do this
What is a priority queue?
A type of queue where each item in the queue has a priority.
How do priority queues work?
- Items are stored within the queue based on priority with highest priority at the front.
- When enqueueing we search for an item that has less priority and insert the item in front of it by shuffling everything after it
- This preserves FIFO within priority levels
How do you enqueue items onto priority queue
How do you dequeue items from priority queue
