A deque is a double-ended-queue. A double-ended-queue is a linear collection of elements that supports the insertion and removal of elements at both end points. The Deque interface is a richer abstract data type than both Stack and Queue because it implements both stacks and queues at the same time.
The Deque interface defines methods to access the elements at both ends of the Deque instance. Methods are provided to insert, remove, and examine the elements.
Predefined classes like ArrayDeque and LinkedList implement the Deque interface.
Deque interface Methods
Note that the Deque interface can be used both as last-in-first-out stacks and first-in-first-out queues. The methods given in the Deque interface are divided into three parts:
Insert
The addfirst and offerFirst methods insert elements at the beginning of the Deque instance. The methods addLast and offerLast insert elements at the end of the Deque instance.
When the capacity of the Deque instance is restricted, the preferred methods are offerFirst and offerLast because addFirst might fail to throw an exception if it is full.
Remove
The removeFirst and pollFirst methods remove elements from the beginning of the Deque instance. The removeLast and pollLast methods remove elements from the end. The methods pollFirst and pollLast return null if the Deque is empty whereas the methods removeFirst and removeLast throw an exception if the Deque instance is empty.
Retrieve
The methods getFirst and peekFirst retrieve the first element of the Deque instance. These methods don't remove the value from the Deque instance. Similarly, the methods getLast and peekLast retrieve the last element.
The methods getFirst and getLast throw an exception if the deque instance is empty whereas the methods peekFirst and peekLast return NULL.
Type of Operation | First Element (Beginning of the Deque instance) | Last Element (End of the Deque instance) |
---|---|---|
Insert | addFirst(e) offerFirst(e) | addLast(e) offerLast(e) |
Remove | removeFirst() pollFirst() | removeLast() pollLast() |
Examine | getFirst() peekFirst() | getLast() peekLast() |
Deque interface Class Diagram
Below diagram shows a list of APIs/Methods that deque interface provides.
Deque interface Hierarchy Diagram
ArrayDeque implementation of Deque Interface Examples
Java ArrayDeque Example
import java.util.ArrayDeque;
import java.util.Deque;
public class ArrayDequeExample {
public static void main(String[] args) {
// Creating Deque and adding elements
Deque<String> deque = new ArrayDeque<String>();
deque.add("element1");
deque.add("element2");
deque.add("element3");
// Traversing elements
for (String str : deque) {
System.out.println(str);
}
}
}
Output:
element1
element2
element3
Java ArrayDeque Example: offerFirst() and pollLast()
package com.javaguides.collections.queueexamples;
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeExample {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<String>();
deque.offer("element1");
deque.offer("element2");
deque.add("element3");
deque.offerFirst("element4");
System.out.println("After offerFirst Traversal...");
for (String s : deque) {
System.out.println(s);
}
// deque.poll();
// deque.pollFirst();//it is same as poll()
deque.pollLast();
System.out.println("After pollLast() Traversal...");
for (String s : deque) {
System.out.println(s);
}
}
}
Output:
After offerFirst Traversal...
element4
element1
element2
element3
After pollLast() Traversal...
element4
element1
element2
package com.javaguides.collections.queueexamples;
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeExample {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<String>();
deque.offer("element1");
deque.offer("element2");
deque.add("element3");
deque.offerFirst("element4");
System.out.println("After offerFirst Traversal...");
for (String s : deque) {
System.out.println(s);
}
// deque.poll();
// deque.pollFirst();//it is same as poll()
deque.pollLast();
System.out.println("After pollLast() Traversal...");
for (String s : deque) {
System.out.println(s);
}
}
}
After offerFirst Traversal...
element4
element1
element2
element3
After pollLast() Traversal...
element4
element1
element2
Java ArrayDeque Example: Book Class
import java.util.ArrayDeque;
import java.util.Deque;
class Book {
int id;
String name, author, publisher;
int quantity;
public Book(int id, String name, String author, String publisher, int quantity) {
this.id = id;
this.name = name;
this.author = author;
this.publisher = publisher;
this.quantity = quantity;
}
}
public class ArrayDequeExample1 {
public static void main(String[] args) {
Deque<Book> set = new ArrayDeque<Book>();
// Creating Books
Book b1 = new Book(101, "Let us C", "Yashwant Kanetkar", "BPB", 8);
Book b2 = new Book(102, "Data Communications & Networking", "Forouzan", "Mc Graw Hill", 4);
Book b3 = new Book(103, "Operating System", "Galvin", "Wiley", 6);
// Adding Books to Deque
set.add(b1);
set.add(b2);
set.add(b3);
// Traversing ArrayDeque
for (Book b : set) {
System.out.println(b.id + " " + b.name + " " + b.author + " " + b.publisher + " " + b.quantity);
}
}
}
Output:
101 Let us C Yashwant Kanetkar BPB 8
102 Data Communications & Networking Forouzan Mc Graw Hill 4
103 Operating System Galvin Wiley 6
Comments
Post a comment