โครงสร้างข้อมูล: สแตกและคิว

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

สแต็คใน Java

สแต็กเป็นโครงสร้างข้อมูลที่รู้จักกันดี มันง่ายมาก มีไม่กี่รายการในชีวิตประจำวันของเราที่ "ใช้งาน" เป็นปึก ลองนึกภาพสถานการณ์ง่ายๆ นี้: คุณกำลังพักอยู่ที่โรงแรม และในระหว่างวัน คุณได้รับจดหมายธุรกิจบางฉบับ ขณะนั้นคุณไม่ได้อยู่ในห้อง พนักงานโรงแรมจึงวางจดหมายรับไว้บนโต๊ะทำงานของคุณ อย่างแรก เขาวางจดหมายฉบับแรกไว้บนโต๊ะ แล้วจดหมายฉบับที่สองก็มาถึง เขาวางไว้บนจดหมายฉบับแรก เขาวางตัวอักษรตัวที่สามไว้บนตัวที่สอง และตัวที่สี่ไว้บนตัวที่สาม และตอนนี้ ตอบคำถามง่ายๆ: คุณจะอ่านจดหมายฉบับใดก่อนเมื่อคุณกลับมาที่ห้องและเห็นกองบนโต๊ะ ถูกต้อง คุณจะอ่านด้านบนสุดจดหมาย. นั่นคืออันที่มาถึงล่าสุด นี่คือวิธีการทำงานของสแต็ค หลักการนี้เรียกว่า"เข้าก่อนออกก่อน" (LIFO ) สแต็คเหมาะสำหรับอะไร? สมมติว่าคุณกำลังสร้างเกมไพ่ใน 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 {

   // 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.
}

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

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

ภายในเมธอดของเรา เราเรียกเมธอดของคลาส Stack ดังต่อไปนี้:

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

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

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

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

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

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

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

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

คิวใน Java

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

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

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

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

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

All implemented interfaces:

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

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

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

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