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:
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
#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.
