Bài 9: Queue - Khái niệm cơ bản - Sử dụng thư viện chuẩn STL cho C/C++

Đăng bởi: Admin | Lượt xem: 6282 | Chuyên mục: C/C++

Queue - Hàng đợi là một cấu trúc dữ liệu dùng để lưu giữ các đối tượng theo cơ chế FIFO (viết tắt từ tiếng Anh: First In First Out), nghĩa là “vào trước ra trước”.

Khác với ngăn xếp, hàng đợi là mở ở cả hai đầu. Một đầu luôn luôn được sử dụng để chèn dữ liệu vào (hay còn gọi là sắp vào hàng) và đầu kia được sử dụng để xóa dữ liệu (rời hàng). Cấu trúc dữ liệu hàng đợi tuân theo phương pháp First-In-First-Out, tức là dữ liệu được nhập vào đầu tiên sẽ được truy cập đầu tiên.

Trong cấu trúc hàng đợi(queue), ta chỉ có thể thêm các phần tử vào một đầu của queue(giả sử là cuối), và cũng chỉ có thể xóa phần tử ở đầu còn lại của queue(tạm gọi là đầu). Như vậy, ở một đầu không thể xảy ra hai hành động thêm và xóa đồng thời.

Trong đời sống thực chúng ta có rất nhiều ví dụ về hàng đợi, chẳng hạn như hàng xe ô tô trên đường một chiều (đặc biệt là khi tắc xe), trong đó xe nào vào đầu tiên sẽ thoát ra đầu tiên. Một vài ví dụ khác là xếp hàng học sinh, xếp hàng mua vé, …

I . Các hoạt động cơ bản trên cấu trúc dữ liệu hàng đợi :

hoạt động trên cấu trúc dữ liệu hàng đợi có thể liên quan tới việc khởi tạo hàng đợi, sử dụng dữ liệu trên hàng đợi và sau đó là xóa dữ liệu khỏi bộ nhớ.

Để cài đặt được Queue, chúng ta sẽ cần sử dụng các biến như sau:

queue[]: Một mảng một chiều mô phỏng cho hàng đợi
arraySize: Số lượng phần tử tối đa có thể lưu trữ trong queue[]
front: Chỉ số của phần tử ở đang đầu queue. Nó sẽ là chỉ số của phần tử sẽ bị xóa ở lần tiếp theo
rear: Chỉ số của phần tử tiếp theo sẽ được thêm vào cuối của queue

Danh sách dưới đây là một số hoạt động cơ bản có thể thực hiện trên cấu trúc dữ liệu hàng đợi:

1 . Enqueue – Thêm vào cuối hàng đợi :

Nếu hàng đợi chưa đầy, chúng ta sẽ thêm phần tử cần thêm vào cuối(rear) của hàng đợi. Ngược lại, thông báo lỗi.

Các bạn lưu ý, rear là chỉ số của phần tử sẽ được thêm ở lần tiếp theo. Do đó, thêm xong rồi ta mới tăng rear lên 1 đơn vị. Giá trị rear cần thay đổi nên được truyền theo tham chiếu.

void Enqueue(int queue[], int element, int& rear, int arraySize) {
    if(rear == arraySize)            // Queue is full
            printf("OverFlow\n");
    else{
         queue[rear] = element;    // Add the element to the back
         rear++;
    }
}

2. Dequeue – Xóa khỏi đầu hàng đợi :

Nếu hàng đợi có ít nhất 1 phần tử, chúng ta sẽ tiến hành xóa bỏ phần tử ở đầu của hàng đợi bằng cách tăng front lên 1 giá trị.

Ở đây, front đang là chỉ số của phần tử sẽ bị xóa rồi. Cho nên chỉ cần tăng là xong, đó cũng là lý do ta cần truyền tham số front sử dụng tham chiếu.

void Dequeue(int queue[], int& front, int rear) {
    if(front == rear)            // Queue is empty
        printf("UnderFlow\n");
    else {
        queue[front] = 0;        // Delete the front element
        front++;
    }
}

Tới đây chắc nhiều bạn thắc mắc tại sao lại tăng front mà không phải là giảm. Các bạn xem giải thích ở hình sau nhé:

3. Front – Lấy giá trị ở đầu hàng đợi :

Hàm này sẽ lấy và trả về giá trị của phần tử đang ở đầu hàng đợi

int Front(int queue[], int front) {
    return queue[front];
}

4. Các hàm hỗ trợ khác :

Hàm lấy kích thước của Hàng đợi, nói cách khác là số lượng phần tử đang có trên hàng đợi

int Size(int front, int rear) {
    return (rear - front);
}

//Hàm kiểm tra queue rỗng
bool IsEmpty(int front, int rear) {
    return (front == rear);
}

II . Hoạt động enqueue trong cấu trúc dữ liệu hàng đợi

Bởi vì cấu trúc dữ liệu hàng đợi duy trì hai con trỏ dữ liệu: front và rear, do đó các hoạt động của loại cấu trúc dữ liệu này là khá phức tạp khi so sánh với cấu trúc dữ liệu ngăn xếp.

Dưới đây là các bước để enqueue (chèn) dữ liệu vào trong hàng đợi:

Kiểm tra xem hàng đợi là có đầy không.
Nếu hàng đợi là đầy, tiến trình bị lỗi và bị thoát.
Nếu hàng đợi không đầy, tăng con trỏ rear để trỏ tới vị trí bộ nhớ trống tiếp theo.
Thêm phần tử dữ liệu vào vị trí con trỏ rear đang trỏ tới trong hàng đợi.
Trả về success.

Bài tiếp theo: Queue - Bài tập cơ bản >>

Theo dõi VnCoder trên Facebook, để cập nhật những bài viết, tin tức và khoá học mới nhất!