Lập trình cài đặt thuật toán mô tả cấu trúc dữ liệu hàng đợi (queue)

Như các bạn học lập trình đã biết Hàng đợi (Queue) là một cấu trúc dữ liệu trừu tượng, là một cái gì đó tương tự như hàng đợi trong đời sống hàng ngày (xếp hàng).

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 đờ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é, …

Để hiểu rõ về cấu trúc dữ liệu hàng đợi queue các bạn có thể tham khảo đoạn code lập trình c để mô tả hàng đợi như sau:

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

#define MAX 6

int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;

int peek(){
   return intArray[front];
}

bool isEmpty(){
   return itemCount == 0;
}

bool isFull(){
   return itemCount == MAX;
}

int size(){
   return itemCount;
}  

void insert(int data){

   if(!isFull()){
	
      if(rear == MAX-1){
         rear = -1;            
      }       

      intArray[++rear] = data;
      itemCount++;
   }
}

int removeData(){
   int data = intArray[front++];
	
   if(front == MAX){
      front = 0;
   }
	
   itemCount--;
   return data;  
}

int main() {
   /* chen 5 phan tu */
   insert(3);
   insert(5);
   insert(9);
   insert(1);
   insert(12);

   // front : 0
   // rear  : 4
   // ------------------
   // index : 0 1 2 3 4 
   // ------------------
   // queue : 3 5 9 1 12
   insert(15);

   // front : 0
   // rear  : 5
   // ---------------------
   // index : 0 1 2 3 4  5 
   // ---------------------
   // queue : 3 5 9 1 12 15
	
   if(isFull()){
      printf("Hang doi (Queue) da day!\n");   
   }

   // xoa mot phan tu 
   int num = removeData();
	
   printf("Phan tu bi xoa: %d\n",num);
   // front : 1
   // rear  : 5
   // -------------------
   // index : 1 2 3 4  5
   // -------------------
   // queue : 5 9 1 12 15

   // Chen them mot phan tu
   insert(16);

   // front : 1
   // rear  : -1
   // ----------------------
   // index : 0  1 2 3 4  5
   // ----------------------
   // queue : 16 5 9 1 12 15

   // neu hang doi la day thi phan tu se khong duoc chen. 
   insert(17);
   insert(18);

   // ----------------------
   // index : 0  1 2 3 4  5
   // ----------------------
   // queue : 16 5 9 1 12 15
   printf("Phan tu tai vi tri front: %d\n",peek());

   printf("----------------------\n");
   printf("Gia tri chi muc : 5 4 3 2  1  0\n");
   printf("----------------------\n");
   printf("Hang doi (Queue):  ");
	
   while(!isEmpty()){
      int n = removeData();           
      printf("%d ",n);
   }   
}

Kết quả

Sau khi Biên dịch và chạy chương trình C trên các bạn sẽ nhận được kết quả như hình sau:

Nếu bạn chưa rõ về nguyên tắc hoạt động của hàng đợi có thể tham khảo bài viết Hàng đợi là gì và mô tả hoạt động ở bài viết này: tại đây.