Cấu trúc dữ liệu và thuật toán - Hàng đợi

Queue là một cấu trúc dữ liệu trừu tượng, hơi giống với Stacks. Không giống như ngăn xếp, hàng đợi được mở ở cả hai đầu của nó. Một đầu luôn dùng để chèn dữ liệu (enqueue) và đầu kia dùng để xóa dữ liệu (dequeue). Queue tuân theo phương pháp First-In-First-Out, tức là mục dữ liệu được lưu trước sẽ được truy cập trước.

Một ví dụ thực tế về hàng đợi có thể là đường một chiều có một làn xe, nơi xe đi vào trước, ra trước. Có thể thấy nhiều ví dụ thực tế hơn như xếp hàng ở cửa sổ soát vé và trạm dừng xe buýt.

Trình bày hàng đợi

Như bây giờ chúng ta hiểu rằng trong hàng đợi, chúng ta truy cập cả hai đầu vì những lý do khác nhau. Sơ đồ sau được đưa ra dưới đây cố gắng giải thích biểu diễn hàng đợi dưới dạng cấu trúc dữ liệu:

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

Hoạt động cơ bản

Các hoạt động 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 tôi 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.

Cần thêm một số chức năng để làm cho hoạt động hàng đợi nói trên hiệu quả. Đây là -

peek() - Lấy phần tử ở phía trước hàng đợi mà không cần xóa nó.
isfull() - Kiểm tra xem hàng đợi đã đầy chưa.
isempty() - Kiểm tra xem hàng đợi có trống không.

Trong hàng đợi, chúng tôi luôn xếp hàng (hoặc truy cập) dữ liệu, được trỏ bởi front con trỏ và trong khi đánh dấu (hoặc lưu trữ) dữ liệu trong hàng đợi, chúng tôi sẽ trợ giúp rear con trỏ.

Đầu tiên chúng ta hãy tìm hiểu về các chức năng hỗ trợ của hàng đợi -

nhìn trộm ()

Chức năng này giúp xem dữ liệu tại frontcủa hàng đợi. Thuật toán của hàm peek () như sau:

Algorithm

begin procedure peek
   return queue[front]
end procedure

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

Example

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

isfull ()

Vì chúng tôi đang sử dụng mảng một chiều để triển khai hàng đợi, chúng tôi chỉ cần kiểm tra xem con trỏ phía sau có đạt đến MAXSIZE hay không để xác định rằng hàng đợi đã đầy. Trong trường hợp chúng tôi duy trì hàng đợi trong một danh sách liên kết vòng tròn, thuật toán sẽ khác. Thuật toán của hàm isfull () -

Algorithm

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.

Example

bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

isempty ()

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

Algorithm

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 nhỏ hơn MIN hoặc 0, nó cho biết rằng hàng đợi chưa được khởi tạo, do đó trống.

Đây là mã lập trình C -

Example

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, front và rear. Do đó, các hoạt động của nó tương đối khó thực hiện hơn so với hoạt động của ngăn xếp.

Các bước sau nên được thực hiện để xếp (chèn) dữ liệu vào hàng đợi:

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

Đôi khi, chúng tôi cũng kiểm tra xem một 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 được.

Thuật toán cho hoạt động hàng đợi

procedure enqueue(data)      
   
   if queue is full
      return overflow
   endif
   
   rear ← rear + 1
   queue[rear] ← data
   return true
   
end procedure

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

Example

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 ở đâu frontlà trỏ và xóa dữ liệu sau khi truy cập. Các bước sau được thực hiện để thực hiệndequeue hoạt động -

Step 1 - Kiểm tra xem hàng đợi có trống không.
Step 2 - Nếu hàng đợi trống, tạo ra lỗi dòng dưới và thoát.
Step 3 - Nếu hàng đợi không trống, hãy truy cập dữ liệu ở đâu front đang trỏ.
Step 4 - Gia tăng front con trỏ để trỏ đến phần tử dữ liệu có sẵn tiếp theo.
Step 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

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

Example

int dequeue() {
   if(isempty())
      return 0;

   int data = queue[front];
   front = front + 1;

   return data;
}

Để có chương trình Queue hoàn chỉnh bằng ngôn ngữ lập trình C, vui lòng nhấp vào đây .