Discuss the queue data structure. What is it? How can it be used? What support e

Question

Discuss the queue data structure.

What is it?

How can it be used?

What support exists for queues in the Java Class Library Collections Framework? Do you think this support is easy to understand and use? Why or why not?

Discuss the pros and cons of creating your own queue classes vs. using those provided by the Java Class Library Collections Framework. Make sure you take into consideration the ability to handle any kind of objects (generics).

What is a priority queue? How does it differ from a regular queue? Give an example of a use for a priority queue.

Explanation / Answer

Queue is a collection of items which are processed in FIFO (i.e First In First Out) order.
As items are processed in the order in which they arrive. A queue data structure should at minimum support
the following operations -
add /enque : to add item to queue
remove / deque : remove an item from queue
peek : look at the item in front of queue without removing it.

In computer science, queues are useful where ever order needs to be maintained. For example,
in FCFS CPU Scheduling (First Come First Serve), the processes that arrive first will be
processed first. So to maintain the order, we can use a queue.

In Java, the Collection interfaces / classes can be found in java.util package.
To support queue data structure, Java provides interface Queue<E> and also implementation classes
such as AbstractQueue, LinkedList in the java.util.package.

The support is easy to understand since all implementation details are not needed and only the
interface need to be understood. The Queue<E> interface shows what functionalities will be provided
and there are different implementations for different types of queues.

We can use the existing Queue implementation classes given by Java collections framework. But for the
sake of understanding how we could provide different implementations , we can implement a array based queue,
or a linked list based queue ourself.

Also Java Collections are generic. So its easy to make a queue of Integers or Strings or even any complex
class type like Process. The data stored in the queue is different but the functionality of queue is the same.

A priority queue is similar to regular queue, but here each element has an associated priority. So an element
with higher priority is processed before an element with lower priority. And if 2 elements with same priority
exist, then they are processed according to their order in the queue. For example in CPU Scheduling, the shortest
job first algorithm, the job with shortest execution time is processed first even if there are other jobs .
So here jobs are given priority based on their execution times.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.