Trình vòng lặp được triển khai như thế nào?

Loạt bài này lấy cảm hứng từ Algorithms, Phần I khóa học từ Đại học Princeton & Algorithms, 4th Edition. Toàn bộ loạt bài viết có thể được tìm thấy ở đây

Vấn đề là gì?

Điều gì sẽ xảy ra nếu chúng ta muốn lặp lại các mục trong một bộ sưu tập [ngăn xếp, hàng đợi,…] mà không tiết lộ cách triển khai, cho dù chúng ta đang sử dụng một mảng hay một danh sách được liên kết. Trong Java, nó có thể được thực hiện bằng cách triển khai Giao diện “Iterable”

Giao diện Iterable có một phương thức gọi là iterator. Phương thức này trả về một đối tượng “Iterator”

Giao diện Iterator là giao diện có các phương thức next và hasNext. Lớp triển khai giao diện iterator sẽ được sử dụng để lặp qua các mục trong bộ sưu tập

Bây giờ, để hiển thị ví dụ về cách sử dụng các giao diện này để tạo bộ sưu tập có thể lặp lại, chúng tôi sẽ sử dụng Ngăn xếp làm ví dụ. Tuy nhiên, bạn có thể áp dụng các bước tương tự cho bất kỳ loại bộ sưu tập nào mà bạn có

Đầu tiên, chúng ta cần xem một lớp Stack có thể trông như thế nào

public class Stack {
    private Node first = null;

    private class Node {
        Item item;
        Node next;
    }
    
    public void push[Item item] { /* … */ }
    public Item pop[] { /* … */ }
}

Nó có thể được thực hiện bằng cách sử dụng một danh sách được liên kết hoặc một mảng. Dù bằng cách nào, bạn sẽ làm theo các bước tương tự

1. Triển khai giao diện Iterable

Lớp Stack nên triển khai Giao diện Iterable

import java.util.Iterator;public class Stack implements Iterable { /* … */ }

Lưu ý rằng Iteratble và Iterator đều là các giao diện chung. Vì vậy, lớp Stack cũng phải là lớp chung. Bởi vì bạn sẽ lặp lại các mục thuộc loại chung trong ngăn xếp

2. Ghi đè Phương thức lặp

Ghi đè phương thức của Iterable Interface được gọi là iterator. Nó trả về một đối tượng Iterator thuộc loại chung

public Iterator iterator[] { return new StackIterator[]; }

Bây giờ, rõ ràng là chúng ta cần tạo một lớp có tên là “StackIterator”, lớp này cần triển khai Giao diện Iterator

3. Triển khai giao diện Iterator

Tạo một lớp bên trong thực hiện Giao diện Iterator. Bạn sẽ cần duy trì tham chiếu đến mục hiện tại mà trình vòng lặp trỏ đến

private class StackIterator implements Iterator {
    private Node current = first;
}

4. Ghi đè các phương thức next và hasNext

public boolean hasNext[]  { return current != null;  }
    
public Item next[] {
    if [!hasNext[]] throw new NoSuchElementException[];
    Item item = current.item;
    current = current.next; 
    return item;
}

Ngăn xếp được thực hiện với mảng

Một lần nữa, bạn sẽ làm theo các bước tương tự. Chỉ cần một số thay đổi nhỏ để làm việc với mảng thay vì danh sách được liên kết

private class StackIterator implements Iterator {
    private int i = N;    public boolean hasNext[]  { return i > 0;  }
    
    public Item next[] {
        if [!hasNext[]] throw new NoSuchElementException[];
        return s[--i];
    }
}

Các cách khác để tạo một bộ sưu tập có thể lặp lại?

Vâng, có. Bạn có thể tạo một bộ sưu tập Có thể lặp lại bằng cách sử dụng một bộ sưu tập Có thể lặp lại khác

Ví dụ: có Bản đồ, một tập hợp các cặp khóa-giá trị, nơi chúng tôi muốn lặp lại các khóa. Chúng tôi có thể lưu trữ tất cả các khóa trong ngăn xếp hoặc hàng đợi [đối tượng Iterable] và sử dụng ngăn xếp hoặc hàng đợi đó để lặp lại các khóa

Có hai cách để làm điều đó, một cách là triển khai Giao diện có thể lặp lại trong lớp Bản đồ [giống như chúng ta đã làm với ngăn xếp]

Việc triển khai phương thức iterator[] trong lớp Map rất đơn giản; . Đây là cách triển khai chính xác như chúng ta đã làm với ngăn xếp

public class Map implements Iterable {
    // ...

    public Iterator iterator[] {
        Queue queue = new Queue[];
        for [int i = 0; i < N; i++] 
            queue.enqueue[keys[i]];
        return queue.iterator[];    // return an Iterator object
    }
}

Một cách khác là trả về chính đối tượng Iterable. Do đó, không cần lớp Bản đồ triển khai Giao diện Iterable. Chỉ cần xác định một phương thức, chẳng hạn như keys[], sẽ lấp đầy đối tượng Iterable bằng các phím và trả về nó. Bây giờ, chúng ta có thể sử dụng đối tượng Iterable được trả về để lặp lại các phím

Nhược điểm của cách tiếp cận này là Bản đồ không phải là một đối tượng Iterable, vì nó không triển khai Giao diện Iterable. Chúng ta phải sử dụng phương thức keys[] để truy cập vào một đối tượng Iterable, đối tượng này sẽ được sử dụng để lặp lại các phím

public class Map {
    // ...

    public Iterable keys[] {
        Queue queue = new Queue[];
        for [int i = 0; i < N; i++] 
            queue.enqueue[keys[i]];
        return queue;               // return an Iterable object
   }
}

Bây giờ, đã đến lúc nếm trải kết quả của những gì chúng ta đã làm cho đến nay. Chúng ta có thể viết một đoạn mã thanh lịch để lặp lại các mục trong bộ sưu tập mà không tiết lộ cách triển khai

Trình vòng lặp được triển khai trong C++ như thế nào?

Iterator được triển khai ở đâu trong Java?

Iterator có triển khai Iterable không?

Trình vòng lặp hoạt động như thế nào trong Java?