Hướng dẫn và ví dụ Java Deque

Deque
Các phương thức của Deque
Examples

1. Deque

Deque là một từ viết tắt của "Double Ended Queue" (Hàng đợi hai đầu). Giống như những người đang xếp hàng tại siêu thị, chỉ người đứng đầu tiên và đứng ở vị cuối cùng được phục vụ. Deque cung cấp sự linh hoạt hơn một chút so với một hàng đợi thông thường.

public interface Deque<E> extends Queue<E>

Hướng dẫn và ví dụ Java Queue

Deque là interface con của Queue, nó cung cấp các phương thức để chèn một phần tử vào đầu hoặc cuối, và các phương thức để truy cập hoặc loại bỏ phần tử đầu hoặc phần tử cuối của nó.

Deque cũng bao gồm các phương thức cho phép nó hoạt động như một stack (Ngăn xếp) (Xem thêm giải thích trong bài viết).

Queue
BlockingDeque
BlockingQueue
TransferQueue
ArrayDeque
ConcurrentLinkedDeque
ConcurrentLinkedQueue
LinkedList
PriorityQueue
ArrayBlockingQueue
DelayQueue
LinkedBlockingQueue
LinkedBlockingDeque
PriorityBlockingQueue
SynchronousQueue
LinkedTransferQueue

2. Các phương thức của Deque

Methods of Deque

void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);

E removeFirst();
E removeLast();
E pollFirst();
E pollLast();

E getFirst();
E getLast();
E peekFirst();
E peekLast();

void push(E e);
E pop();

boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);

Iterator<E> descendingIterator();

// Methods inherited from Queue:

boolean add(E e);
boolean offer(E e);

E remove();
E poll();

E element();
E peek();

// Methods inherited from Collection:

boolean addAll(Collection<? extends E> c);  
boolean remove(Object o);
boolean contains(Object o);

int size();
Iterator<E> iterator();
...

Danh sách 12 phương thức đặc trưng của Deque:

Insert	addFirst(E)	offerFirst(E)	addLast(E)	offerLast(E)
Remove	removeFirst()	pollFirst()	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()

boolean addFirst(E) / boolean offerFirst(E)

boolean addFirst(E)	Chèn một phần tử vào phía trước của Deque, phương thức này sẽ ném ra ngoại lệ nếu sức chứa của Deque đã đầy. Phương thức trả về true nếu việc chèn thành công.
boolean offerFirst(E)	Chèn một phần tử vào phía trước của Deque. Nếu sức chứa của Deque đã đầy hoặc việc chèn không thì thành công phương thức sẽ trả về false, ngược lại trả về true.

Chú ý: Tuỳ thuộc vào kiểu Deque, nó có thể giới hạn (hoặc không giới hạn) số lượng phần tử.

boolean addLast(E) / boolean offerLast(E)

boolean addLast(E)	Chèn một phần tử vào phía cuối của Deque, phương thức này sẽ ném ra ngoại lệ nếu sức chứa của Deque đã đầy. Phương thức trả về true nếu việc chèn thành công.
boolean offerLast(E)	Chèn một phần tử vào phía cuối của Deque. Nếu sức chứa của Deque đã đầy hoặc việc chèn không thì thành công phương thức sẽ trả về false, ngược lại trả về true.

E removeFirst() / E pollFirst()

E removeFirst()	Trả về phần tử đầu tiên của Deque đồng thời loại bỏ nó ra khỏi Deque. Phương thức này sẽ ném ra ngoại lệ nếu *Deque* không có phần tử nào.
E pollFirst()	Trả về phần tử đầu tiên của Deque đồng thời loại bỏ nó ra khỏi Deque. Phương thức này sẽ trả về null nếu Deque không có phần tử nào.

E removeLast() / E pollLast()

E removeLast()	Trả về phần tử cuối cùng của Deque đồng thời loại bỏ nó ra khỏi Deque. Phương thức này sẽ ném ra ngoại lệ nếu *Deque* không có phần tử nào.
E pollLast()	Trả về phần tử cuối cùng của Deque đồng thời loại bỏ nó ra khỏi Deque. Phương thức này sẽ trả về null nếu Deque không có phần tử nào.

E getFirst() / E peekFirst()

E getFirst()	Trả về phần tử đầu tiên của Deque nhưng không loại bỏ nó ra ra khỏi Deque. Phương thức này ném ra ngoại lệ nếu *Deque* không có phần tử nào.
E peekFirst()	Trả về phần tử đầu tiên của Deque nhưng không loại bỏ nó ra ra khỏi Deque. Phương thức này trả về null nếu Deque không có phần tử nào.

E getLast() / E peekLast()

E getLast()	Trả về phần tử cuối cùng của Deque nhưng không loại bỏ nó ra ra khỏi Deque. Phương thức này ném ra ngoại lệ nếu *Deque* không có phần tử nào.
E peekLast()	Trả về phần tử cuối cùng của Deque nhưng không loại bỏ nó ra ra khỏi Deque. Phương thức này trả về null nếu Deque không có phần tử nào.

Methods inherited from Queue:

Các phương thức thừa kế từ Queue và các phương thức tương ứng trong Deque:

booleanadd(E)	booleanaddLast(E)	(*)
booleanoffer(E)	booleanofferLast(E)	(*)
E remove()	E removeFirst()
E poll()	E pollFirst()
E element()	E getFirst()
E peek()	E peekFirst()

(*) - Trong hầu hết các kiểu Queue, 2 phương thức add(E) và offer(E) sẽ chèn phần tử vào cuối. Nhưng điều này không đúng với PriorityQueue, vì PriorityQueue chỉ định vị trí của phần tử được chèn vào dựa trên độ ưu tiên của phần tử.

Hướng dẫn và ví dụ Java PriorityQueue

Stack?

Deque có thể hoạt động như một stack (Ngăn xếp), vì nó cung cấp các phương thức để hoạt động theo cơ chế LIFO (Last In First Out) (Phần tử thêm vào lần cuối sẽ được lấy ra đầu tiên).

boolean push(e)	boolean addFirst(e)
E pop()	E removeFirst()
E peek()	E getFirst()

3. Examples

Deque là một interface vì vậy để tạo ra đối tượng Deque bạn phải sử dụng một trong các lớp con của nó, chẳng hạn ArrayDeque, ConcurrentLinkedDeque, LinkedList, LinkedBlockingDeque.

Deque<String> deque = new ArrayDeque<>();

Deque<String> deque = new LinkedList<>();

Lớp Customer sẽ tham gia vào các ví dụ:

Customer.java

package com.o7planning.deque.ex;

public class Customer {
    private Integer cusId;
    private String cusName;
    
    public Customer(Integer cusId, String cusName) {
        super();
        this.cusId = cusId;
        this.cusName = cusName;
    }
    public Integer getCusId() {
        return cusId;
    }
    public String getCusName() {
        return cusName;
    }
}

DequeEx1.java

package com.o7planning.deque.ex;

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeEx1 {

    public static void main(String[] args) {
        
        // Create a Deque with maximum capacity of 10 elements.
        Deque<Customer> deque = new ArrayDeque<Customer>(10);
        
        deque.addFirst(new Customer(1, "Tom"));
        deque.addFirst(new Customer(2, "Jerry"));
        deque.addLast(new Customer(3, "Donald"));
        
        Customer current = null;
        
        // Retrieve first element and remove it from Deque.
        while((current = deque.pollFirst())!= null) {
            System.out.println("Serving customer: " + current.getCusName());
        }
    }
}

Output:

Serving customer: Jerry
Serving customer: Tom
Serving customer: Donald

Deque có thể được sử dụng như một stack (ngăn xếp), hãy xem một ví dụ mô phỏng các lá bài (cards):

DequeStackEx1.java

package com.o7planning.deque.ex;

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

public class DequeStackEx1 {

    public static void main(String[] args) {
        // Create a Deque to use as a Stack.
        Deque<String> stackOfCards = new LinkedList<>();

        // Pushing new items to the Stack
        stackOfCards.push("Jack");
        stackOfCards.push("Queen");
        stackOfCards.push("King");
        stackOfCards.push("Ace");

        System.out.println("Stack => " + stackOfCards);
        System.out.println();
 
        // Popping items from the Stack
        String cardAtTop = stackOfCards.pop();  // Throws NoSuchElementException if the stack is empty
        System.out.println("Stack.pop() => " + cardAtTop);
        System.out.println("Current Stack => " + stackOfCards);
        System.out.println();

        // Get the item at the top of the stack without removing it
        cardAtTop = stackOfCards.peek();
        System.out.println("Stack.peek() => " + cardAtTop);
        System.out.println("Current Stack => " + stackOfCards);
    }
}