Thứ Sáu, 6 Tháng Mười Hai 2024
Trang chủLập trìnhLập trình C/C++Chinh phục cấu trúc dữ liệu hàng đợi lập trình C/C++ trong...

Chinh phục cấu trúc dữ liệu hàng đợi lập trình C/C++ trong 5 phút

Cấu trúc dữ liệu hàng đợi là một trong những khái niệm cơ bản trong lập trình, được sử dụng để giải quyết các vấn đề liên quan đến việc xử lý và quản lý các phần tử dữ liệu theo một trật tự nhất định. Trong bài viết này, chúng ta sẽ tìm hiểu về cấu trúc dữ liệu hàng đợi trong lập trình C/C++.

DANH SÁCH BÀI VIẾT
Tìm hiểu Cấu trúc dữ liệu Hash table trong lập trình C/C++
Cây đa phân trong lập trình C/C++ – Cấu trúc dữ liệu cây đa phân
Hiểu về cấu trúc dữ liệu cây trong lập trình C/C++
Chinh phục cấu trúc dữ liệu hàng đợi lập trình C/C++ trong 5 phút
Cấu trúc dữ liệu ngăn xếp trong lập trình C/C++
Cấu trúc dữ liệu Danh sách liên kết (Linked list) trong lập trình C/C++
Cấu trúc dữ liệu cây nhị phân trong lập trình C/C++
Cây nhị phân tìm kiếm – Tìm hiểu cây nhị phân tìm kiếm trong C/C++
Duyệt tiền tố, trung tố, hậu tố trong cây nhị phân – Lập trình C/C++

Khái niệm hàng đợi Queue

Chinh phục cấu trúc dữ liệu hàng đợi lập trình C/C++ trong 5 phút

Hàng đợi (queue) là một cấu trúc dữ liệu mà các phần tử được lưu trữ theo thứ tự vào trước ra sau. Điều này có nghĩa là phần tử được thêm vào hàng đợi đầu tiên sẽ được xử lý đầu tiên, và phần tử được thêm vào sau cùng sẽ được xử lý sau cùng.

Bạn có thể cứ hình dung đơn giản như ống nước đang chảy vậy, nước vào một đầu và đi ra đầu bên kia.

Các thao tác cơ bản trên hàng đợi Queue bao gồm:

  • Enqueue: thêm một phần tử vào cuối hàng đợi.
  • Dequeue: loại bỏ phần tử đầu tiên khỏi hàng đợi.
  • Front: truy xuất phần tử đầu tiên trong hàng đợi.
  • Rear: truy xuất phần tử cuối cùng trong hàng đợi.

Cấu trúc dữ liệu hàng đợi trong lập trình C

Cấu trúc dữ liệu hàng đợi(queue) có thể được triển khai bằng cách sử dụng mảng hoặc danh sách liên kết. Trong đó, mảng được sử dụng để lưu trữ các phần tử trong hàng đợi và hai biến front và rear được sử dụng để theo dõi phần tử đầu tiên và phần tử cuối cùng của hàng đợi.

Triển khai hàng đợi bằng mảng

Để triển khai hàng đợi bằng mảng, chúng ta sẽ sử dụng hai biến front và rear để theo dõi phần tử đầu tiên và phần tử cuối cùng của hàng đợi. Ban đầu, cả hai biến này sẽ được thiết lập thành -1 để đại diện cho hàng đợi rỗng. Sau đó, khi chúng ta thêm một phần tử vào hàng đợi, chúng ta sẽ tăng rear lên một đơn vị và gán giá trị của phần tử đó vào vị trí tương ứng trong mảng. Tương tự, khi chúng ta loại bỏ một phần tử khỏi hàng đợi, chúng ta sẽ tăng front lên một đơn vị.

Dưới đây là một ví dụ về cách triển khai hàng đợi bằng mảng trong lập trình C:

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100 // Định nghĩa kích thước tối đa của hàng đợi
int queue[MAX_SIZE]; // Khai báo mảng để lưu trữ các phần tử trong hàng đợi
int front = -1; // Biến front sẽ theo dõi phần tử đầu tiên của hàng đợi
int rear = -1; // Biến rear sẽ theo dõi phần tử cuối cùng của hàng đợi

// Hàm kiểm tra xem hàng đợi có rỗng hay không
int isQueueEmpty() {
  if(front == -1 && rear == -1) return 1;
  else return 0;
}

// Hàm kiểm tra xem hàng đợi đã đầy hay chưa
int isQueueFull() {
  if(rear == MAX_SIZE-1) return 1;
  else return 0;
}

// Hàm Enqueue: thêm một phần tử vào cuối hàng đợi
void Enqueue(int x) {
  if(isQueueFull()) printf("Hàng đợi đã đầy\n");
  else if(isQueueEmpty()) {
    front = rear = 0;
    queue[rear] = x;
  }
  else {
    rear++;
    queue[rear] = x;
  }
}

// Hàm Dequeue: loại bỏ phần tử đầu tiên khỏi hàng đợi
void Dequeue() {
  if(isQueueEmpty()) printf("Hàng đợi đã rỗng\n");
  else if(front == rear) {
    front = rear = -1;
  }
  else {
    front++;
  }
}

// Hàm Front: truy xuất phần tử đầu tiên trong hàng đợi
int Front() {
  if(isQueueEmpty()) {
    printf("Hàng đợi đã rỗng\n");
    return -1;
  }
  else {
    return queue[front];
  }
}

// Hàm Rear: truy xuất phần tử cuối cùng trong hàng đợi
int Rear() {
  if(isQueueEmpty()) {
    printf("Hàng đợi đã rỗng\n");
    return -1;
  }
  else {
    return queue[rear];
  }
}

// Hàm in ra toàn bộ các phần tử trong hàng đợi
void PrintQueue() {
  if (isQueueEmpty()) {
    printf("Hàng đợi đã rỗng\n");
    return;
  } else {
    printf("Các phần tử trong hàng đợi là: ");
    for(int i = front ; i<=rear;i++){ 
        printf("%d ", queue[i]);
   }
  }
}

// Hàm main để thực hiện thao tác trên hàng đợi
int main() {
  Enqueue(10);
  Enqueue(20);
  Enqueue(30);
  Enqueue(40);
  Enqueue(50);
  PrintQueue(); // Kết quả: 10 20 30 40 50
  Dequeue();
  PrintQueue(); // Kết quả: 20 30 40 50
  printf("Phần tử đầu tiên trong hàng đợi là: %d\n", Front()); // Kết quả: 20
  printf("Phần tử cuối cùng trong hàng đợi là: %d\n", Rear()); // Kết quả: 50
  return 0;
}

Triển khai hàng đợi bằng danh sách liên kết

Để triển khai được hàng đợi bằng danh sách liên kết, trước tiên bạn cần nắm rõ danh sách liên kết là gì, có thể thăm khảo ngay bài viết này.

Để triển khai hàng đợi bằng danh sách liên kết, chúng ta sẽ sử dụng hai con trỏ front rear để theo dõi phần tử đầu tiên và phần tử cuối cùng của hàng đợi. Ban đầu, cả hai con trỏ này sẽ được thiết lập thành NULL để đại diện cho hàng đợi rỗng. Khi chúng ta thêm một phần tử vào hàng đợi, chúng ta sẽ tạo ra một nút mới và gán giá trị của phần tử đó vào trường data của nút. Sau đó, chúng ta sẽ liên kết nút mới với phần tử cuối cùng trong danh sách liên kết và cập

nhật rear để trỏ tới nút mới. Khi chúng ta loại bỏ phần tử đầu tiên khỏi hàng đợi, chúng ta sẽ chỉ cần trỏ front tới phần tử tiếp theo trong danh sách liên kết và giải phóng nút đầu tiên.

XEM THÊM: Khóa học lập trình C/C++ từ A-Z cho người mới – Giảm giá 40% hôm nay

Dưới đây là một ví dụ về cách triển khai hàng đợi bằng danh sách liên kết trong lập trình C:

#include <stdio.h>
#include <stdlib.h>

// Khai báo một nút trong danh sách liên kết
struct Node {
  int data;
  struct Node * next;
};

// Khai báo hai con trỏ front và rear để theo dõi phần tử đầu tiên và cuối cùng của hàng đợi
struct Node * front = NULL;
struct Node * rear = NULL;

// Hàm kiểm tra xem hàng đợi có rỗng hay không
int isQueueEmpty() {
  if (front == NULL && rear == NULL) return 1;
  else return 0;
}

// Hàm Enqueue: thêm một phần tử vào cuối hàng đợi
void Enqueue(int x) {
  // Tạo ra một nút mới
  struct Node * newNode = (struct Node * ) malloc(sizeof(struct Node));
  newNode -> data = x;
  newNode -> next = NULL;

  // Nếu hàng đợi rỗng, thì front và rear đều trỏ tới nút mới
  if (isQueueEmpty()) {
    front = rear = newNode;
  }
  // Ngược lại, liên kết nút mới với phần tử cuối cùng trong danh sách liên kết và cập nhật rear
  else {
    rear -> next = newNode;
    rear = newNode;
  }
}

// Hàm Dequeue: loại bỏ phần tử đầu tiên khỏi hàng đợi
void Dequeue() {
  // Nếu hàng đợi rỗng, hiển thị thông báo và thoát khỏi hàm
  if (isQueueEmpty()) {
    printf("Hàng đợi đã rỗng\n");
    return;
  }
  // Nếu hàng đợi chỉ còn một phần tử, thì front và rear sẽ đều trỏ tới NULL
  else if (front == rear) {
    free(front);
    front = rear = NULL;
  }
  // Ngược lại, trỏ front tới phần tử tiếp theo trong danh sách liên kết và giải phóng nút đầu tiên
  else {
    struct Node * temp = front;
    front = front -> next;
    free(temp);
  }
}

// Hàm Front: truy xuất phần tử đầu tiên trong hàng đợi
int Front() {
  if (isQueueEmpty()) {
    printf("Hàng đợi đã rỗng\n");
    return -1;
  } else {
    return front -> data;
  }
}

// Hàm Rear: truy xuất phần tử cuối cùng trong hàng đợi
int Rear() {
  if (isQueueEmpty()) {
    printf("Hàng đợi đã rỗng\n");
  } else {
    return rear -> data;
  }
}

// Hàm in ra toàn bộ các phần tử trong hàng đợi
void PrintQueue() {
  if (isQueueEmpty()) {
    printf("Hàng đợi đã rỗng\n");
    return;
  } else {
    struct Node * temp = front;
    printf("Các phần tử trong hàng đợi là: ");
    while (temp != NULL) {
      printf("%d ", temp -> data);
      temp = temp -> next;
    }
    printf("\n");
  }
}

// Hàm main để thực hiện thao tác trên hàng đợi
int main() {
  Enqueue(10);
  Enqueue(20);
  Enqueue(30);
  Enqueue(40);
  Enqueue(50);
  PrintQueue(); // Kết quả: 10 20 30 40 50
  Dequeue();
  PrintQueue(); // Kết quả: 20 30 40 50
  printf("Phần tử đầu tiên trong hàng đợi là: %d\n", Front()); // Kết quả: 20
  printf("Phần tử cuối cùng trong hàng đợi là: %d\n", Rear()); // Kết quả: 50
  return 0;
}

Trong ví dụ trên, chúng ta đã triển khai các thao tác cơ bản trên hàng đợi bằng cách sử dụng danh sách liên kết. Hàm Enqueue được sử dụng để thêm một phần tử vào cuối hàng đợi, hàm Dequeue được sử dụng để loại bỏ phần tử đầu tiên khỏi hàng đợi, hàm Front được sử dụng để truy xuất phần tử đầu tiên trong hàng đợi, hàm Rear được sử dụng để truy xuất phần tử cuối cùng trong hàng đợi, và hàm PrintQueue được sử dụng để in ra toàn bộ các phần tử trong hàng đợi.

Đó là cách triển khai hàng đợi bằng danh sách liên kết trong lập trình C. Sử dụng cấu trúc dữ liệu hàng đợi sẽ giúp chúng ta giải quyết một số vấn đề liên quan đến thực thi chương trình, đặc biệt là trong trường hợp cần sử dụng thuật toán BFS (Breadth First Search). Hy vọng rằng bài viết này sẽ giúp bạn hiểu thêm về hàng đợi và cách triển khai nó trong lập trình C.

XEM THÊM: Khóa học lập trình Android từ cơ bản đến thành thạo – Giảm ngay 40%

Cảm ơn bạn đã đọc hết bài viết, hy vọng qua bài viết này đã giúp bạn nắm rõ và áp dụng được cấu trúc dữ liệu hàng đợi(Queue).

[Xem tất cả bài viết chủ đề C/C++ tại đây]

XÊM THÊM
Cấu trúc dữ liệu Danh sách liên kết (Linked list) trong lập trình C/C++
Cấu trúc dữ liệu ngăn xếp trong lập trình C/C++
Cấu trúc dữ liệu cây nhị phân trong lập trình C/C++
Tìm hiểu các toán tử thao tác bit trong lập trình C/C++
Cấu trúc dữ liệu cây nhị phân trong lập trình C/C++
Thuật toán đếm số lượng chữ số của số nguyên dương n
Thuật toán tính dãy số Fibonacci
Bài toán chuẩn hóa xâu ký tự
Kiểm tra số chẵn lẻ trong lập trình C/C++
0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?

Dịch vụ code thuê

TUICOCACH.COM NHẬN ĐẶT TEXTLINK, BANNER, GP
0
Giáo sư! có thể ném gạch bên dưới nhé!x