Stack (กองซ้อน)
ลักษณะของสแตก
- สแตก เป็นโครงสร้างข้อมูลแบบเชิงเส้น
- โครงสร้างข้อมูลที่จัดเก็บเป็นแบบเรียงลำดับต่อเนื่องกันไป
- การเพิ่มหรือนำข้อมูลออกจากสแตกทำได้ที่จุดปลายของสแตกทางเดียว
- มาทีหลังแต่ออกก่อน (Last In – First Out : LIFO)
ส่วนประกอบสำคัญของสแตก
1. ตัวชี้สแตก หรือ Stack Pointer เป็นตัวควบคุมการนำสมาชิกเข้า หรือออกจากสแตก
2. สมาชิกของสแตก หรือ Stack Element คือ สมาชิกของสแตก
3. ค่าสูงสุดของสแตก หรือ Max Stack เป็นค่าที่บอกว่าสแตกนี้สามารถเก็บข้อมูลได้มากที่สุดเท่าไหร่
การสร้างสแตก Stack implement
สามารถสร้างสแตกด้วยการแทนที่ข้อมูลสแตกได้ 2 วิธี คือ
1. การสร้างสแตกด้วยอาร์เรย์ เป็นการจัดสรรเนื้อที่หน่วยความจำแบบ Static
2. การสร้างสแตกด้วยลิงค์ลิสต์ เป็นการจัดสรรเนื้อที่หน่วยความจำแบบ Dynamic
การจัดการกับสแตก
ในการทำงานของสแตก ประกอบด้วย 2 กระบวนการ คือ การเพิ่มข้อมูลลงบนสแตก (Push Stack) และการดึงข้อมูลออกจากสแตก (Pop Stack)
ฟังก์ชัน Clear stack ClearStack : เป็นการดำเนินการเพื่อลบข้อมูลออกจากสแตกให้หมดกรณีใช้โครงสร้างข้อมูลอาร์เรย์ ต้องสั่งให้ช่องบนสุดของสแตกเป็น 0 Stack.Top := 0;
ฟังก์ชัน Clear stack ClearStack : กรณีใช้โครงสร้างข้อมูลลิงค์ลิสต์ ต้องสั่งให้ตัวชี้สแตกไม่ชี้ไปที่ไหนเลย
กำหนดค่าตัวชี้สแตก = Null
ฟังก์ชัน empty stack EmptyStack : เป็นการดำเนินการเพื่อตรวจสอบว่าสแตกนั้นมีข้อมูลหรือไม่ กรณีใช้โครงสร้างข้อมูลอาร์เรย์ ต้องสั่งให้ตรวจสอบว่าที่ Top ของสแตกนั้นมีค่า = 0 หรือไม่
EmptyStack := Stack.top := 0;
{ถ้าเป็นจริงจะส่งค่า True ออกมาให้โปรแกรมหลัก}
กรณีใช้โครงสร้างข้อมูลลิงค์ลิสต์ ให้ตรวจสอบว่าตัวชี้สแตกไม่ชี้ไปที่ไหน
EmptyStack := Stack.Nil;
{ถ้าเป็นจริงคืนค่า True ถ้าไม่จริง คืนค่า False}
ฟังก์ชัน Full stack FullStack : เป็นการดำเนินการเพื่อตรวจสอบว่าสแตกนั้นเต็มหรือไม่ ดำเนินการตรวจสอบเฉพาะข้อมูลอาร์เรย์ ต้องตรวจสอบว่า Top ของสแตกนั้นเป็นค่าสูงสุดที่ขอไว้หรือไม่
FullStack := Stack.top := MaxStack;
ฟังก์ชัน push stack เป็นการทำงานของสแตกในการนำข้อมูลเข้าสู่สแตกโดยก่อนที่จะนำข้อมูลเข้านั้นต้องจัดการให้ตัวชี้สแตกให้ไปชี้ในตำแหน่งต่อไปของสแตกก่อน
ฟังก์ชัน push stack ในกรณีที่ Push ข้อมูลลงสู่สแตกจนตัวชี้สแตกเท่ากับจำนวนช่องของสแตกแล้ว จะไม่สามารถทำการ Push ข้อมูลได้อีก จะเกิด Error ที่เรียกว่า Stack Overflow
อัลกอริทึมในการ push stack
1. ตรวจสอบว่าสแตกเต็มหรือไม่ โดยเปรียบเทียบค่า Top กับขนาดของตัวแปรอาร์เรย์ที่ใช้เก็บ ถ้าไม่เต็ม ทำข้อ 2. ถ้าเต็ม ทำข้อ 4.
2. ขยับตำแหน่ง Top ไปยังตำแหน่งถัดไป (Top = Top +1)
3. ทำการนำค่าที่ได้มาเก็บไว้ยังตำแหน่งของ Top {push(value,stack);}
4. แจ้งผู้ใช้งานว่า สแตกเต็มไม่สามารถเก็บข้อมูลได้
5.จบการทำงาน
ฟังก์ชัน pop stack เป็นการทำงานของสแตกที่นำข้อมูลที่เก็บอยู่ในสแตกออกจากสแตกมาใช้งาน เมื่อทำการ Pop ข้อมูลออกจากสแตกแล้วต้องมีการจัดการตัวชี้สแตกให้ชี้ไปยังช่องหรือตำแหน่งก่อนหน้าข้อมูลที่ได้ทำการ
Pop ออกไป
การ Pop ข้อมูล จะนำข้อมูลส่วนบนสุดของสแตกออกไปทำงานตามความต้องการ แต่ไม่สามารถ Pop ข้อมูลออกจากสแตกที่ว่างเปล่าได้ เพราะจะเกิด Error ที่เรียกว่า Stack Underflow
อัลกอริทึม pop stack
1. ตรวจสอบว่าสแตกว่างหรือไม่โดยเปรียบเทียบค่าTopว่ามีค่าเท่ากับ-1หรือไม่ถ้าไม่ว่างทำข้อ2.ถ้าว่างทำข้อ 4.isEmpty(stack)
2. ทำการดึงค่าในตำแหน่งของ Top ออกมาใช้งาน pop(stack)
3. ขยับตำแหน่ง Top ให้ถอยหลังลงมา (Top = Top-1) ไปทำข้อ 5.
4. ผู้ใช้งานว่า สแตกว่างไม่สามารถดึงข้อมูลไปใช้งานได้
5. จบการทำงาน
การใช้สแตกเพื่อแปลงนิพจน์ Infix เป็น Postfix Infix คือ นิพจน์ที่มีตัวดำเนินการ (Operator) อยู่ระหว่างตัวถูกกระทำ (Operand) เช่น A + B เครื่องหมาย + เป็นโอเปอเรเตอร์ระหว่างโอเปอร์แรนด์ A และ B ซึ่งเห็น ว่าเป็นนิพจน์ที่มนุษย์คุ้นเคย ตัวดำเนินการ ก็คือ เครื่องหมายทางคณิตศาสตร์ สำหรับการคำนวณต่าง ๆ เรียงตามลำดับการดำเนินการก่อนหลัง (precedence) ได้แก่
ยกกำลัง ^
คูณ หาร * , /
บวก ลบ + , -
ถ้าเครื่องหมายมีลำดับการดำเนินการเดียวกัน จะเลือกดำเนินงานของเครื่องหมาย จากซ้ายไปขวา (ยกเว้น ยกกำลัง) และถ้ามีวงเล็บจะดำเนินงานสิ่งที่อยู่ในวงเล็บก่อน
การใช้สแตกเพื่อแปลงนิพจน์ Infix เป็น Postfix ข้อเสียของนิพจน์ infix ที่ทำให้คอมไพเลอร์ยุ่งยาก คือ ลำดับความสำคัญของโอเปอร์เรเตอร์ (Precedence) ที่ต่างกัน เช่น เครื่องหมายยกกำลัง (^) มีความสำคัญมากกว่า เครื่องหมายคูณ (*) และหาร (/) และเครื่องหมายคูณและหารมี ความสำคัญมากกว่าเครื่องหมายบวก (+) และลบ (-) เครื่องหมายใดมีลำดับความสำคัญมากกว่าจะถูกคำนวณก่อน (ถ้าไม่มีวงเล็บกำกับ) เช่น A + B * C เครื่องจะคำนวณ B * C ก่อนแล้วนำผลลัพธ์นั้นไปบวกกับค่า A ซึ่งจะทำงานเหมือน กับ A + (B * C) ส่วนนิพจน์ใดที่มีโอเปอร์เรเตอร์ที่มีลำดับ ความสำคัญเท่ากัน การคำนวณจะกระทำจากซ้ายไปขวา เช่น A – B + C จะทำ A – B ก่อน แล้วจึงนำผลลัพธ์นั้นไปบวกกับ ค่า C
นิพจน์ Infix, Postfix เมื่อการประมวลผลนิพจน์ infix เป็นไปด้วยความยากที่ การคำนวณไม่เป็นไปตามลำดับของเครื่องหมายโอเปอร์เรเตอร์ที่มีก่อนหลัง คอมไพเลอร์จึงแปลงนิพจน์ infix ให้เป็น นิพจน์ postfix เสียก่อน ซึ่งนิพจน์ postfix คือนิพจน์ที่มีโอเปอร์เรเตอร์อยู่หลังโอเปอร์แรนด์ทั้งสองของมัน เช่น
AB+ หมายถึง A + B AB/ หมายถึง A / B
AB- A – B AB^ A ^ B
AB* A * B
นิพจน์ Infix, Postfix ข้อดีของนิพจน์ postfix คือเป็นนิพจน์ที่มีการคำนวณตาม โอเปอร์เรเตอร์ที่มาก่อนหลัง เช่น นิพจน์ ABC*+ หมายถึง ทำการคูณแล้วจึงทำการบวก ซึ่งคือต้องคำนวณ B*C ก่อน แล้วจึงนำผลลัพธ์นั้นไปบวกกับ A ต่อไป
กฎการแปลงนิพจน์ Infix, Postfix ด้วยมือ
1. ให้ใส่เครื่องหมายวงเล็บให้กับทุก ๆ นิพจน์ด้วยการคำนึงถึงลำดับการคำนวณ
2. ทำการเปลี่ยนสัญลักษณ์ Infix ในแต่ละวงเล็บให้มาเป็นสัญลักษณ์แบบ Postfix
3. ถอดเครื่องหมายวงเล็บทิ้งให้หมด
กฎการแปลงนิพจน์ Infix, Postfix ด้วยมือ
จงแปลงนิพจน์ A + B * C มาเป็นนิพจน์ Postfix ด้วยมือ
1. ใส่วงเล็บให้หมดตามลำดับความสำคัญ (A + (B*C) )
2. พิจารณานิพจน์ที่อยู่วงเล็บในสุด โดยย้ายเครื่องหมาย * ไปข้างหลัง C (A + (BC*)) จากนั้นย้ายโอเปอเรเตอร์ + ซึ่งอยู่ที่ตำแหน่งวงเล็บเปิดภายนอกไปยังตำแหน่งวงเล็บปิดภายนอกของคู่ตัวเอง (A(BC*)+)
ถอดเครื่องหมายวงเล็บทิ้งออกให้หมด ABC*+
การนำสแตกมาใช้ในการแปลงนิพจน์ Infix, Postfix
1. ถ้าค่า input เป็น operand ให้นำค่าไปเป็น Output
2. ถ้าค่า input เป็น operator (เครื่องหมายคณิตศาสตร์) ให้พิจารณาดังนี้
3. ถ้า สแตกว่าง ให้นำ operator ใส่สแตก
4. ถ้า สแตกไม่ว่าง ให้นำ operator ไปเปรียบกับค่า operator ตัวบนในสแตก ถ้าค่า operator ที่เป็น input มีค่า precedence น้อยกว่าหรือเท่ากับค่า operator ตัวบนของสแตก ให้ดึง operator ตัวบนในสแตกไปเป็น output แล้วเปรียบเทียบกับ operator ในสแตกตัวถัดไป แล้วเปรียบเทียบ
5. ถ้า input เป็น ( ให้ใส่ลงสแตก
6. ถ้าinput เป็น ) ให้ดึงข้อมูลออกจากสแตกทีละตัวไปเป็น output จนกระทั่งพบ (ในสแตกให้ดึงออกมาทิ้งไปไม่ต้องไปใส่เป็นoutput
7. ถ้า input หมด และสแตกยังมีข้อมูลอยู่ ให้ดึงข้อมูลออกจาก stack ที่ตัวไปเป็น output จนกระทั่งสแตกว่าง
ไม่มีความคิดเห็น:
แสดงความคิดเห็น