Зміст курсу
Java Data Structures
Java Data Structures
Queue
Let's talk about two quite interesting data structures - Queue
and Deque
.
Queue
Let's start with a Queue
. Imagine a queue in a store during a sale. There are 10 people; the first person is closer to the store doors than the others, and the 10th person is farthest away. When the first person enters the store, it exits the queue, thereby shifting the entire queue forward by one person. The Java Queue
operates on a very similar principle.
This way, we can implement various programs where the queue logic is well-thought-out. For example, implementing a board with plans and tasks.
But first, let's take a look at the basic methods for working with a Queue
.
Queue
is an interface from which the LinkedList
class inherits, which you are already familiar with, so we will use this implementation.
Note
Note that a class implementation (such as
LinkedList
) can inherit from certain interfaces and implement methods of these interfaces.
This way, we use the interface as the object's type, but the object's implementation will be LinkedList
because it is a specific implementation of this object. (Remember that we cannot create objects based on an interface, right?)
Example:
example
// `LinkedList` as implementation of the `List` interface: List<T> list = new LinkedList<>(); // `LinkedList` as implementation of the `Queue` interface: Queue<T> queue = new LinkedList<>();
This way, we can make our application very flexible by using various implementations of the same interface.
But let's get back to the methods of working with Queue
.
Methods
Some key methods of the Queue interface are:
add(element)
: Adds an element to the queue, throwing an exception if the operation is not possible;offer(element)
: Adds an element to the queue, returningtrue
if successful orfalse
otherwise.
You can notice that these methods essentially do the same thing. However, the key difference is the safety of the offer
method. In case of an improperly added element, the offer
method won't throw an exception and won't halt the program's execution.
But at the moment, this feature is not of great interest to us, as a regular Queue
is not limited. However, there is a structure called BlockingQueue
, which has a restriction on the number of elements; in that case, these methods will have a noticeable difference.
Let's look at an example:
main
package com.example; import java.util.concurrent.BlockingQueue; import java.util.concurrent.LinkedBlockingQueue; public class Main { public static void main(String[] args) { BlockingQueue<String> queue = new LinkedBlockingQueue<>(2); queue.add("One"); queue.add("Two"); queue.add("Three"); System.out.println("Queue: " + queue); } }
As you can see, when using the add()
method and trying to add an element that doesn't fit into the queue, the program throws an error, unexpectedly terminating the execution. Let's try the same operation but with a safer method - offer()
:
main
package com.example; import java.util.concurrent.BlockingQueue; import java.util.concurrent.LinkedBlockingQueue; public class Main { public static void main(String[] args) { BlockingQueue<String> queue = new LinkedBlockingQueue<>(2); queue.offer("One"); queue.offer("Two"); queue.offer("Three"); System.out.println("Queue: " + queue); } }
As you can see, now the element didn't get added to the queue, but it also didn't throw an exception. So, we can consider that we gracefully handled the error. We can handle exceptions differently using a structure like try-catch
, but we'll discuss that later.
Note
Data structures like
BlockingQueue
,BlockingDeque
, and similar ones are in thejava.util.concurrent
package and used for multithreaded programming. We will learn about Java multithreading in future courses.
Let's move on to the next methods:
Removal methods
remove()
: Removes and returns the element from the beginning of the queue, throwing an exception if the queue is empty;poll()
: Removes and returns the element from the beginning of the queue, returning null if the queue is empty.
These methods precisely perform the function as if the first person in the queue entered the store and left the queue. This is where the FIFO (First In, First Out) principle comes into play. In other words, the element that was added first to the queue will be the first one removed.
Here, you can also observe the difference between these two methods. The poll()
method is used more often than the delete()
method because it is safer and does not throw exceptions.
Let's take a look at an example:
main
package com.example; import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { Queue<String> queue = new LinkedList<>(); queue.offer("One"); System.out.println("Queue: " + queue); queue.remove(); queue.remove(); System.out.println("Queue after removal operation: " + queue); } }
As you can see, the program throws a NoSuchElementException
because we are trying to remove an element from an empty queue.
To avoid such an exception, it's better to use the poll()
method:
main
package com.example; import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { Queue<String> queue = new LinkedList<>(); queue.offer("One"); System.out.println("Queue: " + queue); queue.poll(); queue.poll(); System.out.println("Queue after removal operation: " + queue); } }
Now, we have safely removed an element from the queue, and no exception was thrown when we tried to remove an element from an empty list. Cool!
The poll()
returning null
feature can be used, for example, in a while()
loop.
Let's look at an example:
main
package com.example; import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { Queue<String> queue = new LinkedList<>(); queue.offer("One"); queue.offer("Two"); queue.offer("Three"); queue.offer("Four"); queue.offer("Five"); System.out.println("Queue: " + queue); while (queue.poll() != null) { queue.poll(); } System.out.println("Queue after removal operation: " + queue); } }
This way, we can remove all elements from the queue using a loop. Remember that the first element that entered the queue is the one removed! For example, in the case of the above example, the element with the data "One"
was removed first. The FIFO principle is demonstrated below:
main
package com.example; import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { Queue<String> queue = new LinkedList<>(); queue.offer("One"); queue.offer("Two"); queue.offer("Three"); queue.offer("Four"); queue.offer("Five"); System.out.println("Queue: " + queue); queue.poll(); System.out.println("Queue after removal operation: " + queue); } }
Great, we can move on to the methods that return the first and last elements:
element()
: Returns, but does not remove, the element from the beginning of the queue, throwing an exception if the queue is empty;peek()
: Returns, but does not remove, the element from the beginning of the queue, returning null if the queue is empty.
Well, I think I don't need to explain for the third time that using the peek()
method is much better, as it is safer and won't throw an exception.
Let's look at an example of usage:
main
package com.example; import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { Queue<String> queue = new LinkedList<>(); queue.offer("One"); queue.offer("Two"); queue.offer("Three"); System.out.println("Queue: " + queue); System.out.println("The first element in the queue: " + queue.peek()); System.out.println("Queue after the `peek()` method: " + queue); } }
You can combine this method with other queue methods. For example, if we have a queue with five elements and we need to remove all elements until the fourth one(inclusive), let's look at the implementation of such an operation:
main
package com.example; import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { Queue<String> queue = new LinkedList<>(); queue.offer("One"); queue.offer("Two"); queue.offer("Three"); queue.offer("Four"); queue.offer("Five"); System.out.println("Queue: " + queue); while (!queue.peek().equals("Four")) { queue.poll(); } queue.poll(); System.out.println("Queue after removal operation: " + queue); } }
We used a loop with a condition based on the peek()
method. We can significantly optimize this loop by using the contains()
method. This method returns true
if the specified element is present in the queue and false
if it is not.
Let's improve the above code:
main
package com.example; import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { Queue<String> queue = new LinkedList<>(); queue.offer("One"); queue.offer("Two"); queue.offer("Three"); queue.offer("Four"); queue.offer("Five"); System.out.println("Queue: " + queue); while (queue.contains("Four")) { queue.poll(); } System.out.println("Queue after removal operation: " + queue); } }
Here, we set a single condition for the while loop. We successfully managed to remove all elements up to and including the "Four" element.
In the next chapters, you will learn about another similar data structure - Deque
, and also write your own implementation of a Task Manager
application.
Дякуємо за ваш відгук!