Bài 10: Queue - Bài tập cơ bản - Sử dụng thư viện chuẩn STL cho C/C++

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

I . Ứng dụng của hàng đợi :

Để thấy được vai trò của cấu trúc dữ liệu queue cũng như hiểu hơn về nó. Chúng ta sẽ đi vào một bài toán cụ thể như sau:

Bạn có một chuỗi ký tự. Hãy lấy ký tự ở đầu của chuỗi và thêm nó vào cuối chuỗi. Hãy cho tôi thấy sự thay đỗi của chuỗi sau khi thực hiện hành động trên N lần.

Ý tưởng: Chuỗi ký tự trên có thể xem xét như là một hàng đợi. Tại mỗi bước, chúng ta sẽ dequeue(xóa) phần tử ở đầu chuỗi và thực hiện enqueue(thêm) phần tử đó cuối chuỗi. Lặp lại N lần bước công việc này, chúng ta sẽ có câu trả lời.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
void Enqueue(char queue[], char 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++;
    }
}
 
 
void Dequeue(char queue[], int& front, int rear) {
    if(front == rear)            // Queue is empty
        printf("UnderFlow\n");
    else {
        queue[front] = 0;        // Delete the front element
        front++;
    }
}
 
char Front(char queue[], int front) {
    return queue[front];
}
 
 
int main() {
    char queue[20] = {'a', 'b', 'c', 'd'};        
    int front = 0, rear = 4;                
    int arraySize = 20;                // Size of the array
    int N = 3;                    // Number of steps
    char ch;
    for(int i = 0;i < N;++i) {
        ch = Front(queue, front);
        Enqueue(queue, ch, rear, arraySize);
        Dequeue(queue, front, rear);
    }
    for(int i = front;i < rear;++i)
        printf("%c", queue[i]);
    printf("\n");
    return 0;
}

II . Các biến thể của Queue ;

1 . Hàng đợi 2 đầu :

Trong hàng đợi tiêu chuẩn phía trên, dữ liệu được thêm ở cuối và xóa đi ở đầu của hàng đợi. Nhưng với Double-ended queue, dữ liệu có thể thêm hoặc xóa ở cả đầu(front) và cuối(rear) của hàng đợi.

Nào, hãy cùng tôi đi cài đặt các hàm cho các chức năng của queue 2 đầu nào.

Thêm dữ liệu vào cuối queue:

void InsertAtBack(int queue[], int element, int &rear, int array_size){
    if(rear == array_size)
        printf("Overflow\n");
    else{
        queue[rear] = element;
        rear = rear + 1;
    }
}

Xóa dữ liệu ở cuối queue :

void DeleteFromBack(int queue[], int &rear, int front){
    if(front == rear)
        printf("Underflow\n");
    else{
        rear = rear - 1;
        queue[rear] = 0;
    }
}

Thêm dữ liệu vào đầu queue :

void InsertAtFront(int queue[], int &rear, int &front, int element, int array_size){
    if(rear == array_size)
        printf("Overflow\n");
    else{
        for(int i=rear; i>front; i--)
            queue[i] = queue[i-1];
        queue[front] = element;
        rear = rear+1;
    }
}

Xóa dữ liệu ở đầu queue :

void DeleteAtFront(int queue[], int &front, int &rear){
    if(front == rear)
        printf("Underflow\n");
    else{
        queue[front] = 0;
        front = front + 1;
    }
}

Lấy giá trị ở đầu queue :

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

Lấy giá trị ở cuối queue :

int GetRear(int queue[], int rear){
    return queue[rear-1];
}

Các hàm chức năng khác như Size và IsEmpty giống với hàng đợi tiêu chuẩn.

2. Hàng đợi vòng :

Hàng đợi vòng là một cải tiến của hàng đợi tiêu chuẩn. Trong hàng đợi tiêu chuẩn, khi một phần tử bị xóa khỏi hàng đợi, các vị trí bị xóa đó sẽ không được tái sử dụng. Hàng đợi vòng sinh ra để khắc phục sự lãng phí này.

Trong khi thêm phần tử vào hàng đợi vòng, nếu chỉ số rear đã ở vị trí cuối của mảng, khi đó bạn vẫn có thể thêm vào hàng đợi bằng cách thêm vào phía đầu của mảng(đó là các vị trí ở đầu mảng đã bị xóa đi và chưa được dùng).

Để cài đặt hàng đợi vòng, ngoài các biến sử dụng trong hàng đợi tiêu chuẩn, chúng ta cần thêm một biến khác nữa để lưu số lượng phần tử đang có trong hàng đợi, đặt nó là count

Bây giờ chúng ta cùng đi viết các hàm cho hàng đợi vòng nhé.

Enqueue :

void Enqueue(int queue[], int element, int& rear, int arraySize, int& count) {
    if(count == arraySize)            // Queue is full
            printf(“OverFlow\n”);
    else{
        queue[rear] = element;
        rear = (rear + 1)%arraySize;
        count = count + 1;
    }
}

Mình giải thích tại sao lại là (rear + 1)%arraySize : Giả sử khi rear = arraySize - 1, khi đó với hàng đợi tiêu chuẩn bạn sẽ không thể thêm nữa. Nhưng với hàng đợi vòng, ta sẽ thêm chừng nào count != arraySize. arraySize là số phần tử tối đa có thể có, do vậy, count != arraySize nghĩa là còn ô trống để insert vào queue. Chỉ số được insert vào queue như sau(giả sử arraySize = 3 nhé):

Nếu rear = 0, giá trị rear thực là (0 + 1) % 3 = 1
Nếu rear = 1, giá trị rear thực là (1 + 1) % 3 = 2
Nếu rear = 2, giá trị rear thực là (2 + 1) % 3 = 0

Các bạn nên nhớ: rear là chỉ số của phần tử sẽ được insert ở lần tiếp theo. Mỗi khi dequeue, count sẽ phải giảm đi 1. Ngược lại, nếu enqueue thành công, count sẽ tăng lên 1.

Giải thích này cũng đúng với front trong hàm dequeue dưới đây.

Dequeue

void Dequeue(int queue[], int& front, int rear, int& count) {
    if(count == 0)            // Queue is empty
        printf(“UnderFlow\n”);
    else {
        queue[front] = 0;        // Delete the front element
        front = (front + 1)%arraySize;
        count = count - 1;
    }
}

Front

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

Size :

int Size(int count) {
    return count;
}

IsEmpty :

bool IsEmpty(int count) {
    return (count == 0);
}

Bài tiếp theo: Map - Khái niệm 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!