![…
1 2 9
9
10
0
8 …
8 2
0
…
8 2
0
6 …
1
2
3
Point
er
Stack[
100]
แสดงโครงสร้างข้อมูลสแตกด้วยอาร์เรย์ Stack[100]
การแทนโครงสร้างข้อมูลสแตกการแทนโครงสร้างข้อมูลสแตก
(Stack)(Stack)](https://image.slidesharecdn.com/random-130829123809-phpapp01/85/-15-320.jpg)
แสตก
- 2. 2 สแตก (Stack) คือ โครงสร้างข้อมูลชนิด หนึ่งที่มีการเก็บข้อมูลแบบเรียงลำาดับ การใส่ข้อมูล เข้าหรือนำาข้อมูลออกจากสแตกกระทำาที่บริเวณ เดียวกันซึ่งเรียกว่า ทอป (top) ของสแตกและ ลักษณะที่สำาคัญคือ ข้อมูลที่ใส่หลังสุด จะถูกนำาออกมาจากสแตกเป็น ลำาดับแรกสุด (last in, first out หรือ LIFO) การดำาเนินงานของสแตก ะกอบด้วยกระบวนงานหลัก 2 กระบวนงานคือ พุช (push) พอพ (pop)
- 3. 3 push คือ การนำาข้อมูลใส่ลงไปในส แตก s เมื่อต้องการใส่ข้อมูล i ในสแตกดังนั้น การดำาเนินงานของกระบวนงาน push(s,i) คือ ใส่ ข้อมูล i ลงไปที่ทอปของสแตก s pop คือ การนำาข้อมูลออกจากส่วนบน สุดของสแตก และนำาค่านี้ไปใส่ในตัวแปร i สามารถเขียนด้วยคำาสั่ง i = pop(s)
- 4. การดำาเนินการกับสแตก การเพิ่มข้อมูลลงสแตก เรียกว่า push เช่น push(A) หมายถึงนำา A ใส่ลงสแตก push(N) หมายถึงนำา N ใส่ลงสแตก A Ntop Top เป็นตัวชี้ตำาแหน่งของสมาชิกตัวบนสุดของสแตก
- 5. การดำาเนินการกับสแตก (ต่อ) การนำาข้อมูลออกจากสแตก เรียกว่า pop เช่น pop() หมายถึง นำาสมาชิกตัวบนสุดออก จากสแตก A Ntop Atop ก่อน pop() หลัง pop()
- 6. การ Implement สแตก Implement ด้วยอาร์เรย์ Implement ลิงค์ลิสต์ การ implement Stack ทำาได้ 2 วิธี คือ 1. Array Implementation 2. Linked List Implementation
- 7. การ Implement สแตกด้วยอาร์เรย์ ข้อจำากัดของอาร์เรย์ คือ จำานวนสมาชิก จำากัด ตามขนาดของอาร์เรย์ เช่น ถ้าใช้อาร์เรย์ขนาด 10 ช่อง แทน สแตก จำานวนสมาชิกสูงสุดของ สแตกจะถูกจำากัดแค่ 10 ตัว ไม่สามารถใส่ตัวที่ 11 , 12 ลงไปได้ ซึ่งจะส่งผลต่อ อัลกอริทึม push ในการเพิ่มข้อ มูลลงสแตก ส่วนการนำาข้อมูลออกจากสแตก ถ้าสแตกว่าง (อาร์เรย์ยังไม่มีข้อมูล) ก็จะไม่สามารถ pop ได้ เพราะไม่มีข้อมูลให้ pop
- 9. โครงสร้างข้อมูลสแตกโครงสร้างข้อมูลสแตก (Stack)(Stack) ในการใช้งานโครงสร้างข้อมูลที่เปิด ปลายเพียงด้านเดียว การดำาเนินการกับข้อมูล ในโครงสร้างสามารถกระทำาได้เพียงปลาย ข้างหนึ่งเท่านั้น ข้อมูลที่ถูกบรรจุอยู่ใน โครงสร้างดังกล่าว ตัวแรกไม่สามารถถูกดึง ข้อมูลออกจากโครงสร้างได้ถ้าข้อมูลตัวที่เข้า มาในลำาดับหลังยังไม่ถูกดึงออกไปก่อน โครงสร้างข้อมูลที่มีลักษณะดังกล่าวนี้ ไม่ สามารถใช้งานโครงสร้างอาร์เรย์ (Array) ทั่วไปได้ จึงมีการใช้โครงสร้างข้อมูลที่เรียก ว่า โครงสร้างข้อมูลสแตก (Stack) มาแทน
- 10. ลักษณะของโครงสร้างข้อมูลสแตกลักษณะของโครงสร้างข้อมูลสแตก (Stack)(Stack)โครงสร้างข้อมูลแบบสแตก (Stack) เป็นโครงสร้างข้อมูลแบบรายการเชิงเส้น (Linear List) ที่มีลักษณะที่สำาคัญคือ การนำา ข้อมูลเข้าสู่สแตก (Insertion : บางครั้งอาจ เรียกว่า Pushing) และการนำาข้อมูลออกจาก สแตก (Deletion บางครั้งเรียกว่า Popping) สามารถกระทำาได้เพียงปลายด้าน เดียวของโครงสร้างเท่านั้น โดยข้อมูลที่ เข้าไปเก็บทีหลังจะถูกนำาออกมาใช้งานก่อน จะเรียกลักษณะแบบนี้ว่า เข้าหลังออกก่อน (Last In First Out : LIFO)
- 13. การแทนโครงสร้างข้อมูลสแตกการแทนโครงสร้างข้อมูลสแตก (Stack)(Stack) โครงสร้างข้อมูลแบบสแตกสามารถ แทนได้ด้วยโครงสร้างข้อมูลอาร์เรย์ (Array) แต่กำาหนดวิธีการเข้าถึงข้อมูลในอาร์เรย์นั้น ตามกฏเกณฑ์ของสแตก คือ เข้าหลังออกก่อน (Last In First Out : LIFO) ดังนั้นการเข้า ถึงข้อมูลในโครงสร้างสแตกจะต้องอาศัย พอยน์เตอร์ (Pointer) ซึ่งทำาหน้าที่ชี้ ตำาแหน่งของข้อมูลตัวสุดท้ายของสแตก
- 15. … 1 2 9 9 10 0 8 … 8 2 0 … 8 2 0 6 … 1 2 3 Point er Stack[ 100] แสดงโครงสร้างข้อมูลสแตกด้วยอาร์เรย์ Stack[100] การแทนโครงสร้างข้อมูลสแตกการแทนโครงสร้างข้อมูลสแตก (Stack)(Stack)
- 16. การดำาเนินการกับโครงสร้างข้อมูลสการดำาเนินการกับโครงสร้างข้อมูลส แตกแตก (Stack)(Stack) มีอยู่ 3 กระบวนการ คือ 1. การสร้างสแตก 2. การเพิ่มข้อมูลเข้าสแตก (Insertion หรือ Pushing) 3. การลบข้อมูลในสแตก (Deletion หรือ Popping)
- 17. ค่าที่เกี่ยวข้องกับโครงสร้างข้อมูลสค่าที่เกี่ยวข้องกับโครงสร้างข้อมูลส แตกแตก 1. สแตกพอยน์เตอร์ (Stack Pinter : SP) เป็นตัวชี้ข้อมูลค่าที่อยู่บนสุดของสแตก (Top of Stack) 2. พุช (Push) เป็นการกระทำาเพื่อนำา ข้อมูลเข้าสู่สแตก เมื่อสแตกเต็มแล้ว หากมี การนำาข้อมูลเข้าสู่สแตกอีกจะเกิดข้อผิดพลาด ที่เรียกว่า โอเวอร์โฟลว์ (Over flow) ขึ้น 3. ป๊อบ (Pop) เป็นการกระทำาเพื่อนำา ข้อมูลที่อยู่บนสุดออกมาจากโครงสร้างสแตก เมื่อนำาข้อมูลค่าสุดท้ายออกจากสแตกแล้วจะ ทำาให้สแตกว่างเปล่า (Empty) ได้ หากมีการ
- 18. ลักษณะการทำางานของโครงสร้างข้อลักษณะการทำางานของโครงสร้างข้อ มูลสแตกมูลสแตก (Stack)(Stack) Q A Q A Q (Empty) Push box Q onto empty stack Push box A onto stack Pop box A from stack Pop box Q from stack Pushing and Popping a stack
- 19. R D M D M Push box R onto empty stack Push box D onto stack Push box M onto stack Pop box M from stack ลักษณะการทำางานของโครงสร้างข้อลักษณะการทำางานของโครงสร้างข้อ มูลสแตกมูลสแตก (Stack)(Stack) Pushing and Popping a stack (Continue)
- 20. Q S Push box Q onto stack Push box S onto stack ลักษณะการทำางานของโครงสร้างข้อลักษณะการทำางานของโครงสร้างข้อ มูลสแตกมูลสแตก (Stack)(Stack) Pushing and Popping a stack (Continue)
- 21. ลักษณะการทำางานของโครงสร้างข้อลักษณะการทำางานของโครงสร้างข้อ มูลสแตกมูลสแตก (Stack)(Stack) Stack frames for subprogram calls
- 23. คุณลักษณะของสแตก o การนำาข้อมูลเข้าและออกจากสแตกจะกระทำาที่ ปลายข้างเดียวเท่านั้น o การทำางานของสแตกจะมีลักษณะแบบ เข้าหลัง ออกก่อน (LIFO: Last In, First Out) o ตัวอย่างการทำางานแบบ LIFO เช่น การวางจาน ซ้อนกัน
- 24. ประโยชน์ของสแตก o เพื่อแปลงนิพจน์ทางคณิตศาสตร์ o การจัดลำาดับการทำางานแบบ recursive หรือการเรียกใช้ฟังก์ชัน o เป็นกลไกสำาคัญในการทำางานของ compiler เช่น การตรวจสอบ เครื่องหมาย { } ในภาษาซี หรือการ ตรวจสอบเครื่องหมายวงเล็บ