สรุป
สแตก(Stack)เป็นโครงสร้างข้อมูลแบบลิเนียร์ลิสต์(linear list) ที่มีคุณสมบัติว่า การเพิ่มหรือลบข้อมูลในสแตกจะทำได้ด้านเดียวเรียกว่า Top ของสแตก (Top Of Stack) ซึ่งคุณสมบัติที่สำคัญของสแตกคือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมา จากสแตกเป็นอันดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO (Last In First Out)
ส่วนประกอบของสแตก
การนำสแตกไปใช้งานนั้นไม่ว่าจะเป็นโครงสร้างสแตกแบบแถวลำดับ (array) หรือ แบบลิงค์ลิสต์
(link list) เราจะมีตัวแปรตัวหนึ่งที่ใช้เป็นตัวชี้สแตก (stack pointer ) เพื่อเป็นตัวชี้ข้อมูลที่อยู่บนสุดของสแตก ซึ่งจะทำให้สามารถจัดการข้อมูล ที่จะเก็บในสแตกได้ง่าย ดังนั้นโครงสร้างข้อมูลแบบสแตกจะแบ่งออกเป็น 2 ส่วนที่สำคัญ คือ
1. ตัวชี้สแตก ( Stack Pointer ) ซึ่งมีหน้าที่ชี้ไปยังข้อมูลที่อยู่บนสุดของ สแตก ( Top stack )
2. สมาชิกของสแตก ( Stack Element ) เป็นข้อมูลที่จะเก็บลงไปในสแตก ซึ่งจะต้องเป็นข้อมูลชนิดเดียวกัน เช่น ข้อมูลชนิดจำนวนเต็ม เป็นต้น
การทำงานของสแตก
โครงสร้างข้อมูลของสแตกจะใช้กันในเรื่องของการทำอินเตอร์รัพต์หรือการเรียกใช้โปรแกรมย่อย เนื่องจากการทำงานเช่นนี้ ต้องมีการเก็บตำแหน่งการทำงานเดิมเอาไว้ก่อนที่จะกระโดดไปทำงานโปรแกรมย่อยอื่น และหากต้องการกลับมาทำงานในโปรแกรมย่อยเดิมได้อย่างเป็นลำดับ เพราะ สแตกมีการใช้แสดงลำดับการประมวลผลของข้อมูล เมื่อต้องการข้ามขั้นตอน บางขั้นตอนไปกระทำขั้นตอนอื่น ให้จบก่อน แล้วจึงกลับมาทำซ้ำขั้นตอนเดิม
ตัวอย่าง
1. สมมติเมื่อเรากำลังประมวลผลข้อมูล A อยู่ เราต้องการข้ามไปประมวลผลข้อมูล B ให้เสร็จก่อน แล้วนำ ข้อมูลที่ได้มาใช้งานกับข้อมูล A เราจะต้องเก็บข้อมูล A ลงในสแตกก่อน (push A) จากนั้นจึงข้ามไปทำ การประมวลผลข้อมูล B
2. ในขณะที่ประมวลผลข้อมูล B อยู่เราต้องข้ามไปทำข้อมูล C เพื่อนำผลที่ได้มาทำงานกับข้อมูล B เราก็จะต้อง ทำการเก็บ B ลงในสแตก (push B) แล้วจึงจะข้ามไปทำข้อมูล C
3. เมื่อทำข้อมูล C เสร็จ เราก็จะดึงข้อมูล B ออกจากสแตก (pop B) เพื่อทำการประมวลผล
4. เมื่อเราประมวลผลข้อมูล B เสร็จ เราก็จะดึงข้อมูล A ออกจากสแตก (pop A) เพื่อทำการประมวลผล เป็นอันสิ้นสุดการประมวลผล
ตัวอย่าง การทำงานแบบโครงสร้างข้อมูลแบบสแตกที่สามารถเห็นได้ในชีวิตประจำวันทั่วไปได้แก่ การวางจานซ้อนกันต้องวางจานลงบนกล่องเก็บจานจากล่างสุดที่ละใบ และสามารถใส่ได้จนเต็มกล่อง และเมื่อมีการวางจานจนเต็มกล่องแล้วจะไม่สามารถวางจานซ้อนได้อีกเพราะกล่องมีสภาพเต็ม แต่เมื่อเราจะหยิบจานไปใช้ เราต้องหยิบใบบนสุด ซึ่งเป็นจานที่ถูกวางเก็บเป็นอันดับสุดท้ายออกได้เป็นใบแรก และสามารถหยิบออกที่ละใบจากบนสุดเสมอ ส่วนจานที่ถูกวางเก็บเป็นใบแรก จะนำไปใช้ได้ก็ต่อเมื่อนำจานที่วางทับมันอยู่ออกไปใช้เสียก่อน และจะหยิบออกไปใช้เป็นใบสุดท้าย
ไม่มีความคิดเห็น:
แสดงความคิดเห็น