The Java Deque interface is a subtype of the Java Queue interface that provides a double-ended queue data structure. “Deque” stands for “double-ended queue.” A deque allows you to add or remove elements from both ends of the queue.
The Deque interface provides the following methods:
- addFirst(e): Adds the specified element at the beginning of the deque.
- addLast(e): Adds the specified element at the end of the deque.
- offerFirst(e): Adds the specified element at the beginning of the deque and returns true if successful.
- offerLast(e): Adds the specified element at the end of the deque and returns true if successful.
- removeFirst(): Removes and returns the first element of the deque. Throws NoSuchElementException if the deque is empty.
- removeLast(): Removes and returns the last element of the deque. Throws NoSuchElementException if the deque is empty.
- pollFirst(): Removes and returns the first element of the deque or null if the deque is empty.
- pollLast(): Removes and returns the last element of the deque or null if the deque is empty.
- getFirst(): Returns the first element of the deque without removing it. Throws NoSuchElementException if the deque is empty.
- getLast(): Returns the last element of the deque without removing it. Throws NoSuchElementException if the deque is empty.
- peekFirst(): Returns the first element of the deque or null if the deque is empty.
- peekLast(): Returns the last element of the deque or null if the deque is empty.
- removeFirstOccurrence(o): Removes the first occurrence of the specified element from the deque.
- removeLastOccurrence(o): Removes the last occurrence of the specified element from the deque.
- offer(e): Adds the specified element at the end of the deque and returns true if successful.
- add(e): Adds the specified element at the end of the deque. Throws an IllegalStateException if the deque is full.
- poll(): Removes and returns the first element of the deque or null if the deque is empty.
- remove(): Removes and returns the first element of the deque. Throws NoSuchElementException if the deque is empty.
- peek(): Returns the first element of the deque without removing it or null if the deque is empty.
- element(): Returns the first element of the deque without removing it. Throws NoSuchElementException if the deque is empty.
- size(): Returns the number of elements in the deque.
- iterator(): Returns an iterator over the elements in the deque.
The Deque interface is implemented by several classes in the Java Collections Framework, including ArrayDeque and LinkedList.
Deque Interface declaration:
The declaration of the Deque interface in Java is as follows:
public interface Deque<E> extends Queue<E> {
// Element insertion methods
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
// Element retrieval methods
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
// Element removal methods
boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);
// Queue methods
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
// Stack methods
void push(E e);
E pop();
// Collection methods
boolean remove(Object o);
boolean contains(Object o);
int size();
Iterator<E> iterator();
Iterator<E> descendingIterator();
// Other methods
boolean containsAll(Collection<?> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
}
The Deque interface extends the Queue interface and adds methods for inserting and retrieving elements from both ends of the deque. It also provides methods for removing elements, implementing a stack, and performing collection operations.
Methods of Java Deque Interface:
The Java Deque interface provides several methods for manipulating elements in the double-ended queue. Here are the methods provided by the Deque interface:
Element insertion methods:
void addFirst(E e): Inserts the specified element at the front of the deque. Throws an exception if the deque is full.void addLast(E e): Inserts the specified element at the end of the deque. Throws an exception if the deque is full.boolean offerFirst(E e): Inserts the specified element at the front of the deque and returnstrueif successful. Returnsfalseif the deque is full.boolean offerLast(E e): Inserts the specified element at the end of the deque and returnstrueif successful. Returnsfalseif the deque is full.
Element retrieval methods:
E removeFirst(): Removes and returns the first element of the deque. Throws an exception if the deque is empty.E removeLast(): Removes and returns the last element of the deque. Throws an exception if the deque is empty.E pollFirst(): Removes and returns the first element of the deque ornullif the deque is empty.E pollLast(): Removes and returns the last element of the deque ornullif the deque is empty.E getFirst(): Returns the first element of the deque without removing it. Throws an exception if the deque is empty.E getLast(): Returns the last element of the deque without removing it. Throws an exception if the deque is empty.E peekFirst(): Returns the first element of the deque ornullif the deque is empty.E peekLast(): Returns the last element of the deque ornullif the deque is empty.
Element removal methods:
boolean removeFirstOccurrence(Object o): Removes the first occurrence of the specified element from the deque.boolean removeLastOccurrence(Object o): Removes the last occurrence of the specified element from the deque.
Queue methods:
boolean add(E e): Inserts the specified element at the end of the deque. Throws an exception if the deque is full.boolean offer(E e): Inserts the specified element at the end of the deque and returnstrueif successful. Returnsfalseif the deque is full.E remove(): Removes and returns the first element of the deque. Throws an exception if the deque is empty.E poll(): Removes and returns the first element of the deque ornullif the deque is empty.E element(): Returns the first element of the deque without removing it. Throws an exception if the deque is empty.E peek(): Returns the first element of the deque ornullif the deque is empty.
Stack methods:
void push(E e): Inserts the specified element at the front of the deque.E pop(): Removes and returns the first element of the deque.
Collection methods:
boolean remove(Object o): Removes the first occurrence of the specified element from the deque.boolean contains(Object o): Returnstrueif the deque contains the specified element.int size(): Returns the number of elements in the deque.Iterator<E> iterator(): Returns an iterator over the elements in the deque.Iterator<E> descendingIterator(): Returns an iterator over the elements in the deque in reverse order.
Other methods:
boolean containsAll(Collection<?> c): Returnstrueif the deque contains all of the elements in the specified
ArrayDeque class:
In Java, the ArrayDeque class is a concrete implementation of the Deque interface that uses a resizable array to store elements. The ArrayDeque class provides a double-ended queue with no capacity restrictions, meaning that it can grow dynamically as needed to accommodate new elements.
The ArrayDeque class provides constant-time performance for the basic deque operations (addFirst, addLast, removeFirst, removeLast, getFirst, and getLast) as well as for the stack operations (push and pop).
Here’s an example of how to create an ArrayDeque and add elements to it:
ArrayDeque<Integer> deque = new ArrayDeque<>(); deque.addFirst(1); deque.addLast(2); deque.addFirst(3); deque.addLast(4); System.out.println(deque); // Output: [3, 1, 2, 4]
In this example, we create a new ArrayDeque instance of type Integer and add four elements to it using the addFirst and addLast methods. Finally, we print the contents of the deque using the System.out.println method.
Note that the ArrayDeque class is not thread-safe, so it should not be used in a multi-threaded environment without proper synchronization. If thread-safety is required, the ConcurrentLinkedDeque class can be used instead.
ArrayDeque Hierarchy:
In Java, the ArrayDeque class is part of the java.util package and is a concrete implementation of the Deque interface. It extends the AbstractCollection class and implements the Deque interface.
Here’s the class hierarchy for the ArrayDeque class:
java.lang.Object
java.util.AbstractCollection<E>
java.util.ArrayDeque<E>
As you can see, the ArrayDeque class is a direct subclass of the AbstractCollection class and implements the Deque interface. The AbstractCollection class provides a skeletal implementation of the Collection interface, which simplifies the process of creating custom collection classes that conform to the Collection interface.
The ArrayDeque class itself provides a resizable-array implementation of the Deque interface, with no capacity restrictions. It uses a circular buffer to store elements and can grow dynamically as needed to accommodate new elements. The ArrayDeque class provides constant-time performance for the basic deque operations and the stack operations.
Overall, the ArrayDeque class provides a powerful and flexible implementation of the Deque interface that can be used to build efficient and scalable data structures in Java.
ArrayDeque class declaration:
The ArrayDeque class in Java is declared in the java.util package and has the following class declaration:
public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable
As you can see, the class extends the AbstractCollection class and implements the Deque interface, as well as the Cloneable and Serializable interfaces.
The ArrayDeque class is a generic class, which means that it can be parameterized with a type parameter E to specify the type of elements that the deque can hold. For example, if you want to create an ArrayDeque of strings, you can create an instance of the ArrayDeque class with String as the type parameter, like this:
ArrayDeque<String> deque = new ArrayDeque<>();
This creates a new instance of ArrayDeque that can hold elements of type String.
Overall, the class declaration of ArrayDeque shows that it is a powerful and flexible class that provides efficient and scalable storage for elements in a double-ended queue. It can be used in a wide range of applications and provides a number of useful methods for manipulating and querying the deque.
Java ArrayDeque Example:
Here’s an example of how to use the ArrayDeque class in Java:
import java.util.ArrayDeque;
public class ArrayDequeExample {
public static void main(String[] args) {
// Create an empty deque
ArrayDeque<Integer> deque = new ArrayDeque<>();
// Add elements to the front and back of the deque
deque.addFirst(1);
deque.addLast(2);
deque.addFirst(3);
deque.addLast(4);
// Print the deque
System.out.println(deque); // Output: [3, 1, 2, 4]
// Get the first and last elements of the deque
int first = deque.getFirst();
int last = deque.getLast();
// Remove elements from the front and back of the deque
deque.removeFirst();
deque.removeLast();
// Print the deque again
System.out.println(deque); // Output: [1, 2]
// Check if the deque contains a specific element
boolean containsOne = deque.contains(1);
boolean containsThree = deque.contains(3);
// Print the results
System.out.println(containsOne); // Output: true
System.out.println(containsThree); // Output: false
}
}
In this example, we create a new ArrayDeque instance of type Integer and add four elements to it using the addFirst and addLast methods. We then print the contents of the deque using the System.out.println method.
We then use the getFirst and getLast methods to get the first and last elements of the deque, respectively. We remove elements from the front and back of the deque using the removeFirst and removeLast methods and print the contents of the deque again.
Finally, we use the contains method to check if the deque contains specific elements and print the results.
Java ArrayDeque Example: offerFirst() and pollLast():
Sure, here’s an updated example that demonstrates the use of offerFirst() and pollLast() methods in the ArrayDeque class:
import java.util.ArrayDeque;
public class ArrayDequeExample {
public static void main(String[] args) {
// Create an empty deque
ArrayDeque<Integer> deque = new ArrayDeque<>();
// Add elements to the front and back of the deque
deque.offerFirst(1);
deque.offerLast(2);
deque.offerFirst(3);
deque.offerLast(4);
// Print the deque
System.out.println(deque); // Output: [3, 1, 2, 4]
// Get the first and last elements of the deque
int first = deque.peekFirst();
int last = deque.peekLast();
// Remove elements from the front and back of the deque
deque.pollFirst();
deque.pollLast();
// Print the deque again
System.out.println(deque); // Output: [1, 2]
// Check if the deque contains a specific element
boolean containsOne = deque.contains(1);
boolean containsThree = deque.contains(3);
// Print the results
System.out.println(containsOne); // Output: true
System.out.println(containsThree); // Output: false
}
}
In this example, we use the offerFirst() method to add an element to the front of the deque and the offerLast() method to add an element to the back of the deque. We also use the peekFirst() and peekLast() methods to get the first and last elements of the deque, respectively.
We then use the pollFirst() method to remove the first element of the deque and the pollLast() method to remove the last element of the deque. Finally, we use the contains() method to check if the deque contains specific elements and print the results.
Note that the offerFirst() method is used instead of addFirst() to add an element to the front of the deque, and the pollLast() method is used instead of removeLast() to remove an element from the back of the deque. This is because the offerFirst() and pollLast() methods return false instead of throwing an exception when the deque is full or empty, respectively.
Java ArrayDeque Example: Book
Here’s an example of how you could use ArrayDeque to implement a bookshelf in Java:
import java.util.ArrayDeque;
public class Book {
private String title;
private String author;
private int yearPublished;
public Book(String title, String author, int yearPublished) {
this.title = title;
this.author = author;
this.yearPublished = yearPublished;
}
public String getTitle() {
return title;
}
public String getAuthor() {
return author;
}
public int getYearPublished() {
return yearPublished;
}
public String toString() {
return title + " by " + author + ", published in " + yearPublished;
}
public static void main(String[] args) {
// Create an empty bookshelf
ArrayDeque<Book> bookshelf = new ArrayDeque<>();
// Add books to the bookshelf
bookshelf.offerLast(new Book("The Great Gatsby", "F. Scott Fitzgerald", 1925));
bookshelf.offerLast(new Book("To Kill a Mockingbird", "Harper Lee", 1960));
bookshelf.offerLast(new Book("1984", "George Orwell", 1949));
bookshelf.offerLast(new Book("Pride and Prejudice", "Jane Austen", 1813));
// Print the bookshelf
System.out.println("My bookshelf contains the following books:");
for (Book book : bookshelf) {
System.out.println(book);
}
// Remove a book from the bookshelf
Book removedBook = bookshelf.pollFirst();
System.out.println("Removed the following book from the bookshelf:");
System.out.println(removedBook);
// Print the bookshelf again
System.out.println("My bookshelf now contains the following books:");
for (Book book : bookshelf) {
System.out.println(book);
}
// Check if the bookshelf contains a specific book
Book bookToFind = new Book("1984", "George Orwell", 1949);
boolean containsBook = bookshelf.contains(bookToFind);
System.out.println("Does my bookshelf contain " + bookToFind + "? " + containsBook);
}
}
In this example, we define a Book class with properties for the book’s title, author, and year of publication. We also define a toString() method to provide a string representation of a Book instance.
We then create an empty ArrayDeque to represent our bookshelf and add some books to it using the offerLast() method. We print the contents of the bookshelf using a for-each loop to iterate over the elements in the deque.
Next, we remove a book from the front of the deque using the pollFirst() method and print it out. We then print the contents of the bookshelf again to confirm that the book was removed.
Finally, we create a new Book instance to represent a book we want to find on the bookshelf, and use the contains() method to check if the bookshelf contains it. We print the result to the console.