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

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
- นี่คือคิวสองทาง ขยายฟังก์ชันการทำงานของคิวปกติโดยอนุญาตให้คุณเพิ่มองค์ประกอบที่ปลายทั้งสองข้าง (จุดเริ่มต้นและจุดสิ้นสุดของคิว) และรับองค์ประกอบจากปลายทั้งสองด้านของคิว 
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คุณมักจะทำสิ่งนี้ ด้วยเหตุนี้ ความเข้าใจเกี่ยวกับโครงสร้างข้อมูลจึงกว้างกว่าการเรียนทฤษฎีเพียงอย่างเดียว :) วันนี้เราจบทฤษฎีแล้ว แต่ทฤษฎีที่ไม่มีการฝึกฝนก็ไร้ประโยชน์! ปัญหาต่างๆ ไม่สามารถแก้ไขได้ด้วยตัวเอง ดังนั้นตอนนี้เป็นเวลาที่จะจัดการกับมันแล้ว! :)
GO TO FULL VERSION