Friday, August 4, 2023

How to use Deque Data Structure in Java? Example Tutorial

Hello friends, I am really glad to see you all again here. And I know you are here to learn new and valuable Java concepts and continue your journey on Java. Today we are gonna learn something that is really important logically. yes! you heard right, we are going to learn about Deque data structure in Java and how to use Deque in the Java program. Deque is a special data structure, a double-ended queue that allows you to process elements at both ends, I mean you can add and remove objects from both front and rear end. It's a short form of Double-Ended Queue and pronounced as "Deck".  

The difference between a Queue and Deque is that you can only add elements from the rear end on Queue but you can add elements on both the front and rear end on Deque.

That's the main purpose of Dequeue but we will go deeper in this article to not only teach you what is Deque but how and when to use Deque in Java.   So, what's the wait? Let's start! But, as usual, before jumping into what today's topic is, Let's first understand its need using a scenario. (yeah I know scenarios are the best :p). 

Consider you want to implement a ticket counter. People can enter the queue from the end and will be removed from the front. And, for implementing this scenario, the data structure we would use will be a Queue data structure, right? Pretty easy eh? Wait, Now let's observe a scenario once more.

 You enter the queue and buy a ticket. After buying the ticket, you walk away. But, it was not so late that you found there's a discrepancy in your name printed on the ticket. (A classic ticket counter mistake!)

Now, what will you do? As you have already bought the ticket, you are not gonna wait through the queue once more, right? You will directly go to the ticket counter and will check for the discrepancy. But did you guys observe anything through this scenario?

Take 2 minutes and think about something related to Queue.

If you guys observed, you entered the Queue a second time from the front! But that operation is not supported in a Queue right? So, basically, we need a Queue that has the functionality to insert not from only the back, but from the front too. 

Now, suppose during all these, a person from the back is frustrated and leaves the Queue. he's allowed to leave. But, he did this from the back! Again, our simple Queue is not able to handle this. Now, we have our requirements. 

We need to Queue, which can insert, and delete elements from both front and back. For doing this, you don't need to implement all of these yourself. once again Java is here to help you!

This is where the concept of Deque comes! As you all guys would know, a Queue can be implemented using a Linked List. but for those who need more clarification, No worries, I am here to help you today!

Let's understand Deque from scratch then.

1. Linked List Data Structure

The Linked List data structure is a linear data structure that has elements/objects stored in a linear fashion. A singly Linked List is represented below. Head refers to the first node in the Linked List. A single Linked List node has 2 fields attached with it, data and pointer where each pointer points to the next node of the list.




2. Doubly Linked List Data Structure

A doubly linked list is a list where each node in the list has a data field and 2 pointer fields. One pointer points to the previous node and the other pointer point to the next node.

 


3. Unbounded Queue backed by a Linked List:

A queue is a data structure that provides first in first out (FIFO) ordering in a respect to its elements. An unbounded queue is a queue in which size limitations are not given.

This type of queue can be implemented by a linked list as the linked list does not reside in contiguous memory space, and can theoretically grow/shrink dynamically based on the number of elements in the queue.

The benefit of an unbound implementation of a queue is that it takes no memory when there are no elements in it.

Now it must be clear why a linked list is used to represent an unbounded queue. Similarly, a linked list can be used to represent an unbounded stack for similar reasons as the queue mentioned above.



4. Deque Data Structure in Java

A deque is a double-ended queue where we can add, update or delete elements from both ends. A queue can be implemented using a linked list where the elements are first inserted is removed first (FIFO).

A singly linked list can be used to implement an unbounded queue and a doubly linked list can be used to implement a deque.

So let’s discuss its major operations.
        How to use Deque in Java? Example Tutorial


Deque methods:
Here are some important method of Dequeue data structure in Java:
  • insertFront() : adds an item at the front of the deque
  • insertLast() : adds an item at the end of the deque
  • deleteFront() : deletes an item from the front of deque
  • deleteLast() : deletes an item from the end of deque
  • getFront() : gets the front element from deque
  • getRear() : gets the rear/last item from the deque

Now, Let's understand how Deque can be implemented using a code and implementation.





5. Java Deque Example Program

Here is our complete Java Program to demonstrate how to use the Deque collection class in Java. In this program, we have used ArrayDeque as the implementation of Deque. Remember, Dequeue allows you to insert and delete objects at both ends and that's what is shown in this example.

You can add at the first or front using the addFirst() method and add element at the rear end using the add() method. Similarly, you can remove elements from front end using removeFirst() method in Java.  


import java.util.ArrayDeque;
import java.util.Deque;


public class DequeDemo extends Thread{

    public static Deque<Integer> deque;

    public static void main(String[] args) throws InterruptedException {
        deque = new ArrayDeque<>();

        //add at last
        deque.add(1);
        //deque : 1

        //add at first
        deque.addFirst(3);
        //deque : 3 -> 1

        //add at last
        deque.addLast(2);
        //deque: 3 -> 1 -> 2

        //add at last
        deque.add(4);
        //deque : 3 -> 1 -> 2 -> 4

        //remove at first
        deque.removeFirst();
        //deque : 1 -> 2 -> 4

        deque.forEach(a -> System.out.print(a+"->"));
        System.out.println();

    }
}


Let's see how the output will look like.

Output:
What is Deque and when to use Deque in Java



Now, you all must be wondering, this is it! this is the messiah! :p But before moving on, let's check another scenario.


6. Limitations of Deque in Java

There are some limitations of Deque when considering a multi-threaded environment. Consider a scenario. Consider 3 threads simultaneously working on a Deque and both threads want to add an element at the 4th index.

Consider a Deque where thread A and thread B both try to put an element at 4th position.

Thread A wants to insert value 7 and thread B wants to insert value 9. Whichever thread accesses the deque first will put a value. Let’s say thread B first puts a value of 9 and then thread A comes and alters that value to 7.

Now, thread A knows that the value is 7 but thread B still thinks that the value is 9. This is a classic case when one of the values gets lost due to a lack of safety during multi-threading. 

When you actually try to code this scenario using Deque, java will throw a ConcurrentModificationException when you try to modify the Deque simultaneously from multiple threads.

So, what's the solution to this? we will definitely discuss this in our next article.


Till then, Happy learning






Thanks for reading this article if you find these Java Deque examples
 useful then please share them with your friends and colleagues. If you 
have any questions or feedback then please drop me a note. 

P. S. -
 If you are new to Java and looking for a free course to 
learn Java in a structured way then you can also check this Java Tutorial for Complete Beginners(FREE) course
 on Udemy. It's fully online, free and more than 1.4 million developers have 
joined this course. You just need a free Udemy account to join the 
course. 
Posted by at
Labels: , ,

No comments:

Post a Comment

Feel free to comment, ask questions if you have any doubt.

Subscribe to: Post Comments (Atom)