Java collections framework: Queue interface và lớp LinkedList

1. Queue interface trong Java

Queue interface cho phép lưu trữ và xử lý cấu trúc dữ liệu queue. Các bạn nên đọc lại bài Hàng đợi (queue) là gì? Cách xây dựng hàng đợi để hiểu về cơ chế FIFO (First In First Out) của Queue. Queue interface kế thừa từ Collection interface.

Các lớp kế thừa Queue interface

Để sử dụng Queue, chúng ta cần import java.util.Queue.

// LinkedList implementation of Queue
Queue<String> animal1 = new LinkedList<>();

// Array implementation of Queue
Queue<String> animal2 = new ArrayDeque<>();

// Priority Queue implementation of Queue
Queue<String> animal 3 = new PriorityQueue<>();

Trong ví dụ trên, chúng ta tạo ra các đối tượng animal1, animal2 và animal3 của các lớp LinkedList, ArrayDeque và PriorityQueue. Những đối tượng này có thể sử dụng các hàm được kế thừa từ Queue interface.

Những phương thức của Queue interface

Queue interface bao gồm tất cả phương thức của Collection interface. Queue interface còn có những phương thức khác:

• add() thêm một phần tử vào Queue. Nếu thêm được thì sẽ trả về true, ngược lại sẽ gây ra exception.
• offer() thêm một phần tử vào Queue. Nếu thêm thành công thì sẽ trả về true, ngược lại sẽ trả về false.
• element() trả về phần tử đầu (head) của Queue, sẽ gây ra exception nếu Queue rỗng.
• peek() trả về phần tử đầu (head) của Queue, sẽ trả về null nếu Queue rỗng.
• remove() trả về và xóa phần tử đầu (head) của Queue, sẽ gây ra exception nếu Queue rỗng.
• poll() trả về và xóa phần tử đầu (head) của Queue, sẽ trả về null nếu Queue rỗng.

2. Lớp LinkedList trong Java

Lớp LinkedList giúp lưu trữ và xử lý danh sách liên kết kép (Doubly Linked List). Các bạn có thể đọc bài Xây dựng danh sách liên kết kép (Doubly Linked List) với con trỏ (pointer) để hiểu rõ về danh sách liên kết kép.

LinkedList kế thừa từ List, Queue và Deque interface.

Tạo một LinkedList trong Java

LinkedList<Type> linkedList = new LinkedList<>();

Trong đó, linkedList là tên của LinkedList được tạo ra. Type là kiểu dữ liệu của các phần tử trong LinkedList. Lưu ý: Không thể dùng các kiểu dữ liệu nguyên thủy cho LinkedList mà phải sử dụng Wrapper Class. Ví dụ:

// create Integer type linked list
LinkedList<Integer> linkedList = new LinkedList<>();

// create String type linked list
LinkedList<String> linkedList = new LinkedList<>();

Thêm các phần tử vào LinkedList

Sử dụng hàm add() để thêm các phần tử vào LinkedList.

import java.util.LinkedList;
class Main {
  public static void main(String[] args){
    //tạo linkedlist
    LinkedList<String> animals = new LinkedList<>();

    //thêm phần tử vào linkedlist
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);

    //thêm phần tử vào linkedlist ở một ví trị xác định
    animals.add(1, "Horse");
    System.out.println("Updated LinkedList: " + animals);
  }
}

Kết quả

LinkedList: [Dog, Cat, Cow]
Updated LinkedList: [Dog, Horse, Cat, Cow]

Truy cập các phần tử trong LinkedList

Sử dụng hàm get() để truy cập các phần tử trong LinkedList.

import java.util.LinkedList;
class Main {
  public static void main(String[] args){
    //tạo linkedlist
    LinkedList<String> animals = new LinkedList<>();

    //thêm phần tử vào linkedlist
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);

    //lấy phần tử trong linkedlist
    String str = animals.get(1);
    System.out.print("Element at index 1: " + str);
  }
}

Kết quả

LinkedList: [Dog, Cat, Cow]
Element at index 1: Cat

Thay đổi các phần tử trong LinkedList

Sử dụng hàm set() để thay đổi các phần tử trong LinkedList.

import java.util.LinkedList;
class Main {
  public static void main(String[] args){
    //tạo linkedlist
    LinkedList<String> animals = new LinkedList<>();

    //thêm phần tử vào linkedlist
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    animals.add("Chicken");
    animals.add("Duck");
    System.out.println("LinkedList: " + animals);

    //thay đổi phần tử trong linkedlist
    animals.set(3, "Bird");
    System.out.println("LinkedList: " + animals);
  }
}

Kết quả

LinkedList: [Dog, Cat, Cow, Chicken, Duck]
LinkedList: [Dog, Cat, Cow, Bird, Duck]

Xóa các phần tử trong LinkedList

Sử dụng hàm remove() để xóa các phần tử trong LinkedList.

import java.util.LinkedList;
class Main {
  public static void main(String[] args){
    //tạo linkedlist
    LinkedList<String> animals = new LinkedList<>();

    //thêm phần tử vào linkedlist
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    animals.add("Chicken");
    animals.add("Duck");
    System.out.println("LinkedList: " + animals);

    //xóa phần tử trong linkedlist
    String str = animals.remove(3);
    System.out.println("Removed Element: " + str);
    System.out.println("New LinkedList: " + animals);
  }
}

Kết quả

LinkedList: [Dog, Cat, Cow, Chicken, Duck]
Removed Element: Chicken
New LinkedList: [Dog, Cat, Cow, Duck]

Duyệt các phần tử trong LinkedList với for-each

import java.util.LinkedList;
class Main {
  public static void main(String[] args){
    //tạo linkedlist
    LinkedList<String> animals = new LinkedList<>();

    //thêm phần tử vào linkedlist
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    animals.add("Chicken");
    animals.add("Duck");
    System.out.println("LinkedList: " + animals);
    
    //Sử dụng forEach loop
    System.out.println("Accessing linked list elements:");
    for(String animal: animals) {
        System.out.print(animal);
        System.out.print(", ");
    }
  }
}

Kết quả

LinkedList: [Dog, Cat, Cow, Chicken, Duck]
Accessing linked list elements:
Dog, Cat, Cow, Chicken, Duck,

Xem xét LinkedList như Queue

LinkedList kế thừa từ Queue và LinkedList có những thao tác của Queue.

import java.util.LinkedList;
import java.util.Queue;
class Main {
  public static void main(String[] args) {
    Queue<String> languages = new LinkedList<>();

    // add elements
    languages.add("Python");
    languages.add("Java");
    languages.add("C");
    System.out.println("LinkedList: " + languages);

    // access the first element
    String str1 = languages.peek();
    System.out.println("Accessed Element: " + str1);

    // access and remove the first element
    String str2 = languages.poll();
    System.out.println("Removed Element: " + str2);
    System.out.println("LinkedList after poll(): " + languages);

    // add element at the end
    languages.offer("Swift");
    System.out.println("LinkedList after offer(): " + languages);
  }
}

Kết quả

LinkedList: [Python, Java, C]
Accessed Element: Python
Removed Element: Python
LinkedList after poll(): [Java, C]
LinkedList after offer(): [Java, C, Swift]