Java

TOPIC 22 – JAVA COLLECTIONS IV – QUEUES & STACKS

LESSON NOTE

INTRO - QUEUE

A queue is a data structure that holds items in a specific order. New items are always added to the end of the queue. You can only remove items from the front of the queue. This structure is designed to mimic a queue or lineup in the real world.

FIFO & LIFO

An element that is first in the queue, is first to get out of the queue. First in, first out. Or, FIFO.

Similarly, an element that is last in, is last to get out. Last in, last out. Or, LILO.

So a queue is said to be either FIFO or LILO.

IMPLEMENTATIONS

In Java, Queue is an interface. It is implemented by LinkedList. So, you can use a LinkedList as a Queue. Note that the ArrayList does not implement the Queue interface so it cannot serve as a Queue (unless you do extra work).

EXAMPLE CODE 1

Since LinkedList implements Queue, we can do the following:

Queue<Integer> q = new LinkedList<Integer>();

Note that the above approach will limit you to Queue functionality – which is probably what you want!

EXAMPLE CODE 2

We can also just use a LinkedList:

LinkedList<Integer> q = new LinkedList<Integer>();

This approach doesn’t limit you to only the Queue functionality however. You will also be able to use List functionality. So be careful if your teacher (who is very cool by the way) wants you to use only Queue functionality.

FUNCTIONALITY

Here are the most important methods for queue structures:

• add() – adds an element to the end of the queue
• poll() – gets and removes the value at the front of the queue
• peek() – gets the value at the front of the queue (but doesn’t remove it)
• size() – returns the number of elements in the queue
• isEmpty() – return true is the queue contains no elements

EXAMPLE CODE

Queue<Integer> q = new LinkedList<Integer>();

q.add(45);

q.add(24);

q.add(19);

System.out.println(q);

System.out.println("Removing:" + q.poll());

System.out.println(q);

q.poll(); //Removes, but no output

System.out.println(q);

q.add(93);

System.out.println(q);

System.out.println("At Front:" + q.peek()); //No removal

System.out.println(q);

OUTPUT RESULT

[45, 24, 19]

Removing:45

[24, 19]

[19]

[19, 93]

At Front:19

[19, 93]