Deque in java: Basics and Implementation

Dequeue

Dequeue Interface is resides in java.util package. It is a part of Collection.

Double Ended Queue. it allows us to add or remove elements from either the front or rear of the data structure.

DEQUEUE

Operations can be performed on dequeue 

1. Insertion
2. deletion
3. retrieval

Insertion

• push(element): this method will add an element in front of the deque. 
• add(element): this method will add an element in the rear of the deque.
• offer(element): this method works the same as add().

Deletion

• pop(element): removes first element of the dequeue.
• removeLast(element): as name suggest removes last element of the dequeue.
• poll(element): same as removeLast() removes first element of the dequeue.

Retrieval

• peek(): it retrieves the first element of the dequeue.
• peekLast(): it retrieves the last element of the dequeue.
• peekFirst(): same as peek().

Example(hackerearth)

Joe has recently got his new collection of sci-fi novels. He arranges all the books on a shelf. Because of his crazy rules, he only reads a book from one of the ends of the shelf. Thus, each book Joe reads is either leftmost or rightmost book from the shelf.

Joe cannot read a book if it has more than K chapters, again a crazy rule.

When Joe has read a book, he removes it from the shelf. Joe stops when he is unable to read any book from any end of the shelf.

How many books are still present on the shelf?

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class BookReading {

private static Scanner sc = new Scanner(System.in);

public static void main(String[] args) {
Deque<Integer> total_chapter_per_book = new LinkedList<Integer>();

int total_book = sc.nextInt();
int max_chapter = sc.nextInt();
for (int i = 0; i < total_book; i++)
total_chapter_per_book.add(sc.nextInt());
while (!total_chapter_per_book.isEmpty() && total_chapter_per_book.peekFirst() <= max_chapter)
total_chapter_per_book.removeFirst();
while (!total_chapter_per_book.isEmpty() && total_chapter_per_book.peekLast() <= max_chapter)
total_chapter_per_book.removeLast();
System.out.println(total_chapter_per_book.size());
}

}

Define The Deque

Deque<Integer> total_chapter_per_book = new LinkedList<Integer>();

Facebook Google Twitter More

• Pinterest
• Linkedin
• Tumblr

Posted by : Denes Vaghani January 13, 2020 Tags : Data Structure

Subscribe by Email

Follow Updates Articles from This Blog via Email