- สแตกเป็นลิเนียร์ลิสต์ที่มีคุณสมบัติที่ว่าเมื่อทำการเพิ่มข้อมูลหรือลบข้อมูลในสแตกจะกระทำทีปลายข้างเดียวกัน ปลายข้างนั้นเรียกว่า top ของสแตก(Top Of Stack) จึงเรียกว่า เป็นโครงสร้างแบบกองซ้อน
- มีคุณสมบัติเฉพาะที่เรียกว่า ไลโฟลิสต์(LIFO List) คือสมาชิกข้อมูลที่เข้าไปในลิสต์ทีหลังจะได้ออกจากลิสต์ก่อน(Last In First Out)
- การเพิ่มข้อมูลเข้าสแตกจะเรียกว่า pushing
- การนำข้อมูลจากสแตกเรียกว่า poping
- การเพิ่มหรือลบข้อมูลในสแตกทำที่ top ของสแตก
- Top ของสแตกเป็นตัวชี้สมาชิกตัวท้ายสุดของสแตก
- การสร้างสแตกผู้สร้างต้องดำเนินการสองสิ่งใหญ่ ๆ คือ
เลือกการแทนข้อมูลของสแตก
สร้างการดำเนินงานโดยใช้การแทนที่ข้อมูลที่เลือกแล้ว
- การแทนข้อมูลของสแต็ก สามารถทำได้ 2 วิธี คือ
การแทนข้อมูลของสแต็กแบบอะเรย์
การแทนข้อมูลของสแต็กแบบลิงค์ลิสต์
- สิ่งที่ต้องเพิ่มเข้าไปเพื่อให้โครงสร้างข้อมูลแบบลิสต์กลายเป็นโครงสร้างข้อมูลแบบสแตก ก็คือ ตัวชี้ตำแหน่ง สำหรับข้อมูลที่อยู่บนสุดของโครง สร้าง ซึ่งค่าที่เก็บอยู่ที่ตัวชี้ตำแหน่ง ก็คือ ตำแหน่งของข้อมูลที่อยู่บนสุดของโครงสร้างข้อมูล
อาร์เรย์
ลิงค์ลิสต์
การดำเนินการพื้นฐานกับสแตก
การทดสอบว่าสแตกว่างหรือไม่ (empty)
การทำงานเพื่อตรวจสอบว่ามีข้อมูลอยู่ในสแตกหรือไม่ ทำได้โดยการตรวจสอบดูว่าตำแหน่งของ Top ของสแตกอยู่ ณ ตำแหน่งเริ่มต้นหรือไม่ (ตำแหน่ง 0 ตรงนี้ดูไห้ดีว่า top เป็น 0 หรือ -1)
Algorithm empty (s)
Pre s is a stack
Post boolean returned for showing status of stack
Return boolean returned
if Top = 0 then
set empty to True
else set empty to False
endif
return empty
End empty
การนำสมาชิกลงสแตก (push)
- การเพิ่มข้อมูลเข้าสแตก หมายถึง การเพิ่มข้อมูลเข้าในสแตก โดยให้ทับบนข้อมูล สุดท้ายในสแตก
- จะสามารถเพิ่มเข้าได้เรื่อย ๆ จนกว่าจะเต็มสแตก
- ความหมายของคำว่า สแตกเต็ม คือ top ของสแตกชี้ที่เนื้อที่สุดท้ายของสแตกแล้ว เช่น ถ้า สแตกนั้นจองเนื้อที่ไว้ N เนื้อที่ โดยที่สามารถบรรจุสมาชิกในสแตกได้ N ตัว เมื่อสแตกว่างค่า top เป็นศูนย์ เมื่อสแตกเต็มค่า top เป็น N ดังนั้นเมื่อ top ชี้ที่ N ก็ไม่สามารถ Push ข้อมูลลงสแตกได้อีกหรือ เกิด errorที่เรียกว่า “Stack Overflow”
ขั้นตอนการเพิ่มข้อมูลลงในสแตก
- ตรวจสอบว่าสแตกเต็มหรือไม่ โดยดูว่าในขณะนั้น top ของสแตกอยู่ที่ตำแหน่งสูงสุดหรือไม่
- ถ้ายังไม่เกินขนาดของสแตก ให้เพิ่มค่าของ top ไปยังตำแหน่งใหม่
- จากนั้นเพิ่มข้อมูลไว้ที่ตำแหน่ง top ของสแตก
Algorithm push( S, data)
Insert one item into the stack
Pre S is a stack passed by reference
data contain data to be pushed into stack
Post data have been pushed in stack or error printed
Return -
If top = upperbound then
print “Stack Full”
else
set top to top +1
set S[top] to data
endif
End push
การดึงข้อมูลออกจากสแตก (Poping stack)
- การดึงข้อมูลออกจากสแตก หมายถึงการนำข้อมูลที่อยู่บนสุดในสแตกหรือข้อมูลในตำแหน่งที่ top ออกจากสแตก
- จะสามารถ pop สแตกได้เรื่อย ๆ จนกว่าสแตกจะว่าง
- ไม่สามารถ pop ค่าออกจากสแตกที่ว่างเปล่าได้ ไม่เช่นนั้นจะเกิด error ที่เรียกว่า “Stack underflow”
ขั้นตอนการดึงข้อมูลออกจากสแตก
- ตรวจสอบดูก่อนว่าสแตกว่างหรือไม่ โดยเรียกใช้ฟังก์ชัน empty เพื่อป้องกัน ปัญหา underflow
- ถ้าสแตกว่างก็จะตอบกลับมาเป็น False นั่นคือ ดึงข้อมูลไม่ได้
- ถ้าภายในสแตกมีข้อมูลอยู่ ให้ดึงข้อมูลตัวที่อยู่ตำแหน่ง top ของสแตกออกมา
- ลดค่าของ top เนื่องจากเราต้องย้ายตำแหน่ง top ของสแตกลงไป 1 ค่า หลังจากที่มีการดึงข้อมูลออกจากสแตก
Algorithm POP(s)
This algorithm pops the items on the top of the stack and return to the user
Pre s is a stack
Post the item is poped or error is printed
Return dataout contains poped item is returned
if top = 0 then
print “Stack empty”
else
set dataout to S[top]
set top to top –1
endif
return dataout
End POP
ลิงค์สแตก
- คือ โครงสร้างข้อมูลสแตกที่แทนที่ข้อมูลแบบไดนามิกส์ที่ใช้ลิงค์ โดยมี พอยน์เตอร์ top ชี้ที่ top ของสแตก
- การ push คือ การเพิ่มข้อมูลที่ต้นลิสต์
- การ pop คือ การลบข้อมูลที่ต้นลิสต์
- ควรใช้โครงสร้างลิงค์สแตกเมื่อต้องการใช้สแตกเก็บข้อมูลโดยไม่ทราบแน่นอนว่าข้อมูลมีมากเพียงใด แต่ถ้าทราบแน่นอนว่าข้อมูลที่เก็บในสแตกมีน้อย ก็ควรแทนที่ข้อมูลแบบ static เพราะลิงค์สแตกก็ต้องสิ้นเปลืองเนื้อที่ในส่วนของพอยน์เตอร์
struct s {
item type item;
struct s *link;
};
struct s *top;
ไม่มีความคิดเห็น:
แสดงความคิดเห็น