A Queue is another data structure that operates with many similar functions as Lists do, but with a key difference. In a List (as in an array—either with arr[37] or list.get(41) or whatever you want), it’s easy to get to any particular element and do something with it: check its value, change its value, remove it, add it, and so on.
But a queue is different. A queue is, really, just an implementation of “I’m in
line at the grocery store to check out, and there’s an order of the people who
got here.” Social norms dictate that the cashier only helps the first person in
line—the person who has been in line longer than anyone else. They got there
because the person ahead of them cleared the queue, and the person before that
cleared before them, and the person before that, and so on.
The line only shrinks from the cashier end of the line, and only grows from the
back end of the line. The longer you’ve been in line, the sooner you’ll get the
cashier’s attention. If you just arrived, you have to wait for everyone ahead of
you. Jumping ahead (technically possible with real people) is not allowed with
a Queue.
Queues implement the “first-in-first-out” principle, which
we call “FIFO” for short. (There is also a “LIFO”—you may have guessed “last-in-first-out”—structure
called a Stack. We’ll cover it very soon.)
To add to a queue, you use add(). Queues are like Lists—they take generics, so
you make a Queue<Puppy> to store a queue of (only) Puppy objects, or Queue<Student>
to store a queue of Student objects. To remove from a queue, you use remove(). Under
certain circumstances, you may remove with poll().
You may not want to outright add or remove an element, just look at something—remember,
only the front element is visible—and, to do this (again, only for the front
element), you can use poll().
Look at this example:
import java.util.Queue;
import java.util.LinkedList;
public class QueueExample {
public static void
main(String[] args) {
// Create a
queue using LinkedList
Queue<Integer> queue = new LinkedList<>();
// Enqueue
(add) elements to the queue
queue.offer(1); // offer() is
preferred for adding elements
queue.offer(2);
queue.offer(3);
System.out.println("Queue: " + queue);
// Dequeue
(remove) the front element
int
removedItem = queue.poll();
System.out.println("Removed element: " + removedItem);
System.out.println("Queue after dequeue: " + queue);
}
}
Adding an element is called “enqueueing,” and removing is also called “dequeueing.”
Notice the declaration Queue<Integer> queue = new LinkedList<>();.
What does that tell us? Recall from our discussion of inheritance that this is
valid, if and only if (and this is true), a Queue is implemented as a LinkedList,
since every Queue is a LinkedList, but not every LinkedList is a Queue.
On account of this, the element indexed 0—the “first” element—is the element at
the head of the queue, or, the next one to be processed (the person being checked
out by the cashier in our earlier story). The highest index in the queue,
therefore, lies at the opposite end, at the tail of the queue.
This queue we have shown here is the simplest kind of queue. Later, we’ll get
to a more specialized queue called a priority queue. Priority queues aren’t
that much different, so don’t be too scared; in essence, they keep elements in
the proper order, by some priority (“keep the seniors above the juniors above
the sophomores above the freshmen”; or “keep the oldest people at the back of
the queue.”)
The general queue imposes no such restriction, and you’re free to enqueue and
dequeue as much as you want—add 3 things, remove 1, add 57, remove 48, add 1,
take away 2, and so on—without messing with order.
Play around with building your own queue of an object of your choice (or the wrapper
classes of primitives like Integer for integers), and have fun enqueueing and
dequeing.
No comments:
Post a Comment