stack
stack
ลักษณะของ สแตก
•สแตก
เป็นโครงสร้างข้อมูลแบบเชิงเส้น
•โครงสร้างข้อมูลที่จัดเก็บเป็นแบบเรียงลำดับต่อเนื่องกันไป
•การเพิ่มหรือนำข้อมูลออกจากสแตกทำได้ที่จุดปลายของสแตกทางเดียว
•มาทีหลังแต่ออกก่อน
(Last In – First Out : LIFO)
- การสร้าง stack implemet สามารถแทนที่ข้อมูลสแตกได้ 2 วิธี คือ
.การสร้างสแตกด้วยอาร์เรย์ เป็นการจัดสรรเนื้อที่หน่วยความจำแบบ
Static ซึ่งต้องมีการกำหนด
ขนาดของสแตกเพื่อใช้งานล่วงหน้า
.การสร้างสแตกด้วยลิงค์ลิสต์ เป็นการจัดสรรเนื้อที่หน่วยความจำแบบ
Dynamic โดยจะจัดสรร
หน่วยความจำเมื่อมีการใช้งานจริงเท่านั้น
และยังสามารถเก็บข้อมูลต่างชนิดกันได้
1.การจัดการ สแตก
ในการทำงานของสแตก
ประกอบด้วย 2 กระบวนการ คือ การเพิ่มข้อมูลลงบนสแตก
(Push Stack)
และการดึงข้อมูลออกจากสแตก
(Pop Stack)
2.การทำงานของ stack operation
ประกอบด้วยฟังก์ชันพื้นฐาน ดังนี้
2.1 ClearStack เป็นการดำเนินการเพื่อลบข้อมูลออกจากสแตกให้หมด
- กรณีใช้โครงสร้างข้อมูลอาร์เรย์ ต้องสั่งให้ช่องบนสุดของสแตกเป็น 0
Stack.Top := 0;
- กรณีใช้โครงสร้างข้อมูลลิงค์ลิสต์ ต้องสั่งให้ตัวชี้สแตกไม่ชี้ไปที่ไหนเลย
2.2 EmptyStack เป็นการดำเนินการเพื่อตรวจสอบว่าสแตกนั้นมีข้อมูลหรือไม่
กรณีใช้โครงสร้างข้อมูลอาร์เรย์
ต้องสั่งให้ตรวจสอบว่าที่ Top
ของสแตกนั้นมีค่า
=
0 หรือไม่
EmptyStack := Stack.top := 0;
{ถ้าเป็นจริงจะส่งค่า True ออกมาให้โปรแกรมหลัก}
กรณีใช้โครงสร้างข้อมูลลิงค์ลิสต์
ให้ตรวจสอบว่าตัวชี้สแตกไม่ชี้ไปที่ไหน
EmptyStack := Stack.Null;
{ถ้าเป็นจริงคืนค่า True ถ้าไม่จริง คืนค่า False}
2.3 FullStack เป็นการดำเนินการเพื่อตรวจสอบว่าสแตกนั้นเต็มหรือไม่
ดำเนินการตรวจสอบเฉพาะข้อมูลอาร์เรย์
ต้องตรวจสอบว่า Top
ของสแตกนั้นเป็นค่าสูงสุดที่ขอไว้หรือไม่
FullStack := Stack.top := MaxStack;
2.4 Push เป็นการทำงานของสแตกในการนำข้อมูลเข้าสู่สแตก
โดยก่อนที่จะนำข้อมูลเข้านั้นต้องจัด
การให้ตัวชี้สแตกให้ไปชี้ในตำแหน่งต่อไปของสแตกก่อน
ซึ่งต้องเป็นช่องหรือตำแหน่งที่ยังว่างอยู่
แล้วจึงทำการ Push ข้อมูลลงไปในตำแหน่งที่ตัวชี้สแตกชี้อยู่.
ในกรณีที่ Push
ข้อมูลลงสู่สแตกจนตัวชี้สแตกเท่ากับจำนวนช่องของสแตกแล้ว
จะไม่สามารถทำการ
Push
ข้อมูลได้อีก จะเกิด Error
ที่เรียกว่า Stack
Overflow
2.5 Pop เป็นการทำงานของสแตกที่นำข้อมูลที่เก็บอยู่ในสแตกออกจากสแตกมาใช้งาน
เมื่อทำการ Pop
ข้อมูลออกจากสแตกแล้ว
ต้องมีการจัดการตัวชี้สแตกให้ชี้ไปยังช่องหรือตำแหน่งก่อนหน้าข้อมูลที่ได้
ทำการ
Pop ออกไป.
การ Pop
ข้อมูล จะนำข้อมูลส่วนบนสุดของสแตกออกไปทำงานตามความต้องการ
แต่ไม่สามารถ
Pop
ข้อมูลออกจากสแตกที่ว่างเปล่าได้
เพราะจะเกิด Error
ที่เรียกว่า Stack
Underflow
3.การใช้สแตกเพื่อแปลงนิพจน์
Infix เป็น
Postfix
- Infix คือ นิพจน์ที่มีตัวดำเนินการ (Operator) อยู่ระหว่างตัวถูกกระทำ (Operand) เช่น A + B เครื่องหมาย + เป็นโอเปอเรเตอร์ระหว่างโอเปอร์แรนด์ A และ B ซึ่งเห็น ว่าเป็นนิพจน์ที่มนุษย์คุ้นเคย
- postfix คือเป็นนิพจน์ที่มีการคำนวณตาม โอเปอร์เรเตอร์ที่มาก่อนหลัง เช่น นิพจน์ ABC*+ หมายถึง ทำการคูณแล้วจึงทำการบวก ซึ่งคือต้องคำนวณ B*C ก่อน แล้วจึงนำผลลัพธ์นั้นไปบวกกับ A ต่อไป
ความคิดเห็น
แสดงความคิดเห็น