Queues

Flashcards about Queues and Priority Queues in Java

What is a queue?

A waiting line that grows by adding elements to its end and shrinks by taking elements from its front.

What does FIFO stand for in the context of queues?

First In/First Out

What are the essential operations for managing a queue?

clear(), isEmpty(), enqueue(el), dequeue(), front()

What happens when you try to dequeue or front an empty queue?

Throws an EmptyQueueException

Give three direct applications of queues

Waiting lists, Access to shared resources, Multiprogramming

Give two indirect applications of queues

Auxiliary data structure for algorithms, Component of other data structures

In what order does a Queue process its data?

First In First Out order

How can a queue be used to implement a round-robin scheduler?

Repeatedly dequeue, service, and enqueue elements

How does Round-robin scheduling work in operating systems?

Assigns time slices to each process in equal portions and in circular order, handling all processes without priority.

What two variables are required to keep track of the queue in an Array-based queue?

Front and last

What does isFull() do in the ArrayQueue class?

Returns whether the queue is full

What does isEmpty() do in the ArrayQueue class?

Returns whether the queue is empty

When is grow() called in Array implementation of queues?

Doubles the size of the array and copies elements

What does enqueue(Object x) do?

Adds an element to the end of the queue

What does front() do in the array implementation of a queue?

Returns the first element in the queue without removing it

What does dequeue() do in the array implementation of a queue?

Removes and returns the first element in the queue

In a linked list implementation of a queue, what are the two key node pointers?

head and tail

How do you enqueue an item in a linked list implementation of a queue?

Adds a new node at the tail

How do you dequeue an item in a linked list implementation of a queue?

Removes the head node

What is CircularQueue?

A Java interface that extends the Queue ADT with a new rotate( ) method.

What does rotate() do in circular queues?

Move the first element to the end of the queue

What operations are supported by a double-ended queue (Deque)?

Insert and delete at both the front and back

Name the methods for updating or modifying a Deque?

addFirst(e), addLast(e), removeFirst(), removeLast()

What accessor methods are commonly included in a Deque ADT?

first(), last(), size(), isEmpty()

How do priority queues differ from regular queues?

Breaks the FIFO rule by dequeuing elements based on assigned priority

How do elements get dequeued according to their priority queue position?

Elements are dequeued according to their priority and their current queue position

How does enqueue(float x) work in the array implementation of a priority queue?

Elements are inserted into the array in sorted order based on their priority

What does public float front() in the array implementation of priority queue do?

Return the element with the hightest priority

What does public float dequeue() in array implementation of priority queues do?

Removes and returns the element with the highest priority

Summary of behaviour of priority queues

In priority queues, elements are dequeued according to their priority and their current queue position.