Chào mừng bạn đến với Vimentor!

Hỏi đáp
Đăng ký

Hàng đợi

Trong phần này chúng tôi sẽ giới thiệu tới các bạn cấu trúc dữ liệu hàng đợi hay còn gọi là queue. Để hiểu rõ được các hoạt động và thực hiện của loại cấu trúc dữ liệu này bạn cần có những kiến thức về:

  • Mảng
  • Danh sách liên kết (linked list)

Bới vì hàng đợi có thể được cài đặt bằng cahcs sử dụng mảng hoặc danh sách liên kết.

Giới thiệu về Hàng đợi (Queue)

Hàng đợi là loại cấu trúc dữ liệu có tính chất ‘vào trước, ra trước” (First-in, First-out / FIFO). Nó giống như trường hợp hàng đợi ngoài thực tế khi ta mua hàng, người nào xếp hàng vào hàng đợi trước thì sẽ được phục vụ trước và ra khỏi hàng đợi trước.

Hàng đợi thường được ứng dụng làm bộ đệm máy tính để lưu lại những lênh mà máy chưa kịp sử lý. Và sau đó nó sẽ được xử lý thao trình tự FIFO. ví dụ như trường hợp của bộ đệm bàn phím, phím nào nhấn trước sẽ được xử lý trước.

Hàng đợi có thể được thể hiện như sau:

Hình 1: Mô tả cấu trúc dữ liệu hàng đợi

Với Front là vị trí đầu tiên và Rear là vị trí cuối hàng đợi.

Có hai thao tác chính với hàng đợi:

Enqueue: Chèn dữ liệu vào cuối hàng đợi (chèn vào sau Rear).

Dequeue: Lấy dữ liệu ra khỏi hàng đợi (lấy ra từ Front).

Ta cùng đi vào tìm hiểu chi tiết quá trình chèn dữ liệu vào và lấy dữ liệu ra từ hàng đợi để hiểu hơn về cách thức hoạt động của nó.

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.

Hình 2: Trước khi chèn dữ liệu vào hàng đợi

 

Hình 3: Sau khi chèn dữ liệu vào hàng đợi

Dequeue

Ngược lại với Enqueue, Dequeue là thao tác lấy dữ liệu ra khỏi hàng đợi.

Quá trình dequeue được mô tả trong các hình dưới đây.

Ở hình 5, Front là vị trí để lấy dữ liệu ra khỏi hàng đợi, và để chuẩn bị cho lần Dequeue tiếp theo ta phải tăng giá trị của Front lên 1.

Hàng đợi tuyến tính (Linear Queue)

Hàng đợi có hoạt động như đã miêu tả ở các phần trên được gọi là hàng đợi tuyến tính.

Hàng đợi tuyến tính thường được cài đặt bằng cách dùng mảng một chiều. Tuy nhiên cách làm này để lộ một số khuyết điểm.

Theo quá trính Dequeue đã được mô tả ở Hình 4 và Hình 5, nếu bạn chú ý kỹ ở quá trình Dequeue này thì bạn sẽ thấy rằng vị trí các ô nhớ chứa phần dữ liệu sau khi dequeue thì không được sử dụng bởi hàng đợi nữa. Vì khi Enqueue, ta sẽ chèn dữ liệu vào cuối hàng đợi chứ không tác động vào những vị trí đầu đã được dequeue, cho dù những vị trí đó đang rỗng.

Hãy cùng xem ví dụ sau:

Giả sử ta có hàng đợi được cài đặt bằng một mảng tĩnh có thể chứa tối đa 5 ký tự kiểu “char”.

char q[5];

 

Ta có một chuỗi các thao tác sau với hàng đợi trên:

Khi mới khởi tạo, queue rỗng.

Tới bước này ta không thể chèn thêm dữ liệu vào hàng đợi nữa cho dù hàng đợi chưa thực sự đầy. Để tiếp tục chèn dữ liệu vào hàng đợi, ta phải thực hiện thêm một thao tác ở đây, đó là dịch toàn bộ dữ liệu của hàng đợi về bên trái (về phía đầu hàng đợi). Tuy nhiên cái giá mà chúng ta phải trả cho thao tác này đó là thời gian thực hiện sẽ tăng lên đáng kể, nhất là khi kích thước và lượng dữ liệu trong hàng đợi lớn.

Trong trường hợp hàng đợi được cài đặt bằng mảng một chiều. Nó sẽ có kích thước cố định, như ở ví dụ trên là kích thước bằng 5.

Do vậy khi ta không thể chèn dữ liệu (Enqueue) vào vị trí vượt quá kích thước của hàng đợi. Điều kiện để biết được hàng đợi đã đầy là “Rear == kích thước của hàng đợi”.

Ta cũng không thể lấy dữ liệu ra khỏi hàng đợi (Dequeue) khi mà hàng đợi rỗng, ta đặt điều kiện cho hàng đợi rỗng là khi “Front == Rear == 0”.

Khi mà “Rear == kích thước của hàng đợi”, nhưng hàng đợi vẫn còn những khoảng trống ở các vị trí đầu, ta có thể thực hiện phương pháp dịch để tránh tính trạng lãng phí bộ nhớ. Tuy nhiên đây là một phương pháp không nhất thiết phải thực hiện khi cài đặt hàng đợi. Một khi áp dụng phương pháp này hiệu năng của chương trình sẽ bị giảm xuống, thời gian thực hiện chương trình tăng lên.

Cặt đặt hàng đợi

Sau đây là phương pháp đơn giản để cài đặt hàng đợi tuyến tính. Phương pháp này sử dụng mảng một chiều và ngôn ngữ thực hiện là C++.

Code đã được chạ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:
	/* Hàm khởi tạo, khi mới khởi tạo queue rỗng
	   front = rear = 0 */
	Queue(){
		front = 0;
		rear = 0;
	}
	/* Hàm chèn ký tự c vào hàng đợi q */
	void Enqueue(char c);

	/* Hàm lấy phần tử ở đầu ra khỏi hàng đợi */
	char Dequeue();

	/* Hàm trả về giá trị của phần tử đầu tiên trong hàng đợi */
	char getFront();

	/* Hàm kiểm tra xem hàng đợi có rỗng hay không */
	bool isEmpty();

	/* Hàm kiểm tra xem hàng đợi đã đầy hay chưa */
	bool isFull();

	/* Hàm in ra tất cả các phần tử trong hàng đợi */
	void PrintQ();
};

void Queue::Enqueue(char c){
	/* Kiểm tra xem hàng đợi đã đầy hay chưa,
	   Chỉ enqueue khi hà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 hàng đợi có rỗng không,
	   Chỉ Dequeue khi hà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 hàng đợi có rỗng không,
	   Nếu rỗng trả 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()
{
    /* Hàm kiểm tra hoạt động của toàn bộ chương trinh
       In kết quả sau mỗi bước thực hiện */
   Queue Q; /* Tạo một thể hiện củ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 quả sau khi chạy chương trình:

Hình 6: Kết quả sau khi chạy chương trình

Các bạn cũng có thể xem mã nguồn trên gitlab tại đây.

Ngoài cách cài đặt chương trình bằng mảng một chiều, ta cũng có thể cài đặt hàng đợi bằng cách sử dụng danh sách liên kết. Các bạn có thể tham khảo mã nguồn được thực hiện bằng ngôn ngữ C tại đây.

Kết luận

Toàn bộ nội dung bài học này đã đề cập tới cách cài dặt cấu trúc hàng đợi và cách thức hoạt động của chúng.

Ưu điểm của cách này là dễ dàng cài đặt, chương trình thực hiện nhanh (chưa áp dụng kỹ thuật dịch). Tuy nhiên khuyết điểm của nó là gây lãng phí bộ nhớ.

Hàng đợi có thể được ứng dụng để làm:

  • Bộ đệm, chứa các yêu cầu.
  • Thuật toán tìm đường theo chiều rộng (BFS)

Ở bài tiếp theo chúng ta cùng tìm hiểu về cách cài đặt và hoạt động của hàng đợi vòng, là loại hàng đợi cải thiện được một số điểm yếu của hàng đợi tuyến tính.

** Nếu bạn muốn viết các nội dung đặt biệt thì hãy làm theo hướng dẫn sau

Xem thêm 10 bình luận
Viết blog mới của bạn
Báo lỗi trang
Đang tải