เรื่อง สแตก (Stack)
สแตก (Stack) เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ ลิสต์ ที่มีคุณสมบัติที่ว่า การ เพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ ปลายข้างเดียวกัน ซึ่งเรียกว่า Top ของสแตก (TopOf Stack) และ ลักษณะที่สำคัญของสแตกคือ ข้อมูล ที่ใส่หลังสุดจะถูกนำออกมา จากส แตกเป็นลำดับแรกสุด เรียกคุณสมบัตินี้ว่าLIFO (Last In First Out)
การดำเนินงานพื้นฐานของสแตก
การทำงานต่าง ๆ ของสแตกจะกระทำที่ปลายข้างหนึ่งของ สแตกเท่านั้น ดังนั้นจะต้องมีตัวชี้ ตำแหน่งข้อมูลบนสุดของ สแตกด้วย การทำงานของสแตกจะประกอบด้วยกระบวนการ 3 กระบวนการที่สำคัญ คือ
1.Push คือ การนำข้อมูลใส่ลงไปในสแตก เช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้ push (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก s
ในการเพิ่มข้อมูลลงในสแตก จะต้องทำการ ตรวจสอบว่า สแตก เต็มหรือไม่ ถ้าไม่เต็มก็ สามารถเพิ่มข้อมูลลงไปใน สแตกได้ แล้วปรับ ตัวชี้ตำแหน่งให้ไปชี้ที่ตำแหน่งข้อมูลใหม่ ถ้าส แตกเต็ม (Stack Overflow) ก็จะไม่สามารถ เพิ่มข้อมูล เข้าไปในสแตกได้อีก
ตัวอย่าง
2. Pop คือ การนำข้อมูลออกจากส่วนบนสุด ของสแตก เช่น ต้องการนำข้อมูลออกจากสแตก s ไปไว้ที่ตัวแปร i จะได้ i = pop (s) การนำข้อมูลออกจากสแตก ถ้าสแตก มีสมาชิกเพียง 1ตัว แล้วนำสมาชิกออกจากสแตก จะเกิด สภาวะสแตก ว่าง (Stack Empty) คือ ไม่มีสมาชิกอยู่ใน สแตกเลย ตัวอย่าง
3. Stack Top เป็นการคัดลอกข้อมูลที่ อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้น ออกจากสแตก ตัวอย่าง
การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของสแตกแบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์จะประกอบไปด้วย2 ส่วน คือ
1. Head Node จะประกอบไปด้วย 2ส่วนคือ top pointer และจำนวนสมาชิกในสแตก
2. Data Node จะประกอบไปด้วยข้อมูล (Data) และ พอยเตอร์ ที่ชี้ไปยังข้อมูล
สแตก (Stack) เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ ลิสต์ ที่มีคุณสมบัติที่ว่า การ เพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ ปลายข้างเดียวกัน ซึ่งเรียกว่า Top ของสแตก (TopOf Stack) และ ลักษณะที่สำคัญของสแตกคือ ข้อมูล ที่ใส่หลังสุดจะถูกนำออกมา จากส แตกเป็นลำดับแรกสุด เรียกคุณสมบัตินี้ว่าLIFO (Last In First Out)
การดำเนินงานพื้นฐานของสแตก
การทำงานต่าง ๆ ของสแตกจะกระทำที่ปลายข้างหนึ่งของ สแตกเท่านั้น ดังนั้นจะต้องมีตัวชี้ ตำแหน่งข้อมูลบนสุดของ สแตกด้วย การทำงานของสแตกจะประกอบด้วยกระบวนการ 3 กระบวนการที่สำคัญ คือ
1.Push คือ การนำข้อมูลใส่ลงไปในสแตก เช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้ push (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก s
ในการเพิ่มข้อมูลลงในสแตก จะต้องทำการ ตรวจสอบว่า สแตก เต็มหรือไม่ ถ้าไม่เต็มก็ สามารถเพิ่มข้อมูลลงไปใน สแตกได้ แล้วปรับ ตัวชี้ตำแหน่งให้ไปชี้ที่ตำแหน่งข้อมูลใหม่ ถ้าส แตกเต็ม (Stack Overflow) ก็จะไม่สามารถ เพิ่มข้อมูล เข้าไปในสแตกได้อีก
ตัวอย่าง
2. Pop คือ การนำข้อมูลออกจากส่วนบนสุด ของสแตก เช่น ต้องการนำข้อมูลออกจากสแตก s ไปไว้ที่ตัวแปร i จะได้ i = pop (s) การนำข้อมูลออกจากสแตก ถ้าสแตก มีสมาชิกเพียง 1ตัว แล้วนำสมาชิกออกจากสแตก จะเกิด สภาวะสแตก ว่าง (Stack Empty) คือ ไม่มีสมาชิกอยู่ใน สแตกเลย ตัวอย่าง
3. Stack Top เป็นการคัดลอกข้อมูลที่ อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้น ออกจากสแตก ตัวอย่าง
การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของสแตกแบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์จะประกอบไปด้วย2 ส่วน คือ
1. Head Node จะประกอบไปด้วย 2ส่วนคือ top pointer และจำนวนสมาชิกในสแตก
2. Data Node จะประกอบไปด้วยข้อมูล (Data) และ พอยเตอร์ ที่ชี้ไปยังข้อมูล
ไม่มีความคิดเห็น:
แสดงความคิดเห็น