Skip to main content

ArrayDeque

java.util.ArrayDeque CLASS

tip

REFERENCE:~

caution

Sarthak Uses ArrayDeque to implement both Stack and Queue as ArrayDeque contains all the methods of Stack and Queue

  • ArrayDeque can be used to implement both LIFO and FIFO.

To Check: Collections methods can be used with ArrayDeque or not??!⁉️💣​

Relation between Deque & ArrayDeque​

note

As we mentioned before, Deque<E> extends Queue<E> and represents a queue where you can insert and remove elements from both ends. It combines access rules provided by queue (FIFO) and stack (LIFO) together.

The Deque interface provides methods for working with the first and the last element of a queue. Some of the methods throw an exception, while others just return a special value (null). Check out the table:

Since ArrayDeque and LinkedList implement this interface, they both can work as a queue (FIFO), a stack (LIFO), or a deque.

initialisation​

ArrayList to ArrayDeque​

  • using Collections.addAll()
// Collections.addAll(to_be_Name, from_Name);
Collections.addAll(ArrayDequeName, ArrayListName);
OR
  • using DataStructureName.addAll()
// to_name.addAll(from_name)
ArrayDequeName.addAll(ArrayListName);

Array to ArrayDeque​

caution

converting int to Integer using Integer.valueOf(arrayName) as only wrapper classes can be used in Collections Data Structures like - ArrayList, List, ArrayDeque.​

// TO DO

ArrayDeque methods as Deque​

ArrayDeque implements Deque.

  • A deque (usually pronounced “deck”) stands for double ended queue and is a combination of a stack and a queue, in that it supports O(1) insertions and deletions from both the front and the back of the deque. In Java, the deque class is called ArrayDeque. The four methods for adding and removing are offerFirst(), pollFirst(), offerLast(), and pollLast().

:::

caution

🤯 MUST KNOW!​

How to use offerFirst(), pollFirst(), offerLast(), pollLast(),peekLast() & peekFirst() for LIFO and FIFO operations as Stack and Queue​

  • For Stack as LIFO use offerLast() to input elements and pollLast() to print elements. or use offerFirst() to input elements and pollFirst() to print elements.. If

  • For Queue as FIFO use offerLast() to input elements and pollFirst() to print elements. or use offerFirst() to input elements and pollLast() to print elements.

  • Using Iterator methods without pollLast() or pollFirst() :~ For Stack as LIFO use offerFirst() to input elements and then iterate using hasNext() and next() methods of Iterator.

  • Using Iterator methods without pollLast() or pollFirst() :~ For Queue as FIFO use offerLast() to input elements and then iterate using hasNext() and next() methods of Iterator.

I recommend using ↴:

  • For Stack as LIFO use offerLast() to input elements and pollLast() to print elements.
  • For Queue as FIFO use offerLast() to input elements and pollFirst() to print elements.

offerFirst()​

info
// input is [ 45 5 89 65 625 165 ]
ArrayDeque<Integer> ad = new ArrayDeque<>();
while (sc.hasNext()) {
    ad.offerFirst(sc.nextInt());
}   // ArrayDeque becomes: [165, 625, 65, 89, 5, 45]

while (it.hasNext() && (ad.size() != 0)) {  // "!ad.isEmpty()" can be used instead of "ad.size() != 0"
    System.out.println(ad.pollLast());
}
/* It prints:
45
5
89
65
625
165 */

offerLast()​

info
// input is [ 45 5 89 65 625 165 ]
ArrayDeque<Integer> ad = new ArrayDeque<>();
while (sc.hasNext()) {
    ad.offerLast(sc.nextInt());
}   // ArrayDeque becomes: [45, 5, 89, 65, 625, 165]

while (it.hasNext() && !ad.isEmpty()) {  // "ad.size() != 0" can be used instead of "!ad.isEmpty()"
    System.out.println(ad.pollLast());
}
/* It prints:
165
625
65
89
5 */

pollFirst()​

caution

for-Each loop cannot be used with pollLast(). So Iterator must be used.

info
// input is [ 45 5 89 65 625 165 ]
ArrayDeque<Integer> ad = new ArrayDeque<>();
while (sc.hasNext()) {
    ad.offerFirst(sc.nextInt());
}   // ArrayDeque becomes: [165, 625, 65, 89, 5, 45]

Iterator<Integer> it = ad.iterator();
  // "ad.size() != 0" can be used instead of "!ad.isEmpty()"
while (it.hasNext() && !ad.isEmpty()) {  // to avoid printing "null" infinity times as "pollFirst()" shows this problem when "ArrayDeque" is used with "Iterator"
    System.out.println(ad.pollFirst());
}
/* It prints:
165
625
65
89
5 */
  • I use (ad.size() != 0) to avoid printing "null" infinity times as "pollFirst()" shows this problem when "ArrayDeque" is used with "Iterator"
  • This error only occurs when pollFirst, pollLast & poll are used with Iterator

pollLast()​

caution

for-Each loop cannot be used with pollLast(). So Iterator must be used.

info
// input is [ 45 5 89 65 625 165 ]
ArrayDeque<Integer> ad = new ArrayDeque<>();
while (sc.hasNext()) {
    ad.offerLast(sc.nextInt());
}   // ArrayDeque becomes: [45, 5, 89, 65, 625, 165]

Iterator<Integer> it = ad.iterator();
  // "!ad.isEmpty()" can be used instead of "ad.size() != 0"
while (it.hasNext() && (ad.size() != 0)) {  // to avoid printing "null" infinity times as "pollLast()" shows this problem when "ArrayDeque" is used with "Iterator"
    System.out.println(ad.pollLast());
}
/* It prints:
165
625
65
89
5 */
  • I use (ad.size() != 0) to avoid printing "null" infinity times as "pollFirst()" shows this problem when "ArrayDeque" is used with "Iterator"
  • This error only occurs when pollFirst, pollLast & poll are used with Iterator

peekFirst()​

peekLast()​

FIFO using offerLast() with hasNext() & next() ~ Iterator​

// input is [ 45 5 89 65 625 165 ]
ArrayDeque<Integer> ad = new ArrayDeque<>();
while (sc.hasNext()) {
  ad.offerLast(sc.nextInt());
} // ArrayDeque becomes: [45, 5, 89, 65, 625, 165]

Iterator<Integer> it = ad.iterator();

while (it.hasNext()) {
  System.out.println(it.next());
}
/* It prints:
45
5
89
65
625
165 */

LIFO using offerFirst() with hasNext() & next() ~ Iterator​

// input is [ 45 5 89 65 625 165 ]
ArrayDeque<Integer> ad = new ArrayDeque<>();
while (sc.hasNext()) {
  ad.offerFirst(sc.nextInt());
} // ArrayDeque becomes: [165, 625, 65, 89, 5, 45]

Iterator<Integer> it = ad.iterator();

while (it.hasNext()) {
  System.out.println(it.next());
}
/* It prints:
165
625
65
89
5
45 */

ArrayDeque methods as Stack​

pop()​

  • Acts similar to pop() in Stack as LIFO , the Last element inserted comes out First.
  • It returns the REVERSE ODER of the input
/* Input is: [45 5 89 65 625 165] */
ArrayDeque<Integer> ad = new ArrayDeque<>();
 while (sc.hasNext()) {
     ad.push(sc.nextInt());
 }      // ArrayDeque "ad" becomes: [165, 625, 65, 89, 5, 45]

for (int el : ad) {
    System.out.println(ad.pop());
}  /* It prints:
165
625
65
89
5
45 */
caution
  • ❎ On using pop() with Iterator, ArrayDeque shows an error☠️: 👇 BUT also prints as LIFO
  • ❎ On using remove() or poll() or pollLast() or pollFirst() (poll() or pollLast() or pollFirst() throws Infinite Null; not Recommended) with Iterator, ArrayDeque shows an error☠️: 👇 BUT also prints as FIFO
Exception in thread "main" java.util.NoSuchElementException
at java.base/java.util.ArrayDeque.removeFirst(ArrayDeque.java:362)
at java.base/java.util.ArrayDeque.pop(ArrayDeque.java:593) at Main.main(Main.java:33)
  • For pop() and remove() in Arraydeque ~ Iterator throws⏬:
NoSuchElementException
Exception in thread "main" java.util.NoSuchElementException at java.base/java.util.ArrayDeque.removeFirst(ArrayDeque.java:362) at java.base/java.util.ArrayDeque.pop(ArrayDeque.java:593) at Main.main(Main.java:33)
  • For poll() or pollLast() or pollFirst() in ArrayDeque ~ Iterator throws⏬:
prints "null" infinite times
prints `null` infinite times after alll the elements are finished printing.
/* Input is: [45 5 89 65 625 165] */
while (it.hasNext()) {
    if (ad.size() == 0) { // for avoiding the Error/Exception ↴
        break;           // "NoSuchElementException" occurs when the ArrayDeque becomes Empty
    }                   //  By checking the 'size()' for "0", we can avoid the Exception
    System.out.println(ad.pop());
}  /* It prints:
165
625
65
89
5
45 */
info

Instead of using pop(), I can simply use Iterator and its methods hasNext() & next();; just the trick is I will have to initialise:​

  • ArrayDeque as push() for Stack
  • ArrayDeque as offer() or add() for Queue

the add(E e) method does the same as offer(E e) but throws IllegalStateException if no space is currently available;

For pop() of Stack​

/* Input is: [45 5 89 65 625 165] */
ArrayDeque<Integer> ad = new ArrayDeque<>();
while(sc.hasNext()) {
    ad.push(sc.nextInt());
}   // ArrayDeque "ad" becomes: [165, 625, 65, 89, 5, 45]

Iterator<Integer> it = ad.iterator();

while (it.hasNext()) {
    System.out.println(it.next());
}   /* It prints:
165
625
65
89
5
45 */

For remove() of Queue​

/* Input is: [45 5 89 65 625 165] */
ArrayDeque<Integer> ad = new ArrayDeque<>();
while(sc.hasNext()) {
    ad.offer(sc.nextInt());     //"add()" can also be used but not recommended
}   // ArrayDeque "ad" becomes: [45, 5, 89, 65, 625, 165]

Iterator<Integer> it = ad.iterator();

while (it.hasNext()) {
    System.out.println(it.next());
}   /* It prints:
45
5
89
65
625
165 */