Ninja IT

Queue

Queue

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

Có hai hàm phổ biến với queue đó là enQueue() (thêm vào cuối hàng đợi) và deQueue() (xóa một phần từ đầu hàng đợi). Ngoài ra còn hai thông dụng hàm nữa là kiểm tra hàng đợi rỗng (isEmpty()) và hàm lấy dữ liệu phần tử ở đầu hàng đợi (getFront()).

Tương tự như stack thì có thể cài đặt hàng đợi bằng linked list hoặc mảng. Sau đây là cách cài đặt sử dụng linked-list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

typedef struct Node {
  int data; // dữ liệu kiểu int
  struct Node* next;
} Node;

typedef struct Queue {
  Node* front; // front là đầu phía trước
  Node* back;  // back là đầu phía sau
} Queue;

void enQueue(Queue* q, int value) {
  // tạo node với dữ liệu mới
  Node* node = malloc(sizeof(Node)); 
  node->data = value;
  node->next = NULL;

  // thêm node vào phía sau queue
  if (q->front == NULL) {
    q->front = node;
    q->back = node;
  } else {
    q->back->next = node;
    q->back = node;
  }
}

void deQueue(Queue* q) {
  if (q->front == NULL) { // nếu stack rỗng thì bỏ qua
    return;
  }
  // trỏ q->front đến node tiếp theo của q->front cũ
  Node* front = q->front;
  q->front = q->front->next;
  
  free(front); // xóa node không dùng nữa
}

int main() {
  Queue q = {.front = NULL, .rear = NULL};
}

Cài đặt các hàm isEmpty, getFront và hàm in hàng đợi

Sau đây là ví dụ sẽ cài đặt các hàm isEmpty(), getFront() và hàm in hàng đợi

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// kiểm tra queue rỗng
bool isEmpty(Queue* q) {
  return q->front == NULL;
}

// lấy dữ liệu ở đầu phía trước
int getFront(Queue* q) {
  if (q->front == NULL) { // trường hợp queue rỗng thì trả về 0
    return 0;             // có thể in ra lỗi ở đây
  }
  return q->front->data;
}

// in node từ trước ra sau
void printQueue(Queue* q) {
  Node* node = q->front;
  while(node != NULL) {
    printf("%d -> ", node->data);
    node = node->next;
  }
  printf("NULL\n");
}