Bài 16 - Hàng đợi trong cấu trúc dữ liệu & giải thuật

Hàng đợi

Hàng đợi (Queue) là một cấu trúc dữ liệu trừu tượng. Không giống như ngăn xếp, một hàng đợi được mở ở cả hai đầu của nó. Một đầu luôn được sử dụng để chèn dữ liệu (enqueue) và đầu kia được sử dụng để xóa dữ liệu (dequeue). Đặc điểm của hàng đợi là FIFO (first in first out) - có nghĩa là vào trước ra trước. Đặt tên là hàng đợi bởi vì nó 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).

Một ví dụ trong thế giới thực của hàng đợi có thể là đường một chiều, trong đó phương tiện đi vào trước, thoát ra trước. Nhiều ví dụ thực tế hơn có thể được xem là hàng đợi tại cửa sổ bán vé và trạm dừng xe buýt.

Biểu diễn cấu trúc dữ liệu hàng đợi

Giờ thì có lẽ bạn đã tưởng tượng ra hàng đợi là gì rồi. Chúng ta có thể truy cập cả hai đầu của hàng đợi. Dưới đây là biểu diễn hàng đợi dưới dạng cấu trúc dữ liệu:

Như trong ngăn xếp, một hàng đợi cũng có thể được thực hiện bằng cách sử dụng Mảng, Danh sách liên kết, Con trỏ và Cấu trúc. Để đơn giản, chúng ta sẽ thực hiện các hàng đợi bằng cách sử dụng mảng một chiều.

Các hoạt động cơ bản

Các hoạt động trên cấu trúc dữ liệu hàng đợi có thể liên quan đến việc khởi tạo hoặc xác định hàng đợi, sử dụng nó và sau đó xóa hoàn toàn nó khỏi bộ nhớ. Ở đây chúng ta sẽ cố gắng hiểu các hoạt động cơ bản liên quan đến hàng đợi

• enqueue () - thêm (lưu trữ) một mục vào hàng đợi.
• dequeue () - xóa (truy cập) một mục khỏi hàng đợi.

Để sử dụng hàng đợi một cách hiệu quả, chúng ta cũng cần kiểm tra trạng thái của hàng đợi. Để phục vụ cho mục đích này, dưới đây là một số tính năng hỗ trợ khác của hàng đợi:

• Phương thức peek(): lấy phần tử ở đầu hàng đợi, mà không xóa phần tử này.
• Phương thức isFull(): kiểm tra xem hàng đợi là đầy hay không.
• Phương thức isEmpty(): kiểm tra xem hàng đợi là trống hay hay không.

Trong cấu trúc dữ liệu hàng đợi, chúng ta luôn luôn: (1) dequeue (xóa) dữ liệu được trỏ bởi con trỏ front và (2) enqueue (nhập) dữ liệu vào trong hàng đợi bởi sự giúp đỡ của con trỏ rear.

Trong phần tiếp chúng ta sẽ tìm hiểu về các tính năng hỗ trợ của cấu trúc dữ liệu hàng đợi.

peek ()

Giống như trong cấu trúc dữ liệu ngăn xếp, hàm này giúp chúng ta quan sát dữ liệu tại đầu hàng đợi. Giải thuật của hàm peek() là:

Thuật toán

begin procedure peek

   return queue[front]

end procedure

Thực hiện hàm peek () trong ngôn ngữ lập trình C -

Thí dụ

int peek() {

   return queue[front];

}

isfull()

Nếu khi chúng ta đang sử dụng mảng một chiều để triển khai hàng đợi, chúng ta chỉ cần kiểm tra con trỏ rear có tiến đến giá trị MAXSIZE hay không để xác định hàng đợi là đầy hay không. Trong trường hợp triển khai hàng đợi bởi sử dụng Danh sách liên kết vòng (Circular Linked List), giải thuật cho hàm isFull() sẽ khác.

Phần dưới đây là giải thuật của hàm isFull():

Thuật toán

begin procedure isfull 

   if rear equals to MAXSIZE

      return true

   else

      return false

   endif   

end procedure

Thực hiện hàm isfull () trong ngôn ngữ lập trình C -

Thí dụ

bool isfull() {

   if(rear == MAXSIZE - 1)

      return true;

   else

      return false;

}

isempty ()

Thuật toán của hàm isempty () -

Thuật toán

begin procedure isempty

   if front is less than MIN  OR front is greater than rear

      return true

   else

      return false

   endif

end procedure

Nếu giá trị của front là nhỏ hơn MIN hoặc 0 thì tức là hàng đợi vẫn chưa được khởi tạo, vì thế hàng đợi là trống.

Dưới đây là sự triển khai code trong ngôn ngữ C:

Thí dụ

bool isempty() {

   if(front < 0 || front > rear) 

      return true;

   else

      return false;

}

Hoạt động Enqueue

Hàng đợi duy trì hai con trỏ dữ liệu, phía trước và phía sau . Do đó, hoạt động của nó tương đối khó thực hiện hơn so với ngăn xếp.

Các bước sau đây nên được thực hiện để ghi dữ liệu (chèn) vào hàng đợi -

• Bước 1 - Kiểm tra xem hàng đợi đã đầy chưa.
• Bước 2 - Nếu hàng đợi đầy, tạo ra lỗi tràn và thoát.
• Bước 3 - Nếu hàng đợi không đầy, tăng con trỏ phía sau để trỏ khoảng trống tiếp theo.
• Bước 4 - Thêm phần tử dữ liệu vào vị trí hàng đợi, nơi phía sau đang chỉ.
• Bước 5 - trả lại thành công.

Đôi khi, chúng tôi cũng kiểm tra xem hàng đợi có được khởi tạo hay không, để xử lý mọi tình huống không lường trước.

Thuật toán cho hoạt động enqueue

procedure enqueue(data)       

   if queue is full

      return overflow

   endif   

   rear ← rear + 1

   queue[rear] ← data

   return true   

end procedure

Thực hiện enqueue () trong ngôn ngữ lập trình C -

Thí dụ

int enqueue(int data)      

   if(isfull())

      return 0;

   rear = rear + 1;

   queue[rear] = data;  

   return 1;

end procedure

Hoạt động Dequeue

Truy cập dữ liệu từ hàng đợi là một quá trình gồm hai nhiệm vụ - truy cập dữ liệu trong đó mặt trước đang trỏ và xóa dữ liệu sau khi truy cập. Các bước sau đây được thực hiện để thực hiện thao tác dequeue -

• Bước 1 - Kiểm tra xem hàng đợi có trống không.
• Bước 2 - Nếu hàng đợi trống, tạo ra lỗi tràn và thoát.
• Bước 3 - Nếu hàng đợi không trống, truy cập dữ liệu nơi mặt trước đang trỏ.
• Bước 4 - Tăng con trỏ phía trước để trỏ đến phần tử dữ liệu có sẵn tiếp theo.
• Bước 5 - Trả lại thành công.

Thuật toán cho hoạt động dequeue

procedure dequeue 

   if queue is empty

      return underflow

   end if

   data = queue[front]

   front ← front + 1

   return true

end procedure

Triển khai dequeue () trong ngôn ngữ lập trình C -

Thí dụ

int dequeue() {

   if(isempty())

      return 0;

   int data = queue[front];

   front = front + 1;

   return data;

}

- Hiếu Kiều -