โครงสร้างข้อมูลใน Java - สแต็กและคิว

สวัสดี! วันนี้เราจะพูดถึงสิ่งสำคัญสำหรับโปรแกรมเมอร์เช่นโครงสร้างข้อมูล Wikipedia บอกว่า: โครงสร้างข้อมูล ( อังกฤษ โครงสร้างข้อมูล ) เป็นหน่วยซอฟต์แวร์ที่ช่วยให้คุณสามารถจัดเก็บและประมวลผลข้อมูลประเภทเดียวกันและ/หรือข้อมูลเชิงตรรกะจำนวนมากในการคำนวณ คำจำกัดความนั้นค่อนข้างสับสนเล็กน้อย แต่สาระสำคัญของมันชัดเจน โครงสร้างข้อมูลคือการจัดเก็บข้อมูลประเภทหนึ่งที่เราจัดเก็บข้อมูลเพื่อใช้ต่อไป มีโครงสร้างข้อมูลที่หลากหลายในการเขียนโปรแกรม บ่อยครั้งเมื่อแก้ไขปัญหาเฉพาะ สิ่งที่สำคัญที่สุดคือการเลือกโครงสร้างข้อมูลที่เหมาะสมที่สุดสำหรับจุดประสงค์นี้ และคุณคุ้นเคยกับหลาย ๆ คนแล้ว! ตัวอย่างเช่นกับอาร์เรย์ และด้วยMap(ซึ่งมักจะแปลว่า "พจนานุกรม", "แผนที่" หรือ "อาเรย์แบบเชื่อมโยง") สิ่งสำคัญคือต้องเข้าใจ: โครงสร้างข้อมูลไม่ได้เชื่อมโยงกับภาษาใดภาษาหนึ่งโดยเฉพาะ สิ่งเหล่านี้เป็นเพียง "พิมพ์เขียว" แบบนามธรรมตามที่แต่ละภาษาการเขียนโปรแกรมสร้างคลาสของตัวเอง - การใช้งานโครงสร้างนี้ ตัวอย่างเช่น หนึ่งในโครงสร้างข้อมูลที่มีชื่อเสียงที่สุดคือรายการที่เชื่อมโยง คุณสามารถไปที่ Wikipedia อ่านเกี่ยวกับวิธีการทำงาน มีข้อดีและข้อเสียอะไรบ้าง คุณอาจพบว่าคำจำกัดความคุ้นเคย :) “รายการที่เชื่อมโยงคือโครงสร้างข้อมูลไดนามิกพื้นฐานในวิทยาการคอมพิวเตอร์ ซึ่งประกอบด้วยโหนด ซึ่งแต่ละโหนดจะมีทั้งข้อมูลและลิงก์หนึ่งหรือสองลิงก์ (“ลิงก์”) ไปยังลิงก์ถัดไปและ/หรือ รายการโหนดก่อนหน้า” นี่คือของเราLinkedList! นั่นคือวิธีที่มันเป็น :) โครงสร้างข้อมูลรายการ ที่เชื่อมโยงถูกนำไปใช้ในภาษา Java ในคลาส LinkedListแต่ภาษาอื่นก็ใช้รายการที่เชื่อมโยงด้วย! ใน Python เรียกว่า " llist" ใน Scala เรียกว่าเหมือนกับใน Java - " LinkedList" Linked List เป็นหนึ่งในโครงสร้างข้อมูลพื้นฐานทั่วไป ดังนั้นคุณจึงสามารถนำไปใช้ได้ในภาษาการเขียนโปรแกรมสมัยใหม่ สิ่งเดียวกันกับอาร์เรย์ที่เชื่อมโยง นี่คือคำจำกัดความจากวิกิพีเดีย: อาร์เรย์แบบเชื่อมโยงเป็นประเภทข้อมูลเชิงนามธรรม (อินเทอร์เฟซไปยังที่เก็บข้อมูล) ที่ช่วยให้สามารถจัดเก็บคู่ของรูปแบบ "(คีย์, ค่า)" และสนับสนุนการดำเนินการของการเพิ่มคู่ เช่นเดียวกับการค้นหา และลบคู่ด้วยปุ่ม ไม่เตือนคุณถึงอะไรเลยเหรอ? :) สำหรับพวกเราชาว Javaists แล้ว อาเรย์แบบเชื่อมโยงคืออินเทอร์เฟซMap. แต่โครงสร้างข้อมูลนี้ก็ถูกนำไปใช้ในภาษาอื่นด้วย! ตัวอย่างเช่น โปรแกรมเมอร์ C# รู้จักสิ่งนี้ภายใต้ชื่อ “พจนานุกรม” และในภาษา Ruby มันถูกนำไปใช้ในคลาสที่เรียกว่า "Hash" โดยทั่วไป คุณจะเข้าใจความหมายโดยคร่าวว่า โครงสร้างข้อมูลเป็นสิ่งที่พบได้ทั่วไปในการเขียนโปรแกรมทั้งหมด ซึ่งมีการใช้งานที่แตกต่างกันในแต่ละภาษา วันนี้เราจะศึกษาโครงสร้างดังกล่าวสองโครงสร้างและดูวิธีการนำไปใช้ใน Java - สแต็กและคิว

สแต็กใน Java

สแต็กเป็นโครงสร้างข้อมูลที่รู้จัก มันง่ายมากและมีวัตถุมากมายในชีวิตประจำวันของเราถูก "นำไปใช้" เป็นกองซ้อน ลองนึกภาพสถานการณ์ง่ายๆ: คุณอาศัยอยู่ในโรงแรม และในระหว่างวัน คุณได้รับจดหมายธุรกิจ เนื่องจากตอนนั้นคุณไม่ได้อยู่ในห้อง พนักงานโรงแรมจึงวางจดหมายที่เข้ามาบนโต๊ะของคุณ ก่อนอื่นเขาวางอักษรตัวแรกไว้บนโต๊ะ แล้วอันที่สองก็มาวางทับอันแรก เขาวางจดหมายฉบับที่สามไว้บนจดหมายฉบับที่สอง และจดหมายฉบับที่สี่ไว้บนจดหมายฉบับที่สาม ตอนนี้ ตอบคำถามง่ายๆ: คุณจะอ่านจดหมายอะไรเป็นอันดับแรกเมื่อมาถึงห้องและเห็นกองอยู่บนโต๊ะ ถูกต้องคุณจะอ่านจดหมายด้านบน นั่นคืออันที่มาทันเวลา นี่คือวิธีการทำงานของสแต็ก หลักการทำงานนี้เรียกว่าLIFO - "เข้าหลัง - ออกก่อน" ("เข้าหลังออกก่อน") Stack มีประโยชน์อย่างไร? ตัวอย่างเช่น คุณกำลังสร้างเกมไพ่บางประเภทใน Java สำรับไพ่อยู่บนโต๊ะ ไพ่ที่เล่นจะถูกทิ้ง คุณสามารถใช้ทั้งสำรับและทิ้งได้โดยใช้สองสแต็ค ผู้เล่นจั่วไพ่จากด้านบนของสำรับ - หลักการเดียวกับตัวอักษร เมื่อผู้เล่นทิ้งไพ่ ไพ่ใหม่จะถูกวางทับไพ่เก่า ต่อไปนี้คือลักษณะร่างแรกของเกมของเราที่นำไปใช้งานโดยใช้สแต็ก:

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();
   }

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

ดังที่เราได้กล่าวไว้ก่อนหน้านี้ เรามีสองกอง: สำรับและกองทิ้ง โครงสร้างข้อมูลสแต็กถูกนำไปใช้ใน Java ในjava.util.Stack. ในเกมไพ่ของเรามี 3 วิธีที่อธิบายการกระทำของผู้เล่น:

• นำไพ่ออกจากสำรับ (วิธีgetCardFromDeck());
• ทิ้งการ์ด (วิธีdiscard());
• ดูที่การ์ดบนสุด (วิธีlookTopCard()) สมมติว่านี่จะเป็นกลไกโบนัส "ความฉลาด" ซึ่งจะช่วยให้ผู้เล่นค้นหาว่าการ์ดใบใดที่จะเข้ามาเล่นต่อไป

ภายในวิธีการของเรา วิธีการเรียนเรียกว่าStack:

• push()- เพิ่มองค์ประกอบที่ด้านบนของสแต็ก เมื่อเราทิ้งการ์ด มันจะไปอยู่ด้านบนของการ์ดที่ถูกทิ้งก่อนหน้านี้
• pop()— ลบองค์ประกอบด้านบนออกจากสแต็กแล้วส่งคืน วิธีนี้เหมาะอย่างยิ่งสำหรับการนำกลไก "ผู้เล่นจั่วไพ่" ไปใช้
• peek()- ส่งคืนองค์ประกอบด้านบนของสแต็ก แต่ไม่ได้ลบออกจากสแต็ก

มาดูกันว่าเกมของเราจะทำงานอย่างไร:

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());
   }
}

ดังนั้นเราจึงได้เพิ่มไพ่ห้าใบเข้าเด็คของเรา ผู้เล่นคนแรกเอาไป 3 อัน เขาได้บัตรอะไรบ้าง? เอาต์พุตคอนโซล:

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

ให้ความสนใจกับลำดับที่การ์ดถูกส่งออกไปยังคอนโซล การ์ด “Edwin Van Cleiff” เป็นการ์ดใบสุดท้ายที่ตีสำรับ (ใบที่ห้าติดต่อกัน) และเป็นไพ่ที่ผู้เล่นได้ก่อน “Michhlaus” เป็นตัวที่สองที่อยู่บนสำรับคนสุดท้าย และผู้เล่นก็ขึ้นเป็นอันดับสอง “ซิลวานาส” โจมตีสำรับที่สามจากท้ายสุด และไปหาผู้เล่นคนที่สาม จากนั้นผู้เล่นจะทิ้งไพ่ของเขา ก่อนอื่นเขาปล่อยเอ็ดวิน จากนั้นก็มิลล์เฮาส์ แล้วก็ซิลวานาส หลังจากนั้นเราจะส่งออกการ์ดที่อยู่ในทิ้งของเราทีละรายการไปยังคอนโซล: ส่งออกไปยังคอนโซล:

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

และอีกครั้งที่เราได้เห็นว่าสแต็กทำงานอย่างไร! การทิ้งในเกมของเราก็เป็นการกองซ้อนเช่นกัน (เช่นเดียวกับสำรับ) “เอ็ดวิน ฟาน คลิฟฟ์” โดนดรอปเป็นคนแรก สิ่งที่สองที่ดรอปคือ "Millhouse Manastorm" - และวางทับ Edwin ในถังขยะ ถัดไป ซิลวานาสถูกทิ้ง - และการ์ดใบนี้วางอยู่บนมิลล์เฮาส์ อย่างที่คุณเห็น ไม่มีอะไรซับซ้อนเกี่ยวกับวิธีการทำงานของสแต็ก อย่างไรก็ตาม จำเป็นต้องรู้โครงสร้างข้อมูลนี้ - มักถูกถามถึงในการสัมภาษณ์ และโครงสร้างข้อมูลที่ซับซ้อนมากขึ้นมักถูกสร้างขึ้นบนพื้นฐานของโครงสร้างข้อมูลนี้

คิว

คิว (หรือในภาษาอังกฤษเรียกว่า "คิว") เป็นอีกหนึ่งโครงสร้างข้อมูลทั่วไป เช่นเดียวกับสแต็ก มันถูกนำไปใช้ในภาษาการเขียนโปรแกรมหลายภาษา รวมถึง Java ความแตกต่างระหว่างคิวและสแต็กคืออะไร? คิว ของมันไม่ได้ขึ้นอยู่กับ LIFO แต่ใช้หลักการอื่น - FIFO (“เข้าก่อน - ออกก่อน”, “เข้าก่อน - ออกก่อน”) . เข้าใจง่าย ยกตัวอย่าง... หรืออย่างน้อยก็คิวธรรมดาจากชีวิตจริง! เช่น การต่อคิวเข้าร้าน หากมีคนต่อแถวห้าคนคนแรกในแถวจะเข้าไปในร้าน หากมีอีกคนหนึ่ง (นอกเหนือจากห้าคนในแถว) ต้องการซื้อของและเข้าแถว เขาจะเข้าไปในร้านเป็นคนสุดท้ายนั่นคือคนที่หก เมื่อทำงานกับคิว องค์ประกอบใหม่จะถูกเพิ่มที่ส่วนท้าย และหากคุณต้องการรับองค์ประกอบ องค์ประกอบนั้นจะถูกนำไปตั้งแต่ต้น นี่คือหลักการพื้นฐานของการทำงานซึ่งคุณต้องจำไว้ หลักการของคิวนั้นง่ายต่อการเข้าใจโดยสัญชาตญาณเนื่องจากมักพบในชีวิตจริง เป็นที่น่าสังเกตว่าใน Java คิวไม่ได้แสดงโดยคลาส แต่โดยอินเทอร์เฟซQueue- แต่ในขณะเดียวกัน คิวใน Java ก็เป็นอินเทอร์เฟซที่มีการใช้งานหลายอย่าง หากเราดูเอกสารของ Oracle เราจะเห็นว่าอินเทอร์เฟซที่แตกต่างกัน 4 แบบและรายการคลาสที่น่าประทับใจอย่างยิ่งได้รับการสืบทอดมาจากคิว:

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

รายการใหญ่มาก! แต่แน่นอนว่าคุณไม่จำเป็นต้องจำคลาสและอินเทอร์เฟซเหล่านี้ทั้งหมดตอนนี้ - หัวของคุณอาจระเบิดได้ :) เราจะดูเพียงประเด็นที่สำคัญและน่าสนใจที่สุดสองสามจุดเท่านั้น ก่อนอื่นมาใส่ใจกับหนึ่งในสี่ "อินเทอร์เฟซย่อย" ของคิว - Deque. มีอะไรพิเศษเกี่ยวกับเรื่องนี้? Deque- นี่คือคิวสองทาง ขยายฟังก์ชันการทำงานของคิวปกติโดยอนุญาตให้คุณเพิ่มองค์ประกอบที่ปลายทั้งสองข้าง (จุดเริ่มต้นและจุดสิ้นสุดของคิว) และรับองค์ประกอบจากปลายทั้งสองด้านของคิว Deque ใช้กันอย่างแพร่หลายในการพัฒนา ให้ความสนใจกับรายการคลาสคิวที่เราให้ไว้ข้างต้น รายการค่อนข้างยาว แต่มีอะไรที่เราคุ้นเคยบ้างไหม?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

ฮ่าๆ เพื่อนเก่าเรามาแล้วLinkedList! นั่นคือมันใช้อินเทอร์เฟซQueue? แต่เขาจะเป็นคิวได้อย่างไร? ท้ายที่สุดLinkedListนี่คือรายการที่เชื่อมต่อกัน! จริง แต่นั่นไม่ได้หยุดไม่ให้เป็นคิว :) นี่คือรายการอินเทอร์เฟซทั้งหมดที่นำไปใช้:

All Implemented Interfaces:

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

อย่างที่คุณเห็นLinkedListมันใช้อินเทอร์เฟซDeque- คิวแบบสองทาง เหตุใดจึงจำเป็น? ด้วยเหตุนี้เราจึงสามารถรับองค์ประกอบได้จากทั้งจุดเริ่มต้นและจุดสิ้นสุดLinkedList. และยังเพิ่มองค์ประกอบทั้งจุดเริ่มต้นและจุดสิ้นสุด ต่อไปนี้เป็นวิธีการที่สืบทอดมาLinkedListจากอินเทอร์เฟซDeque:

• peekFirst()— ส่งคืน (แต่ไม่ได้ลบออกจากคิว) องค์ประกอบแรก
• peekLast()— ส่งคืน (แต่ไม่ได้ลบออกจากคิว) องค์ประกอบสุดท้าย
• pollFirst()- ส่งคืนองค์ประกอบแรกจากคิวและลบออก
• pollLast()- ส่งคืนองค์ประกอบสุดท้ายจากคิวและลบออก
• addFirst()— เพิ่มองค์ประกอบใหม่ที่จุดเริ่มต้นของคิว
• addLast()— เพิ่มองค์ประกอบที่ส่วนท้ายของคิว

อย่างที่คุณเห็นLinkedListมันใช้ฟังก์ชันการทำงานของคิวแบบสองทางอย่างเต็มที่! และหากจำเป็นต้องใช้ฟังก์ชันดังกล่าวในโปรแกรมก็จะรู้ว่าสามารถใช้งานได้ :) และการบรรยายของเราในวันนี้กำลังจะสิ้นสุดลง สุดท้ายนี้ ฉันจะให้ลิงก์สองสามลิงก์แก่คุณเพื่ออ่านเพิ่มเติม ขั้นแรก ให้ใส่ใจกับบทความเกี่ยวกับ PriorityQueue - "คิวลำดับความสำคัญ" นี่เป็นหนึ่งในการใช้งาน Queue ที่น่าสนใจและมีประโยชน์ที่สุด ตัวอย่างเช่น หากมีคนต่อแถวที่ร้านของคุณ 50 คน และ 7 คนในนั้นเป็นลูกค้าวีไอพีPriorityQueueก็จะช่วยให้คุณเสิร์ฟพวกเขาก่อนได้! สิ่งที่มีประโยชน์มากคุณไม่เห็นด้วยเหรอ? :) ประการที่สอง มันคงไม่ฟุ่มเฟือยที่จะพูดถึง หนังสือของ Robert Laforet เรื่อง“Data Structures and Algorithms in Java” อีกครั้ง ในขณะที่อ่านหนังสือ คุณจะไม่เพียงแต่เรียนรู้โครงสร้างข้อมูลมากมาย (รวมถึงสแต็กและคิว) แต่คุณยังจะได้นำไปใช้หลาย ๆ โครงสร้างด้วยตัวเองอีกด้วย! ตัวอย่างเช่น ลองจินตนาการว่า Java ไม่มีคลาส Stack หรือไม่ คุณจะทำอย่างไรถ้าคุณต้องการโครงสร้างข้อมูลดังกล่าวสำหรับโปรแกรมของคุณ? แน่นอนฉันจะต้องเขียนมันเอง เมื่ออ่านหนังสือของ Laforetคุณมักจะทำสิ่งนี้ ด้วยเหตุนี้ ความเข้าใจเกี่ยวกับโครงสร้างข้อมูลจึงกว้างกว่าการเรียนทฤษฎีเพียงอย่างเดียว :) วันนี้เราจบทฤษฎีแล้ว แต่ทฤษฎีที่ไม่มีการฝึกฝนก็ไร้ประโยชน์! ปัญหาต่างๆ ไม่สามารถแก้ไขได้ด้วยตัวเอง ดังนั้นตอนนี้เป็นเวลาที่จะจัดการกับมันแล้ว! :)