Interface Deque (viết tắt của Double-Ended Queue) trong Java là một interface định nghĩa một cấu trúc dữ liệu cho phép chúng ta có thể thêm hoặc xoá các phần tử ở trước hoặc ở phía sau đó các bạn:
Interface Deque này extends từ interface Queue và nó có 2 implementation chính là ArrayQueue và LinkedList như sau:
Chúng ta có thể sử dụng Deque để implement :
- Stack với LIFO (Last In First Out): thêm phần tử và xoá phần tử từ front
- hay Queue với FIFO (First In First Out): thêm phần tử từ rear, xoá phần tử từ front
Để làm việc với Deque, các bạn có thể sử dụng một số phương thức của nó như sau:
Table of Contents
Phương thức addFirst() và addLast()
- addFirst(E e): thêm phần tử ở đầu.
- addLast(E e): thêm phần tử ở phía sau.
Ví dụ như sau:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
package com.huongdanjava.java; import java.util.ArrayDeque; import java.util.Deque; public class Application { public static void main(String[] args) { Deque<Integer> deque = new ArrayDeque<>(); deque.add(3); deque.addFirst(1); deque.addLast(2); deque.forEach(System.out::print); } } |
Phương thức add() cũng tương tự như phương thức addLast() các bạn nhé! Còn phương thức push() thì tương tự như phương thức addFirst()!
Trong ví dụ trên, ban đầu, deque của mình chỉ có phần tử là 3. Sử dụng phương thức addFirst() và addLast() mình có thể add thêm phần từ vào đầu và cuối. Kết quả như sau:
Phương thức offerFirst() và offerLast()
2 phương thức offerFirst() và offerLast() tương tự như 2 phương thức addFirst() và addLast() nhưng có điểm khác biệt là nếu collection của các bạn có capacity. Việc thêm phần tử mới có thể sẽ không được khi collection của các bạn đã full capacity.
- offerFirst(E e): thêm phần tử vào đầu, nếu không thêm được sẽ trả về false, ngược lại sẽ trả về true.
- offerLast(E e): thêm phần tử vào cuối, tương tự như offerFirst(), sẽ trả về về false nếu không thêm được, ngược lại sẽ trả về true.
Với 2 implementation ArrayQueue hay LinkedList, size của collection sẽ tự động tăng nên khi các bạn sử dụng 2 phương thức offerFirst() và offerLast(), kết quả sẽ luôn luôn trả về true các bạn nhé!
Ví dụ:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
package com.huongdanjava.java; import java.util.ArrayDeque; import java.util.Deque; public class Application { public static void main(String[] args) { Deque<Integer> deque = new ArrayDeque<>(1); deque.add(3); System.out.println(deque.offerFirst(1)); System.out.println(deque.offerLast(2)); deque.forEach(System.out::print); } } |
Kết quả:
Như các bạn thấy, mặc dù mình chỉ khởi tạo đối tượng ArrayDeque với capacity là 1, nhưng đối tượng này có thể tự động tăng capacity và lưu toàn bộ những phần tử mà mình thêm vào bằng các phương thức offer, không có lỗi gì xảy ra cả.
Phương thức removeFirst(), pollFirst(), removeLast() và pollLast()
2 phương thức removeFirst() và pollFirst() để có tác dụng remove và return phần tử ở đầu của collection. Điểm khác biệt là nếu không có phần tử nào để remove, removeFirst() sẽ throw java.util.NoSuchElementException, còn pollFirst() sẽ return lại giá trị null.
Tương tự thì phương thức removeLast() và pollLast() có tác dụng remove và return phần từ ở phía sau của collection. Điểm khác biệt cũng là nếu không có phần tử nào để remove, removeLast() sẽ throw java.util.NoSuchElementException, còn pollLast() sẽ return lại giá trị null.
Ví dụ:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
package com.huongdanjava.java; import java.util.ArrayDeque; import java.util.Deque; public class Application { public static void main(String[] args) { Deque<Integer> deque = new ArrayDeque<>(); deque.add(3); deque.add(2); System.out.println(deque.removeFirst()); System.out.println(deque.pollFirst()); System.out.println(deque.pollLast()); System.out.println(deque.removeLast()); deque.forEach(System.out::print); } } |
Kết quả:
Phương thức poll() cũng tương tự như phương thức pollFirst() các bạn nhé!
Phương thức getFirst(), peekFirst(), getLast() và peekLast()
Các phương thức getFirst() và peekFirst() sẽ chỉ return cho chúng ta phần tử ở front mà không remove phần tử đó. Điểm khác biệt cũng là nếu không có phần tử nào để return, getFirst() sẽ throw java.util.NoSuchElementException, còn peekFirst() sẽ return lại giá trị null.
Tương tự cho các phương thức getLast() và peekLast() các bạn nhé!
Ví dụ:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
package com.huongdanjava.java; import java.util.ArrayDeque; import java.util.Deque; public class Application { public static void main(String[] args) { Deque<Integer> deque = new ArrayDeque<>(); deque.add(3); System.out.println("getFirst: " + deque.getFirst()); System.out.println("getLast: " + deque.getLast()); System.out.println("peekFirst: " + deque.peekFirst()); System.out.println("peekLast: " + deque.peekLast()); deque.forEach(System.out::println); System.out.println("removeFirst: " + deque.removeFirst()); System.out.println("peekFirst: " + deque.peekFirst()); System.out.println("getLast:" + deque.getLast()); deque.forEach(System.out::print); } } |
Kết quả:
