Tại sao phải triển khai Hàng đợi làm Mảng Thông tư?

Question

Khi thực hiện một FIFO như Queues, người hướng dẫn của tôi luôn khuyên chúng tôi đại diện cho nó như là một mảng tròn và không phải trong một mảng thông thường. Tại sao?

Có phải vì sau này, chúng tôi sẽ kết thúc có dữ liệu rác trong mảng không?

Answer 1

Nếu bạn đang sử dụng số lượng Array-Slots/Elements cố định, bạn có thể dễ dàng tái chế các khe của mình theo cách sắp xếp tròn, vì bạn không cần phải sắp xếp lại các Yếu tố của mình. Bất cứ khi nào Element đầu tiên bị loại bỏ trong một sắp xếp giống như mảng, bạn phải di chuyển phần tử còn lại của bạn một vị trí về phía trước, vì vậy đầu không phải là null. Trong Hàng đợi tròn của bạn, bạn chỉ cần tăng con trỏ của mình lên Vị trí đầu tiên. Đó là ít hoạt động hơn trên bản cập nhật và mang đến cho bạn hiệu suất tốt hơn.

Nếu bạn đang xây dựng một Hàng đợi với số lượng khe không giới hạn/động, điều này không quan trọng, bởi vì bạn có thể giải phóng bộ nhớ động và cấp phát bộ nhớ.

Answer 2

Hãy tưởng tượng một Hàng đợi được hỗ trợ bởi một mảng trong đó chỉ mục 0 luôn là mục đầu tiên và chỉ mục n luôn là mục cuối cùng. Để loại bỏ một mục khỏi Hàng đợi, sau đó tất cả các mục 1 đến n phải được dịch chuyển về phía trước để đặt những gì trong chỉ mục 1 vào chỉ mục 0. Như bạn có thể hình dung, quá trình này sẽ mất một khoảng thời gian đáng kể cho các hàng đợi lớn và/hoặc hoạt động thường xuyên trên hàng đợi.

Bằng cách xử lý mảng dưới dạng bộ đệm tròn, trỏ đầu của hàng đợi đến mục tiếp theo khi một mục được xóa trở nên đơn giản như một nhiệm vụ duy nhất, điều này rõ ràng là có hiệu suất cao hơn nhiều.

Answer 3

Đó là chủ yếu là vấn đề về hiệu suất và sự đơn giản. Trong một mảng tiêu chuẩn, bạn sẽ phải thay đổi tất cả các phần tử mỗi khi bạn chọn một phần tử từ hàng đợi. Với mảng hình tròn, bạn chỉ cần cập nhật con trỏ và kích thước hiện tại ... hiệu quả hơn rất nhiều.

Answer 4

Tôi sẽ cung cấp cho bạn sự tương tự.

Hãy tưởng tượng hàng đợi tại nhà cung cấp đường phố nơi mọi người tham gia ở cuối dòng và được phân phát từ phía trước. Khi mỗi người được phục vụ, những người còn lại trong hàng đợi sẽ chuyển tiếp (thường lẩm bẩm về việc mất bao lâu) và những người mới tham gia vào cuối. Trong ví dụ này, mọi người phải di chuyển về phía trước để cho phép người khác tham gia vào dòng, nếu không thì kết thúc hàng đợi sẽ luôn đi xa hơn từ nhà cung cấp. Vì vậy, trong ví dụ này, máy chủ ở phía trước hàng đợi và giao dịch với bất kỳ ai ở phía trước hoặc không có ai.

Bây giờ hãy tưởng tượng nếu mọi người không di chuyển nhưng thay vì sau khi phục vụ người đứng đầu hàng đợi, người bán tự di chuyển xa hơn dọc theo hàng đợi, có hiệu lực di chuyển đến nơi người đứng đầu hàng đợi. Cuối cùng sau khi phục vụ 100 người máy chủ là nửa chừng xuống đường và sau 500 máy chủ bây giờ là ở đường phố tiếp theo, vv ... nó dừng ở đâu? Vì vậy, để thuận tiện cho người bán bản đồ một khu vực circuital lớn, nơi mọi người luôn có thể tham gia vào cuối hàng đợi và ông luôn luôn di chuyển đến người tiếp theo, nhưng hàng đợi vẫn ở một nơi. Anh ta chỉ đi vòng quanh hàng đợi phục vụ mọi người. Chắc chắn anh ta chỉ có thể phục vụ mọi người trong hàng đợi, nhưng với điều kiện anh ta đủ lớn để anh ta có thể theo kịp nhu cầu, và anh ta không phải rời khỏi khu vực bán hàng được chỉ định của mình.

Thực hiện tương tự ngược về máy tính ... trong ví dụ trước tiên có trình quản lý hàng đợi và khi các mục được bảo dưỡng, nó sẽ xáo trộn các mục dọc theo bộ đệm. Trong ví dụ giây thứ hai chương trình chạy cho đến khi không còn bộ nhớ nào để thêm vào mảng = đó là kích thước cố định (được xác định hoặc bị giới hạn bởi không gian).Trong ví dụ thứ ba, máy chủ di chuyển đến đầu hàng đợi như hàng đợi thứ hai nhưng mảng được cố định và chỉ có nhiều mục có thể tham gia hàng đợi, nhưng chúng vẫn sẽ nhận được dịch vụ FIFO.

tl; dr: Quản lý tài nguyên hiệu quả.

Answer 5

Thông tư Mảng là gì, nhưng mảng bình thường; chỉ con trỏ (trước/sau) sẽ được đặt lại về vị trí bắt đầu khi nó đến cuối. Nếu đây không phải là trường hợp và con trỏ duy nhất có thể di chuyển về phía trước thì chúng ta cần phải trao đổi các phần tử mảng lên trên cùng.

import java.lang.reflect.Array; 

/** 
* Based on 
* https://www.youtube.com/watch?v=z3R9-DkVtds 
* Data Structure & Alogorithm: Queue using Circular Array by Ripon Datta 
* 
* 1) When front and rear are equal there is no data. 
* 2) For each addition rear get incremented to new (empty) position, and for each removal 
* front get moved right to point to the next available element. 
* 3) Q Size (N - front + rear) % N :where N is total array size allocated 
* 4) Resize the array as part of adding new element and founding front and rear are equal 
* OR size is reached the MAX value. 
* 5) While resizing add the element from front to rear to the new array. 
* 
*/ 
public class QueueUsingCircularArray<T> { 
    T[] array; 
    int front = 0; 
    int rear = 0; 
    int N; 
    Class<T> clazz; 

    public QueueUsingCircularArray(Class<T> clazz, int size) { 
     N = size; 
     this.clazz = clazz; 
     array = (T[]) Array.newInstance(clazz, N); 
    } 

    public int size() { 
     return (N - front + rear) % N; 
    } 

    public void add(T data) { 
     int size = size(); 
     if (size == N - 1) { 
      resize(); 
     } 
     array[rear++] = data; 
     if (rear == N) { 
      rear = 0; 
     } 
    } 

    private void resize() { 
     int size = size(); 
     N = N * 2; 
     T[] newArray = (T[]) Array.newInstance(clazz, N); 
     int i = 0; 
     while (size > 0) { 
      size--; 
      newArray[i++] = array[front++]; 
      if (front == array.length) { 
       front = 0; 
      } 
     } 
     rear = i; 
     front = 0; 
     array = newArray; 
    } 

    public T remove() { 
     if (size() == 0) { 
      return null; 
     } 
     T data = array[front++]; 
     array[front - 1] = null; 
     if (front == N) { 
      front = 0; 
     } 
     return data; 
    } 

    public static void main(String[] args) { 
     QueueUsingCircularArray ca = new QueueUsingCircularArray(Integer.class, 5); 
     ca.add(1); 
     ca.add(2); 
     ca.add(3); 
     ca.remove(); 
     ca.add(4); 
     ca.add(5); 
     ca.add(55); //RESIZE 
     ca.remove(); 
     ca.remove(); 
     ca.add(6); 
     ca.add(7); 
     ca.add(8); 
     ca.add(9); 
     ca.add(10); 
    } 
}