Java Deque basic concepts and usage methods

In Java,Deque(Double-ended queue) is a queue that supports insertion and deletion at both ends. It is part of the Java Collections Framework, providing efficient dual-ended operation capabilities through interfaces and implementation classes.

Deque Basic Concept

• DequeyesDouble-ended queue, supports in queueheadandThe tailAdd, delete, access elements.
• It inherits fromQueueInterface is a more general data structure.
• Can be used asQueue (FIFO), can also be used asStack (LIFO)。

Interface definition

DequeIt is an interface, and the commonly used implementation classes are:

• ArrayDeque: A double-ended queue implementation based on dynamic arrays.
• LinkedList: A double-ended queue implementation based on a bidirectional linked list.

Common Operations Classification

• Head operation：addFirst、removeFirst、getFirst
• Tail operation：addLast、removeLast、getLast
• ​​​​​​​General Queue Operation：offer、poll、peek

Deque's method details

1. Add elements

Add in the head：

• void addFirst(E e): Insert an element at the head of the queue, and if the queue is full, an exception will be thrown.
• boolean offerFirst(E e): Insert element at the head of the queue, if the queue is full, returnfalse。

Add at the end：

• void addLast(E e): Insert an element at the end of the queue, and if the queue is full, an exception will be thrown.
• boolean offerLast(E e): Insert element at the end of the queue, if the queue is full, returnfalse。

Example:

Deque<Integer> deque = new ArrayDeque<>();
(1); // Add in the head(2);  // Add at the end(deque); // Output：[1, 2]

2. Delete elements

Delete from the head：

• E removeFirst(): Delete and return the header element. If the queue is empty, an exception will be thrown.
• E pollFirst(): Delete and return the header element, if the queue is empty, returnnull。

Delete from the tail：

• E removeLast(): Delete and return the tail element. If the queue is empty, an exception will be thrown.
• E pollLast(): Delete and return the tail element, if the queue is empty, returnnull。

Example:

Deque<Integer> deque = new ArrayDeque<>();
(1);
(2);
(); // Delete the header element();  // Delete the tail element(deque); // Output：[]

3. Access elements

Access head elements：

• E getFirst(): Get but not delete the head element. If the queue is empty, an exception will be thrown.
• E peekFirst(): Get but not delete the head element, if the queue is empty, returnnull。

Accessing the tail element：

• E getLast(): Get but not delete the tail element. If the queue is empty, an exception will be thrown.
• E peekLast(): Get but not delete the tail element, if the queue is empty, returnnull. Example:

Deque<Integer> deque = new ArrayDeque<>();
(1);
(2);
(()); // Output: 1(());  // Output：2

4. Stack Operation (LIFO)

• void push(E e): Push the element onto the top of the stack (equivalent toaddFirst）。
• E pop(): Remove and return the top element of the stack (equivalent toremoveFirst）。

Example:

Deque<Integer> stack = new ArrayDeque<>();
(1); // Push it into the top of the stack(2);
(()); // Pop up the top element of the stack, output: 2(()); // Output：1

5. Queue Operation (FIFO)

• boolean offer(E e): Add elements to the end of the queue (equivalent toofferLast）。
• E poll(): Remove and return the queue header element (equivalent topollFirst）。
• E peek(): Get but not delete the queue header element (equivalent topeekFirst）。

Example:

Deque<Integer> queue = new ArrayDeque<>();
(1); // Add to the end(2);
(()); // Remove the header element, output: 1(()); // Get header elements，Output：2

6. Delete all elements

• void clear(): Clear the queue.

Example:

Deque<Integer> deque = new ArrayDeque<>();
(1);
(2);
(); // Clear the queue(()); // Output：true

7. Check the queue status

• boolean isEmpty(): Check whether the queue is empty.
• int size(): Returns the number of elements in the queue.

Deque implementation class

1. ArrayDeque

• Based on dynamic arraysaccomplish.
• Features：
  • Suitable for use as stacks and queues.
  • Threads are unsafe, but more efficient.
  • Storage is not allowednullelement.

Example:

Deque<Integer> deque = new ArrayDeque<>();
(1);
(2);
(deque); // Output：[1, 2]

2. LinkedList

• Based on a two-way link tableaccomplish.
• Features：
  • Support queue and stack operations.
  • Allow storagenullelement.
  • Suitable for scenarios where frequent insertion and deletion operations are performed.

Example:

Deque<Integer> deque = new LinkedList<>();
(1);
(2);
(deque); // Output：[1, 2]

Common application scenarios

1. Stack Implementation (LIFO Mode)

Deque providespushandpopMethod, can easily simulate the stack.

Example:

Deque<Integer> stack = new ArrayDeque<>();
(1);
(2);
(()); // Output: 2(()); // Output：1

2. Queue Implementation (FIFO Mode)

Deque providesofferandpollMethod, can simulate queue operations.

Example:

Deque<Integer> queue = new ArrayDeque<>();
(1);
(2);
(()); // Output: 1(()); // Output：2

3. Sliding window

Deque can be used as a data structure for maintaining sliding windows, such as calculations for maximum or minimum values.

4. Dual-ended processing

Deque supports simultaneously processing data from both ends, such as algorithms that simultaneously access elements from the beginning and end (such as palindrome checking).

Summarize

Recommended usage scenarios

• For simple stack or queue operations, useArrayDeque。
• For frequent insertion, deletion or storage requirednullScenario, chooseLinkedList。

DequeIt is a powerful dual-ended data structure, which is very flexible in queue and stack operations. Just select the implementation class according to actual needs.

This is the end of this article about Java Deque’s detailed explanation. For more detailed explanations of Java Deque, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!