Cấu trúc dữ liệu trong Java - Ngăn xếp và hàng đợi

Xin chào! Hôm nay chúng ta sẽ nói về những thứ quan trọng đối với bất kỳ lập trình viên nào như cấu trúc dữ liệu . Wikipedia nói: Cấu trúc dữ liệu ( eng. datastructure ) là một đơn vị phần mềm cho phép bạn lưu trữ và xử lý nhiều dữ liệu cùng loại và/hoặc có liên quan về mặt logic trong điện toán. Định nghĩa này hơi khó hiểu, nhưng bản chất của nó rất rõ ràng. Cấu trúc dữ liệu là một loại lưu trữ nơi chúng tôi lưu trữ dữ liệu để sử dụng tiếp. Có rất nhiều cấu trúc dữ liệu trong lập trình. Rất thường xuyên, khi giải quyết một vấn đề cụ thể, điều quan trọng nhất là chọn cấu trúc dữ liệu phù hợp nhất cho mục đích này. Và bạn đã quen thuộc với nhiều người trong số họ! Ví dụ: với mảng . Và cả với Map(thường được dịch là “từ điển”, “bản đồ” hoặc “mảng kết hợp”). Điều rất quan trọng là phải hiểu: cấu trúc dữ liệu không bị ràng buộc với bất kỳ ngôn ngữ cụ thể nào . Đây chỉ đơn giản là những “bản thiết kế” trừu tượng, theo đó mỗi ngôn ngữ lập trình sẽ tạo ra các lớp riêng - việc triển khai cấu trúc này. Ví dụ: một trong những cấu trúc dữ liệu nổi tiếng nhất là danh sách liên kết . Bạn có thể vào Wikipedia, đọc về cách thức hoạt động của nó, những ưu điểm và nhược điểm của nó. Bạn có thể thấy định nghĩa của nó quen thuộc :) “Danh sách liên kết là một cấu trúc dữ liệu động cơ bản trong khoa học máy tính, bao gồm các nút, mỗi nút chứa cả dữ liệu đó và một hoặc hai liên kết (“liên kết”) đến nút tiếp theo và/hoặc danh sách nút trước đó” Vì vậy, đây là của chúng tôi LinkedList! Chính xác là như vậy :) Cấu trúc dữ liệu danh sách liên kết được triển khai bằng ngôn ngữ Java trong lớp LinkedList. Nhưng các ngôn ngữ khác cũng triển khai danh sách liên kết! Trong Python nó được gọi là “ llist”, trong Scala nó được gọi giống như trong Java - “ LinkedList“. Danh sách liên kết là một trong những cấu trúc dữ liệu phổ biến cơ bản, vì vậy bạn có thể tìm thấy cách triển khai nó bằng bất kỳ ngôn ngữ lập trình hiện đại nào. Điều tương tự với một mảng kết hợp. Đây là định nghĩa của nó từ Wikipedia: Mảng kết hợp là một kiểu dữ liệu trừu tượng (giao diện cho kho dữ liệu) cho phép lưu trữ các cặp có dạng “(khóa, giá trị)” và hỗ trợ các hoạt động thêm một cặp cũng như tìm kiếm. và xóa một cặp theo khóa. Không nhắc nhở bạn về bất cứ điều gì? :) Chính xác, đối với những người theo chủ nghĩa Java chúng tôi, mảng kết hợp là một giao diệnMap. Nhưng cấu trúc dữ liệu này cũng được triển khai bằng các ngôn ngữ khác! Ví dụ, các lập trình viên C# biết đến nó với cái tên “Dictionary”. Và trong ngôn ngữ Ruby, nó được triển khai trong một lớp có tên là “Hash”. Nói chung là bạn hiểu đại khái ý nghĩa là gì: cấu trúc dữ liệu là thứ chung cho mọi chương trình, được triển khai khác nhau ở từng ngôn ngữ cụ thể. Hôm nay chúng ta sẽ nghiên cứu hai cấu trúc như vậy và xem chúng được triển khai như thế nào trong Java - ngăn xếp và xếp hàng.

Ngăn xếp trong Java

Ngăn xếp là một cấu trúc dữ liệu đã biết. Nó rất đơn giản và khá nhiều đồ vật trong cuộc sống hàng ngày của chúng ta được “triển khai” dưới dạng một ngăn xếp. Hãy tưởng tượng một tình huống đơn giản: bạn sống trong một khách sạn và ban ngày bạn nhận được thư kinh doanh. Vì lúc đó bạn không có trong phòng nên nhân viên khách sạn chỉ cần đặt những bức thư gửi đến lên bàn của bạn. Đầu tiên anh đặt lá thư đầu tiên lên bàn. Rồi cái thứ hai đến và anh đặt nó lên trên cái thứ nhất. Anh ta đặt lá thư thứ ba lên trên lá thư thứ hai và lá thư thứ tư lên trên lá thư thứ ba. Bây giờ, hãy trả lời một câu hỏi đơn giản: bạn sẽ đọc lá thư nào đầu tiên khi vào phòng và nhìn thấy một chồng giấy trên bàn? Đúng vậy, bạn sẽ đọc được chữ cái trên cùng . Đó là, cái đến cuối cùng . Đây chính xác là cách một ngăn xếp hoạt động. Nguyên tắc hoạt động này được gọi là LIFO - “vào sau - ra trước” (“cuối cùng vào, ra trước”). Một ngăn xếp có thể hữu ích cho việc gì? Ví dụ: bạn đang tạo một số loại trò chơi bài bằng Java. Một bộ bài nằm trên bàn. Thẻ đã chơi sẽ bị loại bỏ. Bạn có thể triển khai cả bộ bài và bộ bài loại bỏ bằng cách sử dụng hai ngăn xếp. Người chơi rút bài từ trên cùng của bộ bài - nguyên tắc tương tự như với các chữ cái. Khi người chơi loại bỏ thẻ, thẻ mới sẽ được đặt lên trên thẻ cũ. Đây là bản phác thảo đầu tiên của trò chơi của chúng tôi, được triển khai bằng cách sử dụng ngăn xếp:

public class Card {

   public Card(String name) {
       this.name = name;
   }

   private String name;

   public String getName() {
       return name;
   }

   public void setName(String name) {
       this.name = name;
   }

   @Override
   public String toString() {
       return "Card{" +
               "name='" + name + '\'' +
               '}';
   }
}

import java.util.Stack;

public class SimpleCardGame {

   //  колода
   private Stack<Card> deck;

   //  сброс
   private Stack<Card> graveyard;

   public Card getCardFromDeck() {
       return deck.pop();
   }

   public void discard(Card card) {
       graveyard.push(card);
   }

   public Card lookTopCard() {

       return deck.peek();
   }

   //  ..геттеры, сеттеры и т.д.
}

Như chúng tôi đã nói trước đó, chúng tôi có hai ngăn xếp: bộ bài và loại bỏ. Cấu trúc dữ liệu ngăn xếp được triển khai trong Java ở định dạng java.util.Stack. Trong trò chơi bài của chúng tôi có 3 phương pháp mô tả hành động của người chơi:

• lấy một lá bài từ bộ bài (phương pháp getCardFromDeck());
• bỏ thẻ (phương thức discard());
• nhìn vào thẻ trên cùng (phương pháp lookTopCard()). Giả sử đây sẽ là cơ chế thưởng "Trí thông minh", cho phép người chơi tìm ra lá bài nào sẽ được sử dụng tiếp theo.

Bên trong các phương thức của chúng ta, các phương thức lớp được gọi Stack:

• push()- thêm một phần tử vào đầu ngăn xếp. Khi chúng ta loại bỏ một lá bài, nó sẽ nằm trên các lá bài đã bị loại bỏ trước đó;
• pop()— xóa phần tử trên cùng khỏi ngăn xếp và trả về nó. Phương pháp này lý tưởng để triển khai cơ chế “người chơi rút thẻ”.
• peek()- trả về phần tử trên cùng của ngăn xếp nhưng không xóa nó khỏi ngăn xếp

Hãy xem trò chơi của chúng tôi sẽ hoạt động như thế nào:

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       //  создаем колоду и добавляем в нее карты
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Рагнарос"));
       deck.push(new Card("Пират Глазастик"));
       deck.push(new Card("Сильвана Ветрокрылая"));
       deck.push(new Card("Миллхаус Манашторм"));
       deck.push(new Card("Эдвин ван Клифф"));

       //  создаем сброс
       Stack<Card> graveyard = new Stack<>();

       //  начинаем игру
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setGraveyard(graveyard);

       //  первый игрок берет 3 карты из колоды
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Какие карты достались первому игроку?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       //  первый игрок отправляет в сброс 3 своих карты
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("Какие карты находятся в сбросе?");
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
   }
}

Vì vậy, chúng tôi đã thêm năm lá bài vào bộ bài của mình. Người chơi đầu tiên lấy 3 trong số đó. Anh ấy đã nhận được thẻ gì? Đầu ra của bảng điều khiển:

Card{name='Эдвин ван Клифф'}
Card{name='Миллхаус Манашторм'}
Card{name='Сильвана Ветрокрылая'}

Hãy chú ý đến thứ tự các thẻ được xuất ra bảng điều khiển. Lá bài “Edwin Van Cleiff” là lá bài cuối cùng được đánh lên bộ bài (thứ năm liên tiếp) và là lá bài mà người chơi lấy đầu tiên. “Michhlaus” đánh bộ bài từ vị trí thứ hai đến cuối cùng và người chơi của nó chiếm vị trí thứ hai. “Sylvanas” đánh vào bộ bài thứ ba tính từ cuối và thuộc về người chơi thứ ba. Tiếp theo, người chơi loại bỏ thẻ của mình. Đầu tiên anh ta đánh rơi Edwin, sau đó là Millhouse, rồi đến Sylvanas. Sau đó, chúng tôi lần lượt xuất ra bảng điều khiển các thẻ bị loại bỏ: Xuất ra bảng điều khiển:

Card{name='Сильвана Ветрокрылая'}
Card{name='Миллхаус Манашторм'}
Card{name='Эдвин ван Клифф'}

Và một lần nữa chúng ta thấy ngăn xếp hoạt động như thế nào! Vật bị loại bỏ trong trò chơi của chúng ta cũng là một chồng (giống như bộ bài). "Edwin Van Clyffe" là người đầu tiên bị loại. Cái thứ hai bị đánh rơi là “Millhouse Manastorm” - và nằm đè lên Edwin trong thùng rác. Tiếp theo, Sylvanas bị loại bỏ - và lá bài này nằm trên Millhouse. Như bạn có thể thấy, không có gì phức tạp về cách hoạt động của ngăn xếp. Tuy nhiên, cần phải biết cấu trúc dữ liệu này - nó thường được hỏi trong các cuộc phỏng vấn và các cấu trúc dữ liệu phức tạp hơn thường được xây dựng trên cơ sở đó.

Xếp hàng

Hàng đợi (hoặc trong tiếng Anh là “Hàng đợi”) là một cấu trúc dữ liệu phổ biến khác. Giống như ngăn xếp, nó được triển khai bằng nhiều ngôn ngữ lập trình, bao gồm cả Java. Sự khác biệt giữa hàng đợi và ngăn xếp là gì? Hàng đợi của nó không dựa trên LIFO mà dựa trên một nguyên tắc khác - FIFO (“vào trước - ra trước”, “vào trước - ra trước”) . Dễ hiểu thôi, lấy làm ví dụ... hoặc ít nhất là một hàng người bình thường, có thật từ đời thực! Ví dụ, một hàng đợi đến cửa hàng. Nếu có năm người xếp hàng thì người đầu tiên xếp hàng sẽ được vào cửa hàng . Nếu có thêm một người (ngoài năm người xếp hàng) muốn mua thứ gì đó và xếp hàng thì người đó sẽ vào cửa hàng cuối cùng , tức là người thứ sáu. Khi làm việc với hàng đợi, các phần tử mới sẽ được thêm vào cuối và nếu bạn muốn lấy một phần tử thì nó sẽ được lấy từ đầu. Đây là nguyên tắc hoạt động cơ bản của nó mà bạn cần nhớ, nguyên lý của hàng đợi rất dễ hiểu bằng trực giác vì nó thường gặp trong đời thực. Điều đáng lưu ý riêng là trong Java hàng đợi được biểu thị không phải bằng một lớp mà bằng một giao diện - Queue. Nhưng đồng thời, hàng đợi trong Java là một giao diện có nhiều cách triển khai. Nếu xem tài liệu của Oracle, chúng ta sẽ thấy 4 giao diện khác nhau và một danh sách các lớp cực kỳ ấn tượng được kế thừa từ hàng đợi:

All Known Subinterfaces

BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

All Known Implementing Classes

AbstractQueue, ArrayBlockingQueue, ArrayDeque

ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

PriorityBlockingQueue, PriorityQueue, SynchronousQueue

Thật là một danh sách lớn! Tuy nhiên, tất nhiên, bây giờ bạn không cần phải ghi nhớ tất cả các lớp và giao diện này - đầu bạn có thể nổ tung :) Chúng ta sẽ chỉ xem xét một số điểm quan trọng và thú vị nhất. Đầu tiên, chúng ta hãy chú ý đến một trong bốn “giao diện phụ” của hàng đợi - Deque. Có gì đặc biệt về nó? Deque- Đây là hàng đợi hai chiều. Nó mở rộng chức năng của hàng đợi thông thường bằng cách cho phép bạn thêm các phần tử vào cả hai đầu (đầu và cuối hàng đợi) và lấy các phần tử từ cả hai đầu của hàng đợi. Deque được sử dụng rộng rãi trong phát triển. Hãy chú ý đến danh sách các lớp hàng đợi mà chúng tôi cung cấp ở trên. Danh sách này khá dài nhưng có điều gì quen thuộc với chúng ta ở đó không?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha, vậy là bạn cũ của chúng ta đang ở đây LinkedList! Tức là nó thực hiện giao diện Queue? Nhưng làm sao anh ta có thể xếp hàng được? Rốt cuộc LinkedList, đây là một danh sách được kết nối! Đúng, nhưng điều đó không ngăn nó trở thành hàng đợi :) Đây là danh sách tất cả các giao diện mà nó triển khai:

All Implemented Interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

Như bạn có thể thấy, LinkedListnó triển khai một giao diện Deque- hàng đợi hai chiều. Tại sao điều này là cần thiết? Nhờ đó, chúng ta có thể lấy được các phần tử từ cả phần đầu và phần cuối LinkedList. Và ngoài ra - thêm các phần tử vào cả phần đầu và phần cuối. Dưới đây là các phương thức được kế thừa LinkedListtừ giao diện Deque:

• peekFirst()— trả về (nhưng không xóa khỏi hàng đợi) phần tử đầu tiên.
• peekLast()— trả về (nhưng không xóa khỏi hàng đợi) phần tử cuối cùng.
• pollFirst()- trả về phần tử đầu tiên trong hàng đợi và xóa nó.
• pollLast()- trả về phần tử cuối cùng trong hàng đợi và xóa nó.
• addFirst()- thêm một phần tử mới vào đầu hàng đợi.
• addLast()- thêm một phần tử vào cuối hàng đợi.

Như bạn có thể thấy, LinkedListnó thực hiện đầy đủ chức năng của hàng đợi hai chiều! Và nếu chương trình cần chức năng như vậy, bạn sẽ biết rằng nó có thể được sử dụng :) Và bài giảng hôm nay của chúng ta sắp kết thúc. Cuối cùng, tôi sẽ cung cấp cho bạn một vài liên kết để đọc thêm. Đầu tiên, hãy chú ý đến bài viết dành riêng cho PriorityQueue - “hàng đợi ưu tiên”. Đây là một trong những triển khai thú vị và hữu ích nhất của Hàng đợi. Ví dụ: nếu có 50 người xếp hàng tại cửa hàng của bạn và 7 người trong số họ là khách hàng VIP, PriorityQueuenó sẽ cho phép bạn phục vụ họ trước! Một điều rất hữu ích, bạn có đồng ý không? :) Thứ hai, sẽ không thừa nếu một lần nữa nhắc đến cuốn sách “Cấu trúc dữ liệu và thuật toán trong Java” của Robert Laforet . Khi đọc cuốn sách này, bạn sẽ không chỉ tìm hiểu nhiều cấu trúc dữ liệu (bao gồm cả ngăn xếp và hàng đợi) mà còn có thể tự mình triển khai nhiều cấu trúc trong số đó! Ví dụ: hãy tưởng tượng nếu Java không có lớp Stack. Bạn sẽ làm gì nếu cần cấu trúc dữ liệu như vậy cho chương trình của mình? Tất nhiên là tôi sẽ phải tự viết nó. Khi đọc cuốn sách của Laforet, bạn thường sẽ làm như vậy. Nhờ đó, sự hiểu biết của bạn về cấu trúc dữ liệu sẽ rộng hơn nhiều so với việc chỉ học lý thuyết :) Hôm nay chúng ta đã học xong lý thuyết, nhưng lý thuyết mà không thực hành thì chẳng là gì cả! Các vấn đề sẽ không tự giải quyết được, vì vậy bây giờ là lúc để giải quyết chúng! :)