Stack (กองซ้อน)

วัตถุประสงค์

• เข้าใจแนวคิดและหลักการของโครงสร้างข้อมูลแบบสแตก
• อธิบายหลักการทำงานของฟังก์ชันการดำเนินงานพื้นฐานของสแตกได้
• เข้าใจหลักการสร้างสแตกด้วยอาร์เรย์และลิงค์ลิสต์ได้
• สามารถแปลงนิพจน์ Infix ให้เป็น Postfix ได้
• เข้าใจหลักการรีเคอร์ซีฟ

ลักษณะของสแตก Stack        

• สแตก เป็นโครงสร้างข้อมูลแบบเชิงเส้น
• โครงสร้างข้อมูลที่จัดเก็บเป็นแบบเรียงลำดับต่อเนื่องกันไป
• การเพิ่มหรือนำข้อมูลออกจากสแตกทำได้ที่จุดปลายของสแตกทางเดียว
• มาทีหลังแต่ออกก่อน (Last In – First Out : LIFO)

ส่วนประกอบสำคัญของสแตก

1. ตัวชี้สแตก หรือ Stack Pointer เป็นตัวควบคุมการนำสมาชิกเข้า หรือออกจากสแตก
2. สมาชิกของสแตก หรือ Stack Element คือ สมาชิกของสแตก 
3. ค่าสูงสุดของสแตก หรือ Max Stack เป็นค่าที่บอกว่าสแตกนี้สามารถเก็บข้อมูลได้มากที่สุดเท่าไหร่

การสร้างสแตก Stack implement

      สามารถสร้างสแตกด้วยการแทนที่ข้อมูลสแตกได้ 2 วิธี คือ

• การสร้างสแตกด้วยอาร์เรย์ เป็นการจัดสรรเนื้อที่หน่วยความจำแบบ Static 
• การสร้างสแตกด้วยลิงค์ลิสต์ เป็นการจัดสรรเนื้อที่หน่วยความจำแบบ Dynamic

การจัดการกับสแตก

       ในการทำงานของสแตก ประกอบด้วย 2 กระบวนการ คือ การเพิ่มข้อมูลลงบนสแตก (Push Stack) และการดึงข้อมูลออกจากสแตก (Pop Stack)

การดำเนินงานของสแตก Stack operations

ประกอบด้วยฟังก์ชันพื้นฐาน ดังนี้

• ClearStack
• EmptyStack
• FullStack
• Push
• Pop

ฟังก์ชัน 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 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

อัลกอริทึม pop stack

1. ตรวจสอบว่าสแตกว่างหรือไม่ โดยเปรียบเทียบค่า Top ว่ามีค่าเท่ากับ -1 หรือไม่ ถ้าไม่ว่าง ทำข้อ 2. ถ้าว่าง ทำข้อ 4. isEmpty(stack)
2. ทำการดึงค่าในตำแหน่งของ Top ออกมาใช้งาน pop(stack)
3. ขยับตำแหน่ง Top ให้ถอยหลังลงมา (Top = Top-1) ไปทำข้อ 5.
4. แจ้งผู้ใช้งานว่า สแตกว่างไม่สามารถดึงข้อมูลไปใช้งานได้
5. จบการทงาน

เปรียบเทียบประสิทธิภาพของการสร้างสแตกด้วยอะเรย์และลิงค์ลิสต์

• การแทนที่ข้อมูลสแตกด้วยอะเรย์ มีข้อจำกัด สำหรับขนาดของสแตกและจะต้องจองเนื้อที่เท่ากับขนาดที่ ใหญ่ที่สุดของสแตกไว้เลย
• การแทนที่ข้อมูลสแตกด้วยลิงค์ลิสต์ ไม่มี ข้อจำกัดของขนาดของสแตกและหน่วยความจำจะถูกใช้ก็ต่อ เมื่อมีข้อมูลจริงๆ แล้วเท่านั้น เพราะเป็นการจัดสรรเนื้อที่หน่วย ความจำแบบไดนามิก

การประยุกต์ใช้งานสแตก

• การเรียงลำดับข้อมูลแบบย้อนกลับ (Reversing Data)
• การแตกข้อมูลออกเป็นส่วน ๆ (Parsing)
• การหน่วงเวลา (Postponement)
• การย้อนรอย (Backtracking Steps)

การใช้สแตกเพื่อแปลงนิพจน์ 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*)+)
3. ถอดเครื่องหมายวงเล็บทิ้งออกให้หมด                   ABC*+

จงแปลงนิพจน์ 5 * 6 – 10 มาเป็นนิพจน์ Postfix ด้วยมือ                                                                                                                             5 * 6 – 10        = ((5 * 6) – 10)
                        = ((56*)-10)
                        = ((56*)10-)
                        = 56*10-

นิพจน์ Infix, Postfix

การนำสแตกมาใช้ในการแปลงนิพจน์ 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 จนกระทั่งสแตกว่าง