Queue Flashcards
How would you describe a queue?
- Usually First in first out
- Some exceptions ie., Priority Queue
- Add to front (enqueue)
- Remove from rear (dequeue)
- Size in the num of elements
When is a queue a good choice?
A queue is good when you want to get elements out in the same order as you put them in
What is a priority queue?
A Priority Queue is an implementation of the Queue interface that provides a priority ordering of elements.
It stores elements in a priority heap and allows elements to be removed in order of their priority.
Can you insert a NULL value into a queue?
No you shouldn’t, but technically you can insert NULL into LinkedList which implements the queue interface
What are the 3 most common implementations of the queue interface?
Priority Queue
LinkedList
Array Dequeue (Double Ended Queue)
What is the difference between a regular queue and a priority queue?
Each queue’s item has an additional piece of information, namely priority. Unlike a regular queue, the values in the priority queue are removed based on priority instead of the first-in-first-out (FIFO) rule.
What is the benefit of the queue?
You only need to keep track of two positions
What five queue operations are O(1)?
- enqueue (add to end)
- dequeue (remove from front)
- peek
- isEmpty
- isFull
O(1) because items are added or removed from the ends
What would you need for an Array implementation of a queue that had variables, a constructor, enqueue, dequeue and a toString method?
public class ArrayQueue {
private int[] items;
private int rear;
private int front;
private int count;
public ArrayQueue(int capacity) {
items = new int[capacity];
}
public void enqueue(int item) {
if (isFull())
throw new IllegalStateException();
items[rear] = item; rear = (rear + 1) % items.length; count++; }
public int dequeue() {
if (isEmpty())
throw new IllegalStateException();
var item = items[front]; items[front] = 0; front = (front + 1) % items.length; count--; return item; }
public int peek() {
if (isEmpty())
throw new IllegalStateException();
return items[front]; }
public boolean isEmpty() {
return count == 0;
}
public boolean isFull() {
return count == items.length;
}
@Override
public String toString() {
return Arrays.toString(items);
}
}
If we create a priority queue and add 5, 1, 3 and 2 to the queue in this order
If we loop through and remove each element in the queue, what order will the elements be printed?
1,2,3,5
because the default ordering of a java priority queue is ascending order
so if we added another value 4 it would not be added to the end, it would be added between 3 and 5
How do you reverse a queue?
- Create a stack
- While there are elements in the queue, remove each element from the queue, and push it to the stack
- While there are elements in the stack, pop the elements from the stack and add them to the queue
What are the most common implementations of the queue data structure in Java?
LinkedList - This is a linked list-based implementation of the Queue interface in Java. It provides O(1) time complexity for both adding and removing elements from both ends of the queue.
PriorityQueue - This is an implementation of the Queue interface that provides a priority ordering of elements. It stores elements in a priority heap and allows elements to be removed in order of their priority.
ArrayDeque - This is a double-ended queue (deque) implementation that allows elements to be added and removed from both ends of the queue. It provides constant-time performance for adding and removing elements from the beginning or end of the queue.
BlockingQueue - This is an interface that extends the Queue interface and provides additional methods for blocking operations. It allows a thread to wait until an element is available in the queue or until space is available for adding an element to the queue.
What is ArrayDeque?
Double Ended Queue (can add and remove from both sides)
Internally uses a resizable array
