Trong phần này chúng tôi sẽ giới thiệu tới các bạn cấu trúc dữ liệu hàng đợi hay còn gọi là queue. Để hiểu rõ được các hoạt động và thực hiện của loại cấu trúc dữ liệu này bạn cần có những kiến thức về:

Mảng
Danh sách liên kết (linked list)

Bới vì hàng đợi có thể được cài đặt bằng cahcs sử dụng mảng hoặc danh sách liên kết.

Giới thiệu về Hàng đợi (Queue)

Hàng đợi là loại cấu trúc dữ liệu có tính chất ‘vào trước, ra trước” (First-in, First-out / FIFO). Nó giống như trường hợp hàng đợi ngoài thực tế khi ta mua hàng, người nào xếp hàng vào hàng đợi trước thì sẽ được phục vụ trước và ra khỏi hàng đợi trước.

Hàng đợi thường được ứng dụng làm bộ đệm máy tính để lưu lại những lênh mà máy chưa kịp sử lý. Và sau đó nó sẽ được xử lý thao trình tự FIFO. ví dụ như trường hợp của bộ đệm bàn phím, phím nào nhấn trước sẽ được xử lý trước.

Hàng đợi có thể được thể hiện như sau:

Hình 1: Mô tả cấu trúc dữ liệu hàng đợi

Với Front là vị trí đầu tiên và Rear là vị trí cuối hàng đợi.

Có hai thao tác chính với hàng đợi:

Enqueue: Chèn dữ liệu vào cuối hàng đợi (chèn vào sau Rear).

Dequeue: Lấy dữ liệu ra khỏi hàng đợi (lấy ra từ Front).

Ta cùng đi vào tìm hiểu chi tiết quá trình chèn dữ liệu vào và lấy dữ liệu ra từ hàng đợi để hiểu hơn về cách thức hoạt động của nó.

Enqueue

Trong phạm vi bài học này, chúng ta coi rear luôn luôn là vị trí cuối cùng trong hàng đợi, do vậy khi chèn dữ liệu mới vào, ta phải tăng vị trí này lên 1 đơn vị để được vị trí rear mới.

Hình 2: Trước khi chèn dữ liệu vào hàng đợi

Hình 3: Sau khi chèn dữ liệu vào hàng đợi

Dequeue

Ngược lại với Enqueue, Dequeue là thao tác lấy dữ liệu ra khỏi hàng đợi.

Quá trình dequeue được mô tả trong các hình dưới đây.

Ở hình 5, Front là vị trí để lấy dữ liệu ra khỏi hàng đợi, và để chuẩn bị cho lần Dequeue tiếp theo ta phải tăng giá trị của Front lên 1.

Hàng đợi tuyến tính (Linear Queue)

Hàng đợi có hoạt động như đã miêu tả ở các phần trên được gọi là hàng đợi tuyến tính.

Hàng đợi tuyến tính thường được cài đặt bằng cách dùng mảng một chiều. Tuy nhiên cách làm này để lộ một số khuyết điểm.

Theo quá trính Dequeue đã được mô tả ở Hình 4 và Hình 5, nếu bạn chú ý kỹ ở quá trình Dequeue này thì bạn sẽ thấy rằng vị trí các ô nhớ chứa phần dữ liệu sau khi dequeue thì không được sử dụng bởi hàng đợi nữa. Vì khi Enqueue, ta sẽ chèn dữ liệu vào cuối hàng đợi chứ không tác động vào những vị trí đầu đã được dequeue, cho dù những vị trí đó đang rỗng.

Hãy cùng xem ví dụ sau:

Giả sử ta có hàng đợi được cài đặt bằng một mảng tĩnh có thể chứa tối đa 5 ký tự kiểu “char”.

char q[5];

Ta có một chuỗi các thao tác sau với hàng đợi trên:

Khi mới khởi tạo, queue rỗng.

Tới bước này ta không thể chèn thêm dữ liệu vào hàng đợi nữa cho dù hàng đợi chưa thực sự đầy. Để tiếp tục chèn dữ liệu vào hàng đợi, ta phải thực hiện thêm một thao tác ở đây, đó là dịch toàn bộ dữ liệu của hàng đợi về bên trái (về phía đầu hàng đợi). Tuy nhiên cái giá mà chúng ta phải trả cho thao tác này đó là thời gian thực hiện sẽ tăng lên đáng kể, nhất là khi kích thước và lượng dữ liệu trong hàng đợi lớn.

Trong trường hợp hàng đợi được cài đặt bằng mảng một chiều. Nó sẽ có kích thước cố định, như ở ví dụ trên là kích thước bằng 5.

Do vậy khi ta không thể chèn dữ liệu (Enqueue) vào vị trí vượt quá kích thước của hàng đợi. Điều kiện để biết được hàng đợi đã đầy là “Rear == kích thước của hàng đợi”.

Ta cũng không thể lấy dữ liệu ra khỏi hàng đợi (Dequeue) khi mà hàng đợi rỗng, ta đặt điều kiện cho hàng đợi rỗng là khi “Front == Rear == 0”.

Khi mà “Rear == kích thước của hàng đợi”, nhưng hàng đợi vẫn còn những khoảng trống ở các vị trí đầu, ta có thể thực hiện phương pháp dịch để tránh tính trạng lãng phí bộ nhớ. Tuy nhiên đây là một phương pháp không nhất thiết phải thực hiện khi cài đặt hàng đợi. Một khi áp dụng phương pháp này hiệu năng của chương trình sẽ bị giảm xuống, thời gian thực hiện chương trình tăng lên.

Cặt đặt hàng đợi

Sau đây là phương pháp đơn giản để cài đặt hàng đợi tuyến tính. Phương pháp này sử dụng mảng một chiều và ngôn ngữ thực hiện là C++.

Code đã được chạy kiểm tra trên https://www.onlinegdb.com/online_c++_compiler.

#include<iostream>
using namespace std;

#define Q_SIZE 500
#define ERROR -99999

class Queue{
private:
	char q[Q_SIZE];
	int front,rear;
public:
	/* Hàm khởi tạo, khi mới khởi tạo queue rỗng
	   front = rear = 0 */
	Queue(){
		front = 0;
		rear = 0;
	}
	/* Hàm chèn ký tự c vào hàng đợi q */
	void Enqueue(char c);

	/* Hàm lấy phần tử ở đầu ra khỏi hàng đợi */
	char Dequeue();

	/* Hàm trả về giá trị của phần tử đầu tiên trong hàng đợi */
	char getFront();

	/* Hàm kiểm tra xem hàng đợi có rỗng hay không */
	bool isEmpty();

	/* Hàm kiểm tra xem hàng đợi đã đầy hay chưa */
	bool isFull();

	/* Hàm in ra tất cả các phần tử trong hàng đợi */
	void PrintQ();
};

void Queue::Enqueue(char c){
	/* Kiểm tra xem hàng đợi đã đầy hay chưa,
	   Chỉ enqueue khi hàng đợi chưa đầy */
	if(isFull()){
		cout << "ERROR: Queue is full, can't enqueue" << endl;
		return;
	}
	if(isEmpty()){
	    front++; /* front = 1 */
	    rear ++; /* rear = 1 */
	}
	q[rear++] = c;
}

char Queue::Dequeue(){
	char temp;
	/* Kiển tra xem hàng đợi có rỗng không,
	   Chỉ Dequeue khi hàng đợi không rỗng */
	if(isEmpty()){
		cout << "ERROR: Queue is empty, can't dequeue" << endl;
		return ERROR;
	}
	temp = q[front++];
	return temp;
}

char Queue::getFront(){
	/* Kiển tra xem hàng đợi có rỗng không,
	   Nếu rỗng trả về lỗi */
	if(isEmpty()){
		cout << "ERROR: Queue is empty, can't get front element" << endl;
		return ERROR;
	}
	return q[front];
}

bool Queue::isEmpty(){
	return (front == 0 && rear == 0);
}

bool Queue::isFull(){
	return (rear == Q_SIZE);
}

void Queue::PrintQ(){
         if(!isEmpty()){
	        for(int i = front; i <= rear; i++){
		       cout << q[i] << " ";
	        }
	        cout << endl;
         }else{
                 cout << "NULL " << endl;
         }
}

int main()
{
    /* Hàm kiểm tra hoạt động của toàn bộ chương trinh
       In kết quả sau mỗi bước thực hiện */
   Queue Q; /* Tạo một thể hiện của Queue */
   Q.Enqueue('A');  Q.PrintQ();  
   Q.Enqueue('B');  Q.PrintQ();  
   Q.Enqueue('C');  Q.PrintQ();
   Q.Dequeue();	  Q.PrintQ();
   Q.Dequeue();	  Q.PrintQ();
   Q.Enqueue('D');  Q.PrintQ();
   Q.Enqueue('E');  Q.PrintQ();

   return 0;
}

Kết quả sau khi chạy chương trình:

Hình 6: Kết quả sau khi chạy chương trình

Các bạn cũng có thể xem mã nguồn trên gitlab tại đây.

Ngoài cách cài đặt chương trình bằng mảng một chiều, ta cũng có thể cài đặt hàng đợi bằng cách sử dụng danh sách liên kết. Các bạn có thể tham khảo mã nguồn được thực hiện bằng ngôn ngữ C tại đây.

Kết luận

Toàn bộ nội dung bài học này đã đề cập tới cách cài dặt cấu trúc hàng đợi và cách thức hoạt động của chúng.

Ưu điểm của cách này là dễ dàng cài đặt, chương trình thực hiện nhanh (chưa áp dụng kỹ thuật dịch). Tuy nhiên khuyết điểm của nó là gây lãng phí bộ nhớ.

Hàng đợi có thể được ứng dụng để làm:

Bộ đệm, chứa các yêu cầu.
Thuật toán tìm đường theo chiều rộng (BFS)

Ở bài tiếp theo chúng ta cùng tìm hiểu về cách cài đặt và hoạt động của hàng đợi vòng, là loại hàng đợi cải thiện được một số điểm yếu của hàng đợi tuyến tính.

Uncategorized

Hàng đợi

Giới thiệu về Hàng đợi (Queue)

Enqueue

Hàng đợi tuyến tính (Linear Queue)

Cặt đặt hàng đợi

Kết luận

Để lại một bình luận Hủy