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, 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). Queue sau phương pháp First-In-First-Out, tức là, các mục dữ liệu được lưu trữ đầu tiên sẽ được truy cập đầu tiên.

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.

Đại diện xếp hàng

Bây giờ chúng tôi hiểu rằng trong hàng đợi, chúng tôi truy cập cả hai đầu vì những lý do khác nhau. Sơ đồ sau đây đượ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, 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. Vì lợi ích của sự đơn giản, chúng tôi chịu trách nhiệm thi hàng đợi sử dụng mảng một chiều.

Hoạt động cơ bản

Các hoạt động xếp hàng 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 -

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

Ít chức năng hơn được yêu cầu để làm cho hoạt động hàng đợi được đề cập ở trên có hiệu quả. Đây là -

1. peek () - Gets các yếu tố ở phía trước của hàng đợi mà không cần loại bỏ nó.
2. isfull () - Kiểm tra xem hàng đợi đã đầy chưa.
3. isempty () - Kiểm tra nếu hàng đợi trống.

Trong hàng đợi, chúng tôi luôn xử lý dữ liệu (hoặc truy cập), được chỉ bởi con trỏ phía trước và trong khi ghi lại (hoặc lưu trữ) dữ liệu trong hàng đợi, chúng tôi có sự trợ giúp của con trỏ phía sau .

Trước 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 ở phía trước hàng đợi. Thuật toán của hàm peek () như sau -

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];
}

đầy đủ ()

Vì chúng tôi đang sử dụng mảng thứ nguyên đơn để thực hiện hàng đợi, chúng tôi chỉ cần kiểm tra con trỏ phía sau để đạt tới MAXSIZE để 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 tròn, thuật toán sẽ khác nhau. Thuật toán 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 mặt trước nhỏ hơn MIN hoặc 0, nó báo rằng hàng đợi chưa được khởi tạo, do đó trống.

Đây là mã lập trình 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 -

1. Bước 1 - Kiểm tra xem hàng đợi đã đầy chưa.
2. Bước 2 - Nếu hàng đợi đầy, tạo ra lỗi tràn và thoát.
3. 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.
4. Bước 4 - Thêm phần tử dữ liệu đến vị trí hàng đợi, nơi phía sau được trỏ đến.
5. 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 -

1. Bước 1 - Kiểm tra xem hàng đợi có trống không.
2. Bước 2 - Nếu hàng đợi trống, tạo ra lỗi tràn và thoát.
3. 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ỏ.
4. 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.
5. 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;
}

Được cập nhật: 16 tháng 4 lúc 2:31:33 | Lượt xem: 644