Sự khác biệt giữa hàng đợi tuyến tính và hàng đợi tròn

• 2019

Một hàng đợi tuyến tính đơn giản có thể được thực hiện theo ba cách khác nhau, trong đó một trong các loại là hàng đợi tròn. Sự khác biệt giữa hàng đợi tuyến tính và vòng tròn nằm ở các yếu tố cấu trúc và hiệu suất. Sự khác biệt cơ bản giữa hàng đợi tuyến tính và hàng đợi tròn là hàng đợi tuyến tính tiêu tốn nhiều không gian hơn hàng đợi tròn, trong khi hàng đợi tròn được nghĩ ra để hạn chế lãng phí bộ nhớ của hàng đợi tuyến tính.

Hàng đợi có thể được mô tả là cấu trúc dữ liệu tuyến tính không nguyên thủy theo thứ tự FIFO trong đó các phần tử dữ liệu được chèn từ một đầu (đầu sau) và bị xóa khỏi đầu kia (mặt trước). Các biến thể khác của hàng đợi là hàng đợi tròn, hàng đợi kết thúc gấp đôi và hàng đợi ưu tiên.

Biểu đồ so sánh

Cơ sở để so sánh	Hàng đợi tuyến tính	Hàng đợi thông tư
Căn bản	Sắp xếp các phần tử dữ liệu và hướng dẫn theo thứ tự lần lượt từng phần một.	Sắp xếp dữ liệu theo mẫu hình tròn trong đó phần tử cuối cùng được kết nối với phần tử đầu tiên.
Trình tự thực hiện nhiệm vụ	Nhiệm vụ được thực hiện theo thứ tự chúng được đặt trước (FIFO).	Trình tự thực hiện một nhiệm vụ có thể thay đổi.
Chèn và xóa	Phần tử mới được thêm vào từ phía sau và loại bỏ từ phía trước.	Chèn và xóa có thể được thực hiện tại bất kỳ vị trí nào.
Hiệu suất	Không hiệu quả	Hoạt động tốt hơn so với hàng đợi tuyến tính.

Định nghĩa của hàng đợi tuyến tính

Một hàng đợi tuyến tính là hợp lý đầu tiên trong danh sách ra thứ tự đầu tiên . Nó được gọi là tuyến tính vì nó giống với một đường thẳng trong đó các phần tử được đặt lần lượt từng phần tử. Nó chứa một bộ sưu tập đồng nhất các yếu tố trong đó các yếu tố mới được thêm vào ở một đầu và bị xóa khỏi đầu kia. Khái niệm về hàng đợi có thể được hiểu bằng ví dụ về một hàng đợi khán giả đang chờ bên ngoài quầy bán vé để lấy vé nhà hát. Trong hàng đợi này, người này tham gia vào phía sau của hàng đợi để lấy vé và vé được phát hành ở đầu trước của hàng đợi.

Có một số hoạt động được thực hiện trong hàng đợi

• Đầu tiên, hàng đợi được khởi tạo về 0 (tức là trống).
• Xác định xem hàng đợi có trống hay không.
• Xác định xem hàng đợi có đầy đủ hay không.
• Chèn phần tử mới từ phía sau (Enqueue).
• Xóa phần tử từ mặt trước (Dequeue).

Hàng đợi có thể được thực hiện trong hai cách

• Tĩnh (Sử dụng mảng)
• Tự động (Sử dụng con trỏ)

Hạn chế của hàng đợi tuyến tính là nó tạo ra một kịch bản trong đó không có phần tử mới nào có thể được thêm vào trong hàng đợi ngay cả khi hàng đợi chứa các khoảng trống. Tình huống trên được minh họa trong hình dưới đây. Ở đây phía sau đang chỉ vào chỉ mục cuối cùng trong khi tất cả các hộp đều trống, không có yếu tố mới nào có thể được thêm vào.

Định nghĩa hàng đợi thông tư

Hàng đợi tròn là một biến thể của hàng đợi tuyến tính giúp khắc phục hiệu quả giới hạn của hàng đợi tuyến tính. Trong hàng đợi tròn, phần tử mới được thêm vào ở vị trí đầu tiên của hàng đợi nếu phần cuối cùng bị chiếm dụng và không gian có sẵn. Khi nói đến hàng đợi tuyến tính, việc chèn chỉ có thể được thực hiện từ phía sau và xóa từ đầu trước. Trong một hàng đợi đầy đủ sau khi thực hiện một loạt các lần xóa liên tiếp trong hàng đợi phát sinh một tình huống nhất định trong đó không có yếu tố mới nào có thể được thêm vào ngay cả khi không gian có sẵn vì điều kiện dưới dòng (Phía sau = tối đa 1) vẫn tồn tại.

Hàng đợi tròn kết nối hai đầu thông qua một con trỏ trong đó phần tử đầu tiên xuất hiện sau phần tử cuối cùng. Nó cũng theo dõi phía trước và phía sau bằng cách thực hiện một số logic bổ sung để có thể theo dõi các yếu tố sẽ được chèn và xóa. Với điều này, hàng đợi tròn không tạo ra điều kiện tràn cho đến khi hàng đợi đầy đủ trong thực tế.

Một số điều kiện theo sau là hàng đợi tròn:

• Mặt trước phải trỏ đến yếu tố đầu tiên.
• Hàng đợi sẽ trống nếu Front = Rear.
• Khi một phần tử mới được thêm vào, hàng đợi được tăng theo giá trị một (Phía sau = Phía sau + 1).
• Khi một phần tử bị xóa khỏi hàng đợi, mặt trước được tăng thêm một (Front = Front + 1).

Sự khác biệt chính giữa hàng đợi tuyến tính và hàng đợi tròn

1. Hàng đợi tuyến tính là một danh sách có thứ tự trong đó các thành phần dữ liệu được sắp xếp theo thứ tự tuần tự. Ngược lại, hàng đợi tròn lưu trữ dữ liệu theo kiểu vòng tròn.
2. Hàng đợi tuyến tính tuân theo thứ tự FIFO để thực thi tác vụ (phần tử được thêm vào ở vị trí đầu tiên sẽ bị xóa ở vị trí đầu tiên). Ngược lại, trong hàng đợi tròn, thứ tự các thao tác được thực hiện trên một phần tử có thể thay đổi.
3. Việc chèn và xóa các phần tử được cố định trong hàng đợi tuyến tính tức là thêm vào từ phía sau và xóa từ phần đầu. Mặt khác, hàng đợi tròn có khả năng chèn và xóa phần tử từ bất kỳ điểm nào cho đến khi không có người.
4. Hàng đợi tuyến tính lãng phí không gian bộ nhớ trong khi hàng đợi tròn giúp sử dụng không gian hiệu quả.

Thực hiện hàng đợi tuyến tính

Thuật toán được đưa ra dưới đây minh họa việc thêm các phần tử trong hàng đợi:
Hàng đợi cần ba biến dữ liệu bao gồm một mảng để lưu trữ hàng đợi và biến khác để lưu trữ vị trí ban đầu phía trước và phía sau là -1.

 chèn (mục, hàng đợi, n, phía sau) {if (phía sau == n) sau đó in "tràn hàng đợi"; khác {phía sau = phía sau + 1; hàng đợi [phía sau] = mục; }} 

Thuật toán được đưa ra dưới đây minh họa việc xóa các phần tử trong hàng đợi:

 xóa_circular (mục, hàng đợi, phía sau, phía trước) {if (phía sau == phía trước) sau đó in "dòng chảy dưới hàng đợi"; khác {trước = trước + 1; mục = hàng đợi [phía trước]; }} 

Thực hiện hàng đợi tròn

Một thuật toán để giải thích việc thêm phần tử trong hàng đợi tròn:

 insert_circular (item, queue, phía sau, phía trước) {phía sau = (phía sau + 1) mod n; if (front == phía sau) thì in "queue is full"; other {queue [phía sau] = item; }} 

Thuật toán giải thích việc xóa phần tử trong hàng đợi tròn:

 xóa_circular (mục, hàng đợi, phía sau, phía trước) {if (front == phía sau) sau đó in ("hàng đợi trống"); khác {trước = trước + 1; mục = hàng đợi [phía trước]; }} 

Phần kết luận

Hàng đợi tuyến tính không hiệu quả trong một số trường hợp nhất định trong đó các phần tử được yêu cầu chuyển sang các khoảng trống để thực hiện thao tác chèn. Đó là lý do nó có xu hướng lãng phí không gian lưu trữ trong khi hàng đợi tròn sử dụng không gian lưu trữ thích hợp vì các yếu tố được thêm vào tại bất kỳ vị trí nào nếu có không gian trống.