สแตกเป็นโครงสร้างข้อมูลชนิดหนึ่งซึ่งมีการจัดการข้อมูลแบบ LIFO ( Last In First Out ) คือ ลำดับของข้อมูลที่ถูกนำมาเก็บก่อนจะถูกนำไปใช้ทีหลัง เหมือนกับวาง จานซ้อนกัน เวลาเราจะหยิบจานไปใช้ เราต้องหยิบใบบนสุดก่อน ซึ่งเป็นจานที่ถูกวางเก็บเป็นอันดับ สุดท้าย ส่วนจานที่ถูกวางเก็บเป็นใบแรกจะนำไปใช้ได้ก็ต่อเมื่อนำจานที่วางทับมันอยู่ออกไปใช้เสียก่อน
การทำงานของสแตกจะประกอบด้วย
กระบวนการ 3 กระบวนการที่สำคัญ คือ
1. การนำข้อมูลเข้าสู่สแตก ( Insertion ) คือการนำข้อมูลเข้าไปเก็บไว้ในสแตก ซึ่งการกระทำเช่นนี้ เราเรียกว่า PUSH โดยก่อนที่จะนำข้อมูลเก็บลงในสแตกจะต้องมีการตรวจสอบพื้นที่ว่างในสแตกก่อน ว่ามีที่เหลือให้เก็บหรือไม่
2. การนำข้อมูลออกจากสแตก ( Deletion ) คือการนำข้อมูลที่อยู่บนสุดออกจากสแตก โดยการกระทำ เช่นนี้เราเรียกว่า POP โดยก่อนที่จะนำข้อมูลออกจากสแตก จะต้องมีการตรวจสอบว่าในสแตกมีข้อมูลเก็บ อยู่หรือไม่
3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้น
ส่วนประกอบของสแตก
การนำสแตกไปใช้งานนั้น เราจะใช้ในรูปแบบของพอยน์เตอร์ ซึ่งจะทำให้สามารถจัดการข้อมูล ที่จะเก็บในสแตกได้ง่าย โครงสร้างข้อมูลแบบสแตกจะแบ่งออกเป็น 2 ส่วน คือ
1. ตัวชี้สแตก ( Stack Pointer ) หรือ SP ซึ่งมีหน้าที่ชี้ไปยังข้อมูลที่อยู่บนสุดของสแตก ( Top stack ) หรือชี้ไปยังช่องว่างข้อมูลในสแตกที่อยู่บนข้อมูลที่บนสุด
2. สมาชิกของสแตก ( Stack Element ) เป็นข้อมูลที่จะเก็บลงไปในสแตก ซึ่งจะต้องเป็นข้อมูลชนิดเดียวกัน เช่น ข้อมูลชนิดจำนวนเต็ม
นอกจากนี้ยังต้องมีตัวกำหนดค่าสูงสุดของสแตก ( Max Stack ) ซึ่งจะเป็นตัวบอกว่าสแตกนี้สามารถเก็บ จำนวนข้อมูลได้มากที่สุดเท่าไร
เราจะเปรียบเทียบส่วนประกอบของสแตกได้ดังนี้ คือ สแตกเป็นกระป๋องเก็บลูกเทนนิส ส่วน Stack Element คือ ลูกเทนนิส ส่วนตัวชี้สแตกเป็นตัวบอกว่าขณะนี้มีลูกเทนนิสอยู่ในกระป๋องกี่ลูก ส่วน Max Stack เป็นตัวบอกว่า กระป๋องนี้เก็บลูกเทนนิสได้มากที่สุดเท่าไร
การดำเนินการเกี่ยวกับสแตก
การดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack
จัดสรรหน่วยความจำให้แก่ Head Nodeและส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
2. Push Stack
การเพิ่มข้อมูลลงไปในสแตก
3. Pop Stack
การนำข้อมูลบนสุดออกจากสแตก
4. Stack Top
เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก โดยไม่มีการลบข้อมูลออกจากสแตก
5.Empty Stack
เป็นการตรวจสอบการว่างของสแตก เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลออกจากสแตกที่เรียกว่า Stack Underflow
6. Full Stack
เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
7. Stack Count
เป็นการนับจำนวนสมาชิกในสแตก
8. Destroy Stack
เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
การทำงานของสแตก
สแตกมีการใช้แสดงลำดับการประมวลผลของข้อมูล เมื่อต้องการข้ามขั้นตอน บางขั้นตอนไปกระทำขั้นตอนอื่น ให้จบก่อน แล้วจึงกลับมาทำซ้ำขั้นตอนเดิม ดังตัวอย่าง
สมมติเมื่อเรากำลังประมวลผลข้อมูล A อยู่ เราต้องการข้ามไปประมวลผลข้อมูล B ให้เสร็จก่อน แล้วนำ ข้อมูลที่ได้มาใช้งานกับข้อมูล A เราจะต้องเก็บข้อมูล A ลงในสแตกก่อน (Push A) จากนั้นจึงข้ามไปทำ การประมวลผลข้อมูล B
ในขณะที่ประมวลผลข้อมูล B อยู่เราต้องข้ามไปทำข้อมูล C เพื่อนำผลที่ได้มาทำงานกับข้อมูล B เราก็จะต้อง ทำการเก็บ B ลงในสแตก (Push B) แล้วจึงจะข้ามไปทำข้อมูล C
มื่อทำข้อมูล C เสร็จเราก็จะดึงข้อมูล B ออกจากสแตก (Pop B) เพื่อทำการประมวลผล
เมื่อเราประมวลผลข้อมูล B เสร็จ เราก็จะดึงข้อมูล A ออกจากสแตก (Pop A) เพื่อทำการประมวลผล เป็นอันสิ้นสุดการประมวลผล
ไม่มีความคิดเห็น:
แสดงความคิดเห็น