Chương trình Java triển khai cấu trúc dữ liệu Queue (Hàng đợi)

Trong bài viết này, chúng ta sẽ hiểu cách triển khai cấu trúc dữ liệu Queue (Hàng đợi). Queue là cấu trúc tuyến tính tuân theo thứ tự cụ thể cho các thao tác. Thứ tự là First In First Out (FIFO - Vào trước ra trước).

Minh họa dưới đây:

Giả sử đầu vào là:

Input Queue: [150, 300, 450, 600]

Đầu ra mong muốn:

After removing an element, the elements of the queue are: [300, 450, 600]

Thuật toán

Bước 1 - BẮT ĐẦU 
Bước 2 - Khai báo biến 
Bước 3 - Thêm phần tử bằng 'offer' 
Bước 4 - Hiển thị nội dung queue 
Bước 5 - Dùng 'poll' xóa phần tử khỏi queue 
Bước 6 - Hiển thị phần tử queue sau khi gọi 'poll' 
Bước 7 - Hiển thị kết quả 
Bước 8 - DỪNG

Ví dụ 1

Dùng hàm built-in để thực hiện tất cả thao tác stack (queue).

import java.util.Queue; 
import java.util.LinkedList; 

public class Demo { 
    public static void main(String[] args) { 
        System.out.println("The required packages have been imported"); 
        Queue input_queue = new LinkedList<>(); 
        input_queue.offer(150); 
        input_queue.offer(300); 
        input_queue.offer(450); 
        input_queue.offer(600); 
        System.out.println("The queue is defined as: " + input_queue); 
        int removedNumber = input_queue.poll(); 
        System.out.println("After removing an element, the elements of the queue are: " + input_queue); 
    } 
}

Kết quả

The required packages have been imported 
The queue is defined as: [150, 300, 450, 600] 
After removing an element, the elements of the queue are: [300, 450, 600]

Ví dụ 2

Dùng hàm tự định nghĩa (user defined) để thực hiện các thao tác queue (triển khai mảng tròn - circular array).

public class Queue { 
    int SIZE = 5; 
    int items[] = new int[SIZE]; 
    int front, rear; 
    
    Queue() { 
        front = -1; 
        rear = -1; 
    } 
    
    boolean isFull() { 
        if (front == 0 && rear == SIZE - 1) 
            return true; 
        return false; 
    } 
    
    boolean isEmpty() { 
        if (front == -1) 
            return true; 
        else 
            return false; 
    } 
    
    void enQueue(int element) { 
        if (isFull()) { 
            System.out.println("\nThe queue is full"); 
        } else { 
            if (front == -1) 
                front = 0; 
            rear++; 
            items[rear] = element; 
            System.out.println("\nThe element " + element + " is inserted"); 
        } 
    } 
    
    int deQueue() { 
        int element; 
        if (isEmpty()) { 
            System.out.println("\nThe queue is empty"); 
            return (-1); 
        } else { 
            element = items[front]; 
            if (front >= rear) { 
                front = -1; 
                rear = -1; 
            } else { 
                front++; 
            } 
            System.out.println("\nThe element " + element + " is deleted"); 
            return (element); 
        } 
    } 
    
    void display() { 
        int i; 
        if (isEmpty()) { 
            System.out.println("The queue is empty "); 
        } else { 
            System.out.println("\nThe elements of the queue are: "); 
            for (i = front; i <= rear; i++) 
                System.out.print(items[i] + " "); 
        } 
    } 
    
    public static void main(String[] args) { 
        Queue input_queue = new Queue(); 
        for(int i = 1; i < 6; i++) { 
            input_queue.enQueue(i * 100); 
        } 
        System.out.println("The queue is defined as: " + input_queue); 
        input_queue.enQueue(6); 
        input_queue.display(); 
        input_queue.deQueue(); 
        input_queue.display(); 
    } 
}

Kết quả

The element 100 is inserted 
The element 200 is inserted 
The element 300 is inserted 
The element 400 is inserted 
The element 500 is inserted 
The queue is defined as: Queue@2a139a55 
The queue is full 
The elements of the queue are: 100 200 300 400 500 
The element 100 is deleted 
The elements of the queue are: 200 300 400 500