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

CHÀO! Hôm nay chúng ta sẽ nói về một thứ cực kỳ quan trọng đối với bất kỳ lập trình viên nào: cấu trúc dữ liệu. Wikipedia cho biết: " Cấu trúc dữ liệu là định dạng tổ chức, quản lý và lưu trữ dữ liệu cho phép truy cập và sửa đổi hiệu quả. Chính xác hơn, cấu trúc dữ liệu là tập hợp các giá trị dữ liệu, mối quan hệ giữa chúng và các chức năng hoặc hoạt động có thể được áp dụng cho dữ liệu." Định nghĩa hơi khó hiểu, nhưng ý chính của nó thì rõ ràng. Cấu trúc dữ liệu là một loại kho lưu trữ nơi chúng tôi lưu trữ dữ liệu để sử dụng trong tương lai. Trong lập trình, có rất nhiều cấu trúc dữ liệu. Khi giải quyết các vấn đề cụ thể, điều quan trọng nhất thường là chọn cấu trúc dữ liệu phù hợp nhất cho vấn đề. Và bạn đã quen thuộc với nhiều người trong số họ! Ví dụ, bạn biết về mảng. Và bạn cũng đã quen thuộc vớiMap(cấu trúc dữ liệu này cũng có thể được gọi là "từ điển" hoặc "mảng kết hợp"). Điều rất quan trọng là phải hiểu rằng 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. Chúng chỉ đơn giản là những "bản thiết kế" trừu tượng mà mỗi ngôn ngữ lập trình sử dụng để tạo các lớp hoặc triển khai cấu trúc cụ thể của riêng nó. 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ể truy cập Wikipedia và đọc về cách thức hoạt động cũng như những ưu điểm và nhược điểm của nó. Có lẽ định nghĩa của nó sẽ có vẻ quen thuộc với bạn :) "Danh sách được liên kết là một tập hợp tuyến tính các phần tử dữ liệu, thứ tự của chúng không được xác định bởi vị trí vật lý của chúng trong bộ nhớ. Thay vào đó, mỗi phần tử trỏ đến phần tử tiếp theo." Điều đó mô tả người yêu dấu của chúng ta LinkedList, phải không? Vâng, và đó chính là nó :) Trong Java, cấu trúc dữ liệu "danh sách liên kết" được thực hiện bởi 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, cấu trúc dữ liệu này được gọi là " llist". Trong Scala, nó được gọi là " LinkedList", giống như trong Java. Danh sách được 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 sẽ thấy rằng nó được triển khai trong bất kỳ ngôn ngữ lập trình hiện đại nào. Điều tương tự cũng đúng với các mảng kết hợp. Đây là định nghĩa từ Wikipedia: "Một mảng kết hợp, bản đồ, bảng biểu tượng hoặc từ điển là một kiểu dữ liệu trừu tượng bao gồm một tập hợp các cặp (khóa, giá trị), sao cho mỗi khóa có thể xuất hiện nhiều nhất một lần trong bộ sưu tập." Điều đó có nhắc nhở bạn về bất cứ điều gì? :) Chuẩn rồi. Đối với chúng tôi, các nhà phát triển Java, một mảng kết hợp làMapgiao diện. 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ó dưới cái tên "Từ điển". Và trong Ruby, nó được triển khai trong một lớp gọi là "Hash". Chà, bạn hiểu rồi: cấu trúc dữ liệu là khái niệm phổ biến trong lập trình và mỗi ngôn ngữ lập trình triển khai chúng theo cách riêng của nó. Hôm nay chúng ta sẽ nghiên cứu hai cấu trúc như vậy — ngăn xếp và hàng đợi — và xem cách chúng được triển khai trong Java.

Ngăn xếp trong Java

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

   // Draw deck
   private Stack<Card> deck;
  
   // Discard pile
   private Stack<Card> discardPile;

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

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

   public Card lookAtTopCard() {

       return deck.peek();
   }
  
   // ...getters, setters, etc.
}

Như chúng tôi đã nói trước đó, chúng tôi có hai ngăn xếp: một bộ bài rút và một ngăn xếp loại bỏ. Trong Java, cấu trúc dữ liệu ngăn xếp được triển khai trong java.util.Stacklớp. 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 thẻ từ bộ bài ( getCardFromDeck()phương pháp )
• loại bỏ một thẻ ( discard()phương pháp)
• nhìn vào thẻ trên cùng ( lookAtTopCard()phương pháp). Giả sử đây là phần thưởng "Trí thông minh" cho phép người chơi tìm ra lá bài nào sẽ xuất hiện tiếp theo trong trò chơi.

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

• push()— thêm một mục vào đầu ngăn xếp. Khi chúng tôi gửi một thẻ đến đống loại bỏ, nó sẽ ở trên cùng của đống
• pop()- loại bỏ phần tử trên cùng khỏi ngăn xếp và trả lại nó. Phương pháp này là hoàn hảo để thực hiện các hành động trong đó 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 loại bỏ nó khỏi ngăn xếp

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

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       // Create a deck and add cards to it
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Ragnaros"));
       deck.push(new Card("Patches the Pirate"));
       deck.push(new Card("Sylvanas Windrunner"));
       deck.push(new Card("Millhouse Manastorm"));
       deck.push (new Card ("Edwin VanCleef"));

       // Create the discard pile
       Stack<Card> discardPile = new Stack<>();

       // Start the game
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setDiscardPile(discardPile);

       // The first player draws 3 cards from the deck
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Which cards went to the first player?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       // The first player discards 3 of his cards
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("What cards are in the discard pile?");
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
   }
}

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

Card{name='Edwin VanCleef"}
Card{name='Millhouse Manastorm'}
Card{name='Sylvanas Windrunner'}

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

Card{name='Sylvanas Windrunner'}
Card{name='Millhouse Manastorm'}
Card{name='Edwin VanCleef"}

Một lần nữa, chúng ta thấy ngăn xếp hoạt động như thế nào! Trong trò chơi của chúng tôi, bộ bài loại bỏ cũng là một bộ bài (giống như bộ bài rút). "Edwin VanCleef" bị loại bỏ đầu tiên. Lá bài bị loại bỏ thứ hai là Millhouse Manastorm, và nó được đặt lên trên Edwin trong đống bài bị loại bỏ. Sau đó, Sylvanas bị loại bỏ, và lá bài này được đặt lên trên Millhouse. Như bạn có thể thấy, không có gì phức tạp về ngăn xếp. Tuy nhiên, bạn cần biết cấu trúc dữ liệu này — nó thường được hỏi về nó trong các cuộc phỏng vấn xin việc và nó thường là cơ sở để xây dựng các cấu trúc dữ liệu phức tạp hơn.

Hàng đợi trong Java

Hàng đợi là một cấu trúc dữ liệu phổ biến khác. Ngoài ngăn xếp, nhiều ngôn ngữ lập trình, bao gồm cả Java, cũng triển khai cấu trúc dữ liệu hàng đợi. Sự khác biệt giữa hàng đợi và ngăn xếp là gì? Một hàng đợi không dựa trên nguyên tắc LIFO, mà dựa trên nguyên tắc FIFO ("vào trước, ra trước"). Nguyên tắc này rất dễ hiểu bằng cách xem xét, ví dụ, một dòng hoặc hàng đợi bình thường trong cuộc sống thực! Ví dụ, một hàng tại cửa hàng tạp hóa. Nếu có năm người xếp hàng, người đầu tiên được phục vụ sẽ là người bước vào hàng đầu tiên . Nếu một người khác (ngoài năm người đã xếp hàng) muốn mua thứ gì đó và xếp hàng, thì người đó sẽ được phục vụ cuối cùng, nghĩa là, thứ sáu. Khi làm việc với hàng đợi, các phần tử mới được thêm vào phần đuôi (phía sau), và muốn lấy phần tử nào thì phần tử đó sẽ được lấy từ phần đầu (phía trước). Đây là nguyên tắc chính bạn cần nhớ về cách hoạt động của hàng đợi. Hoạt động của hàng đợi rất trực quan, vì chúng tôi thường thấy hàng đợi trong cuộc sống thực. Cần lưu ý riêng rằng trong Java, một hàng đợi không được biểu diễn bởi một lớp mà bởi một giao diện: Hàng đợi. Hơn nữa, có rất nhiều cách triển khai giao diện hàng đợi này trong Java. Nếu chúng ta xem tài liệu của Oracle, chúng ta sẽ thấy rằng 4 giao diện khác nhau, cũng như một danh sách các lớp cực kỳ ấn tượng, kế thừa giao diện 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! Nhưng, tất nhiên, bạn không cần phải ghi nhớ tất cả các lớp và giao diện này ngay bây giờ - đầu của bạn có thể nổ tung :) Chúng tôi sẽ chỉ xem xét một vài đ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 con" của Queue: Deque . Điều gì làm cho nó trở nên đặc biệt? A Dequelà hàng đợi hai đầu. Nó mở rộng chức năng của hàng đợi thông thường, cho phép bạn thêm các phần tử vào cả hai đầu (ở đầu và đuôi) và lấy các phần tử từ cả hai đầu của hàng đợi. Hàng đợi kết thúc kép được sử dụng rộng rãi trong phát triển phần mềm. Hãy chú ý đến danh sách các lớp xếp hàng mà chúng tôi đã cung cấp ở trên. Danh sách này khá dài, nhưng nó có chứa điều gì quen thuộc không?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Hà! Đây là người bạn cũ của chúng ta LinkedList! Vì vậy, nó thực hiện giao diện Hàng đợi? Nhưng làm thế nào nó có thể là một hàng đợi? Rốt cuộc, a LinkedListlà một danh sách được liên kết! Đú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, LinkedListcài đặt Dequegiao diện (một lần nữa, điều này có nghĩa là hàng đợi kết thúc kép). Tại sao lại phải cần cái này? Điều này cho phép chúng tôi lấy các phần tử từ đầu và cuối của tệp LinkedList. Nó cũng cho phép chúng ta thêm các phần tử vào đầu và cuối. Dưới đây là các phương thức LinkedListnhận được từ Dequegiao diện:

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

Như bạn có thể thấy, LinkedListthực hiện đầy đủ chức năng của hàng đợi kết thúc kép! Và bạn cần chức năng như vậy trong chương trình của mình, bạn sẽ biết tìm nó ở đâu :) Bài học hôm nay đến đây là kết thúc. Tóm lại, tôi sẽ cung cấp cho bạn một vài liên kết để đọc thêm. Trước tiên, hãy chú ý đến bài viết này về PriorityQueue . Đây là một trong những Queuetriển khai thú vị và hữu ích nhất. Ví dụ: giả sử có 50 người đang 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. PriorityQueue sẽ cho phép bạn phục vụ họ trước! Công cụ rất hữu ích, phải không? :) Thứ hai, sẽ không hại gì nếu một lần nữa đề cập đến cuốn sách "Cấu trúc dữ liệu và thuật toán trong Java" của Robert Lafore. Đọc cuốn sách này, bạn sẽ không chỉ học được nhiều cấu trúc dữ liệu (bao gồm ngăn xếp và hàng đợi), mà còn tự mình thực hiện nhiều cấu trúc dữ liệu đó! Ví dụ, nếu Java không có lớp Stack thì sao? Bạn sẽ làm gì nếu cần một cấu trúc dữ liệu như vậy cho chương trình của mình? Bạn sẽ phải tự viết nó, tất nhiên. Khi bạn đọc cuốn sách của Lafore , bạn sẽ thường làm điều đó. Do đó, sự hiểu biết của bạn về cấu trúc dữ liệu sẽ sâu sắc hơn nhiều so với những gì bạn nhận được từ một nghiên cứu lý thuyết đơn giản :) Hôm nay chúng ta sẽ tổng kết lý thuyết, nhưng lý thuyết mà không có thực hành thì chẳng là gì cả! Các nhiệm vụ sẽ không tự giải quyết, vì vậy đã đến lúc giải quyết chúng! :)