Abstract Data Types — stack, queue, linked list
แนะนำใหม่| English | ความหมาย |
|---|---|
| queue/kjuː/ | คิว |
| push/pʊʃ/ | ดันเข้าส택 |
| abstract data type/ˈæbstrækt ˈdeɪtə taɪp/ | ชนิดข้อมูลนามธรรม |
| stack/stæk/ | สตैก |
| linked list/lɪŋkt lɪst/ | ลิงค์ลิสต์ |
| LIFO/ˈlaɪfəʊ/ | 后进先出 (LIFO) |
| pop/pɒp/ | ป๊อป |
| pointer/ˈpɔɪntə/ | พอยเตอร์ |
| FIFO/ˈfaɪfəʊ/ | 先进先出 (FIFO) |
| enqueue/enˈkjuː/ | เควนู |
| dequeue/diːˈkjuː/ | ดีคิว |
| node/nəʊd/ | โหนด |
| traverse/trəˈvɜːs/ | ทราเวอร์ส |
ปุ่มย้อนกลับและคิวงานเครื่องพิมพ์
- หน้าเว็บที่คุณเข้าชมจะถูกส่งเข้ากอง; ปุ่มย้อนกลับจะดึงหน้าบนสุดออก หน้าที่คุณออกจากล่าสุดจะเป็นหน้าที่คุณกลับไปเป็นอันดับแรก
- ตามทางเดิน เครื่องพิมพ์จะดำเนินการตามลำดับที่รับเข้ามา เอกสารที่ส่งไปก่อนจะออกมาก่อน แม้เอกสารต่อจากนั้นจะมีขนาดเล็กแค่ไหนก็ตาม
- โครงสร้างสองชนิด กฎตรงข้ามกัน และคุณต้องใช้ทั้งสองก่อนพักNeither ไม่ระบุว่าจัดเก็บอย่างไร; แต่ละชนิดระบุเพียงว่าการทำงานของมันทำอะไร
- นั่นคือ โครงสร้างข้อมูลนามธรรม บทเรียนนี้คือสามสิ่งที่หลักสูตรตั้งชื่อ, การทำงานของแต่ละอย่าง,以及如何证明适合某个情境。
โครงสร้างข้อมูลนามธรรมคืออะไร
- โครงสร้างข้อมูลนามธรรม (ADT) คือชุดของข้อมูลพร้อมกับการดำเนินการชุดหนึ่งบนข้อมูลนั้น ประโยคเดียวนี้คือคำนิยามสำหรับหนึ่งคะแนน
- กำหนดโดย สิ่ง ที่การดำเนินการทำ ไม่ใช่วิธีการจัดเก็บข้อมูล การนำไปใช้ถูกซ่อนไว้ดังนั้นจึงเปลี่ยนแปลงได้โดยไม่กระทบโค้ดที่ใช้มัน
- Stack, Queue, Linked list, Binary tree และ Array ล้วนเป็น ADT
ประเภทข้อมูลเชิง 추้อยู (ADT) ถูกกำหนดโดย:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ADT ระบุการดำเนินการ (อินเทอร์เฟซ); ส่วนการนำไปใช้จริงถูกซ่อนและสามารถเปลี่ยนแปลงได้ตามต้องการ
Stack
- Stack คือรายการที่เพิ่มและลบรายการจากปลายเดียวกัน คือ ด้านบน ดังนั้นรายการที่เพิ่มสุดท้ายจะเป็นรายการที่ถูกลบก่อน: LIFO
- การดำเนินการ: push เพิ่มที่ด้านบน, pop ลบที่ด้านบน, peek ดูที่ด้านบน, และทดสอบความเป็นว่างและเต็ม
- การใช้: ประวัติการ undo, ปุ่มย้อนกลับ, ที่อยู่กลับของการเรียกฟังก์ชัน, การตรวจสอบวงเล็บ, การย้อนกลับ
*ทุกอย่างเกิดขึ้นที่ด้านบน
สแต็กทำงานตามลำดับใด?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
สแต็กเป็น LIFO: รายการที่ถูกpush เข้ามาล่าสุดจะเป็นรายการแรกที่pop ออกมา
ตัวอย่างวิธีทำ: ติดตาม stack
- Stack Holdings, จากด้านล่าง,
'P' 'N' 'Z' 'X' 'Y' 'W'; ชี้ไปที่บนอยู่ที่'W'. การดำเนินการPOP,POP,PUSH 'A',PUSH 'B',POPถูกดำเนินการ. Stack Holdingsอะไร, และชี้อยู่ที่ไหน? - การ pop ทั้งสองจะดึง
'W'แล้วตามด้วย'Y'การ push จะใส่'A'แล้วตามด้วย'B'ลงไปแทนที่ การ pop สุดท้ายจะดึง'B'ออก - สแตกเก็บ
'P' 'N' 'Z' 'X' 'A'ไว้ โดยมีพอยเตอร์อยู่ที่'A'รายการที่ยาวที่สุดในสแตกคือรายการที่อยู่ด้านล่างสุด'P'; สามารถทำ pop ได้อีก 5 ครั้ง และ做一次 sixth จะเกิดข้อผิดพลาด ดังนั้นการทดสอบ pop จึงต้องตรวจสอบว่าว่างหรือไม่ก่อนเสมอ
สแต็กมี P N Z X Y W (บนสุดคือ W) หลังจาก POP, POP, PUSH 'A', PUSH 'B', POP รายการใดจะอยู่บนสุด?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
W และ Y ถูกpop ออก, A แล้ว B ถูกpush เข้า, B ถูกpop ออก. บนสุดคือ A, อยู่เหนือ X
Queue
- Queue คือรายการที่เพิ่มรายการที่ ด้านหลัง และลบรายการที่ ด้านหน้า ดังนั้นรายการที่เพิ่มแรกจะเป็นรายการที่ถูกลบก่อน: FIFO
- การดำเนินการ: enqueue เพิ่มที่ด้านหลัง, dequeue ลบที่ด้านหน้า, และทดสอบความเป็นว่างและเต็ม
- การใช้: Print spooling, Keyboard buffers, Scheduling, ลูกค้าในร้าน, Breadth-first search
*เชื่อมต่อกันที่ด้านหลัง, ออกจากด้านหน้า
Stacks, queues & linked lists
LIFO vs FIFO
สแต็ก (stack) เป็นโครงสร้างแบบเข้าหลังออกหน้า; การ push และ pop เกิดขึ้นที่ปลายเดียวกัน (ด้านบน)
คิว (queue) เป็นแบบเข้าหน้าออกหน้า: รายการจะถูกนำออกจาก ______ และเพิ่มที่ท้าย
Difficulty 1/5 · 100 coins + a small bonus on first completion today
FIFO: dequeue จากด้านหน้า, enqueue ที่ด้านหลัง — เหมือนคนต่อแถว
ตัวอย่างวิธีทำ: อธิบายการเพิ่มและลบออกจาก Queue
- การเพิ่ม: ตรวจสอบว่า Queue ไม่เต็ม; จัดเก็บรายการที่ตำแหน่งที่ชี้ที่ด้านหลังกำหนด; เคลื่อนชี้ที่ด้านหลัง (และเพิ่มหนึ่งกับนับ)
- การลบ: ตรวจสอบว่า Queue ไม่ว่าง; อ่านรายการที่ชี้ที่ด้านหน้ากำหนด; เคลื่อนชี้ที่ด้านหน้า (และลบหนึ่งจากนับ)
- บอกล().' convention ที่คุณใช้: หากชี้ที่ด้านหลังระบุพื้นที่ว่างถัดไป ให้จัดเก็บก่อนแล้วค่อยเคลื่อน; หากระบุรายการสุดท้าย ให้เคลื่อนก่อนแล้วค่อยจัดเก็บ. ทั้งสองให้คะแนน ถ้าคุณสม่ำเสมอ
เรียงขั้นตอนการเพิ่มรายการลงในคิว (พอยเตอร์ Rear ชี้ไปที่ช่องว่างถัดไป)
Difficulty 3/5 · 200 coins + a small bonus on first completion today
การตรวจสอบทำก่อน; แล้วเก็บ, แล้วเลื่อน, ภายใต้กฎนี้ ให้ระบุว่าคุณใช้กฎ哪种
Linked List
- Linked List คือรายการที่แต่ละ Node Holdings ข้อมูลหนึ่งและ Chиe ไปยัง Node ถัด, พร้อม Chиeเริ่มต้นไปยัง Node แรก. Chиeของ Node สุดท้ายเป็น Sentinel เช่น
NULL. - การดำเนินการ: แทรก ลบ ค้นหา และ ** traversal** โดยติดตามตัวชี้จากหัวไปยังทุกโหนดตามลำดับ
- ข้อดีเหนือ-array: การแทรกหรือลบมีต้นทุนต่ำ เพียงแค่ปรับสายตัวชี้ และลิสต์จะขยายตามต้องการ ข้อเสีย: ไม่สามารถเข้าถึงแบบสุ่ม; การเข้าถึงโหนดที่สิบต้องติดตามตัวชี้เก้าตัว
ค่าและลูกศร ซ้ำกัน
ลิงก์ลิสต์: โหนดเชื่อมต่อกันด้วยพอยเตอร์
แต่ละโหนดเก็บค่าและพอยเตอร์ไปยังโหนดถัดไป การเพิ่มหรือลบข้อมูลเพียงเชื่อมต่อพอยเตอร์ใหม่ — ไม่มีรายการเลื่อนตำแหน่งเหมือนในอาร์เรย์
แต่ละโหนดของลิงก์ลิสต์มี:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
โหนดเก็บค่าของตัวเองพร้อมพอยเตอร์ (อ้างอิง) ไปยังโหนดถัดไป; Head แสดงจุดเริ่มต้น, NULL แสดงจุดสิ้นสุด
ลิงก์ลิสต์ทำให้เพิ่ม/ลบข้อมูลง่าย (แค่ปรับสายพอยเตอร์) แต่การเข้าถึงแบบสุ่มช้า (ต้องติดตามพอยเตอร์จาก Head)
Difficulty 1/5 · 100 coins + a small bonus on first completion today
นี่คือการแลกเปลี่ยนระหว่างอาร์เรย์กับลิสต์: อาร์เรย์ให้การเข้าถึงด้วยดัชนี O(1); ลิสต์ให้การเพิ่ม/ลบข้อมูลที่มีประสิทธิภาพ
ตัวอย่างทำข้อ: เพิ่มโหนดตามลำดับ
- อธิบายวิธีการแทรกค่าใหม่ลงในลิสต์เชิงเชื่อมโยงที่จัดเรียงตามลำดับเพิ่มขึ้น [4]
- Traverse ลิสต์จากหัว ตามตัวชี้ จนกว่าจะพบโหนดก่อนตำแหน่งนั้น: โหนดสุดท้ายที่มีค่าน้อยกว่าค่าใหม่
- นำโหนดว่างมาเก็บค่าใหม่ไว้ therein ตั้งค่า ตัวชี้ของโหนดใหม่ ไปยังที่อยู่ที่โหนดก่อนหน้าชี้อยู่ปัจจุบัน
- จากนั้นตั้งค่า ตัวชี้ของโหนดก่อนหน้า ไปยังโหนดใหม่ หากค่าใหม่ควรอยู่ที่ด้านหน้า ตัวชี้หัวคือสิ่งที่เปลี่ยนแปลงแทน
เรียงขั้นตอนการใส่ค่าลงในลิงก์ลิสต์ที่เรียงลำดับแล้ว
Difficulty 3/5 · 200 coins + a small bonus on first completion today
หา, เติม, ชี้โหนดใหม่ไปข้างหน้า, แล้วปรับสายโหนดก่อนหน้า. การสลับสองขั้นตอนสุดท้ายจะทำให้ส่วนที่เหลือของลิสต์หายไปได้
การให้เหตุผลในการเลือก
- รายการต้องจัดการตามลำดับที่มา: งานพิมพ์, การกดคีย์, ลูกค้า: queue เพราะเป็น First In First Out
- รายการล่าสุดต้องจัดการก่อน: ยกเลิก, ย้อนกลับ, การเรียกซ้ำ: stack เพราะเป็น Last In First Out
- มีการแทรกหรือลบรายการบ่อยครั้งใน กลาง ของชุดข้อมูลที่เรียงลำดับ และขนาดไม่ทราบ: linked list เพราะเฉพาะตัวชี้ที่เปลี่ยนและไม่มีการเลื่อน
- ชื่อโครงสร้าง, บอกรูปแบบ, เชื่อมโยงรูปแบบเข้ากับสถานการณ์
จับคู่ ADT แต่ละชนิดกับกฎและการใช้งานทั่วไป
Difficulty 2/5 · 140 coins + a small bonus on first completion today
สแต็ก = เข้าหลังออกหน้า; คิว = เข้าหน้าออกหน้า; ลิงก์ลิสต์เชื่อมโหนดด้วยพอยเตอร์
งานพิมพ์ต้องพิมพ์ตามลำดับที่ส่งเข้ามา Which ADT, และทำไม?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ลำดับการมาถึงคือกฎ FIFO. สแต็กจะพิมพ์งานที่ใหม่ที่สุดก่อน
ADT เทียบกับการนำไปใช้
- ADT คือ พฤติกรรม: push และ pop, enqueue และ dequeue, insert และ traverse
- การนำไปใช้คือ การจัดเก็บ: ในรายวิชานี้คือ array连同 few ตัวแปรตัวชี้ (บทถัดไป)
- คำถามเกี่ยวกับ ADT ต้องการการดำเนินการและกฎ; คำถามเกี่ยวกับการนำไปใช้ต้องการ array, ตัวชี้ และการตรวจสอบ
คะแนนที่หลุดหายไป
- Push และ enqueue ตรวจสอบว่า เต็ม ก่อน; pop และ dequeue ตรวจสอบว่า ว่าง ก่อน เขียนการตรวจสอบลงในคำอธิบาย
- การแทรกใน linked list: ตั้งค่า โหนดใหม่ ตัวชี้ ก่อน เปลี่ยนตัวชี้ของโหนดก่อนหน้า มิฉะนั้นส่วนที่เหลือของลิสต์จะหายไป
- Stack เปลี่ยนที่ปลายหนึ่ง Queue เปลี่ยนทั้งสอง "ลบจากด้านบนของ queue" เป็นคำตอบของ stack
- ขยายคำย่อonce: LIFO, last in first out; FIFO, first in first out
คุณเข้าใจแล้ว
- ADT คือชุดข้อมูลพร้อมกับการดำเนินการ对它; พฤติกรรม ไม่ใช่การจัดเก็บ
- stack: เพิ่มและลบที่ด้านบน, LIFO, push และ pop · queue: เพิ่มที่ท้าย, ลบที่หน้า, FIFO, enqueue และ dequeue
- linked list: โหนดของค่า + ตัวชี้จากตัวชี้หัว; แทรกและลบราคาถูก, เข้าถึงแบบสุ่มช้า; traverse bằng cáchติดตามตัวชี้
- ให้เหตุผลด้วยกฎ: ลำดับการมาถึง → queue; ล่าสุดก่อน → stack; การแทรกในกลางบ่อยครั้ง → linked list