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

Posted on Updated on by adminChuyên mục:Kiến thức Internet

Đăng bởi : Admin | Lượt xem : 3091 | 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ỉ hoàn toàn có thể thêm những thành phần vào một đầu của queue ( giả sử là cuối ), và cũng chỉ hoàn toàn có thể xóa thành phần ở đầu còn lại của queue ( tạm gọi là đầu ). Như vậy, ở một đầu không hề xảy ra hai hành vi thêm và xóa đồng thời .Trong đời sống thực tất cả chúng ta có rất nhiều ví dụ về hàng đợi, ví dụ điển hình như hàng xe xe hơi trên đường một chiều ( đặc biệt quan trọng là khi tắc xe ), trong đó xe nào vào tiên phong sẽ thoát ra tiên phong. Một vài ví dụ khác là xếp hàng học viên, 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 giải trí trên cấu trúc tài liệu hàng đợi hoàn toàn có thể tương quan tới việc khởi tạo hàng đợi, sử dụng tài liệu trên hàng đợi và sau đó là xóa dữ liệu khỏi bộ nhớ .Để thiết lập được Queue, tất cả chúng ta sẽ cần sử dụng những 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à 1 số ít hoạt động giải trí cơ bản hoàn toàn có thể thực thi trên cấu trúc tài 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ối thiểu 1 thành phần, tất cả chúng ta sẽ triển khai xóa bỏ thành phần ở đầ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 cỡ của Hàng đợi, nói cách khác là số lượng thành phần đ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 tài liệu hàng đợi duy trì hai con trỏ tài liệu : front và rear, do đó những hoạt động giải trí của loại cấu trúc tài liệu này là khá phức tạp khi so sánh với cấu trúc tài liệu ngăn xếp .Dưới đây là những bước để enqueue ( chèn ) tài 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.

admin