Stack

โครงสร้างข้อมูลสแตก

                โครงสร้างสแตกข้อมูลที่รู้จักและนำมาใช้งานชนิดหนึ่งก็คือ สแตก (Stack) มีลักษณะเป็นรายการในแนวเชิงเส้น (Linear List) รูปแบบหนึ่ง และมีข้อกำหนดให้ชุดปฏิบัติการ สามารถเพิ่มและลบรายการเพียงด้านเดียว ซึ่งเป็นด้านบนสุดของสแตก (Top of Stack)

เรียกว่าตัวชี้สแตก (Stack Pointer) มีรูปแบบเป็น (Top)(S)โดยสแตกมีการกำหนดเป็นรูปแบบดังนี้

  S = [s_{1 ,S}2, … ,S_T]

ด้านบนสุดของสแตกจะอยู่ที่ Top (S) =S_T และมีจำนวนสมาชิกในสแตกเท่ากับ T

ดังในรูปที่ 4.1

รูปที่ 4.1 ตัวอย่างลักษณะสแตกที่มีสมาชิกเท่ากับ T มีตัวชี้สแตก Top

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

ปัญหาที่ 1  เนื่องจากคอมพิวเตอร์ทำงานในรูปแบบของเลขฐาน 2 แต่ในส่วนของผู้ใช้งานจะเป็นเลขฐาน 10 จึงต้องแปลงค่าจากเลขฐาน 10 ไปเป็นเลขฐาน 2 เช่น เปลี่ยนจาก 26 เป็น 11010

ปัญหาที่ 2  คอมไพเลอร์ (Compiler) จะต้องคำนวณนิพจน์ (Expression) ทางคณิตศาสตร์ที่มีเครี่องหมายวงเล็บเปิดและปิดเข้ามาเกี่ยวข้อง

ปัญหาที่ 3  โปรแกรมเกมเล่นไพ่ (Card Game) จะมีที่วางกองไพ่และการแจกไพ่ได้เฉพาะใบที่อยู่บนสุด

ปัญหาที่ 4  รูปแบบปัญหาการทำงานบางอย่าง  เช่น  การทำงานของ  Switching Box ของเครือข่าย หรือรูปแบบการสลับตู้รถไฟบนราง  ดังในรูปที่ 4.3

 

รูปที่ 4.3 ตัวอย่างการใช้สแตกแก้ปัญหาการสลับตู้รถไฟบนราง

ปัญหาต่าง ๆ  เหล่านี้สามารถแก้ไขโดยใช้โครงสร้างสแตก  ซึ่งมีลักษณะการทำงานในรูปแบบที่เรียกว่าเข้าทีหลังออกก่อน (Last-In-First-Out, LIFO) เมื่อมีค่าใหม่เข้ามาก็จะใส่ลงในสแตกซ้อนทับค่าเดิมที่เก็บอยู่ลงไปอยู่ด้านล่างไปเรื่อย ๆ ในลักษณะแบบนี้

การปฏิบัติการของสแตก

                จากลักษณะดังที่กล่าวมาของสแตก  จะต้องมีการปฏิบัติการเข้ามาช่วยการทำงานของสแตกให้มีความถูกต้อง

1.    CreateStack( ) ใช้สร้างสแตกใหม่ขึ้นมาใช้งานและกำหนดค่าเริ่มต้นต่าง ๆ

2.    Push(value,  stack)  ใช้เพิ่มค่าใหม่เก็บลงในสแตกที่ใช้งานอยู่  มีอัลกอริทึมการทำงานเป็นดังในตารางที่ 4.1

ตารางที่ 4.1  อัลกอริทึมการเพิ่มค่าใหม่เก็บลงในสแตก

        1.  ตรวจสอบสแตกว่าจะมีสมาชิกอยู่เต็มหรือไม่  โดยเปรียบเทียบค่า Top กับขนาดอาร์เรย์

        2.  ถ้าสแตกไม่เต็ม

                    2.1  เพิ่มค่าให้กับ Top โดยการบวก 1

                    2.2  ทำการนำค่าที่ได้มาเก็บลงในสแตกในตำแหน่ง Top ไม่เช่นนั้นแจ้งกลับมาว่าสแตกเต็ม

        3.  Pop(stack)  ใช้ดึงค่าออกจากสแตกที่ใช้งานอยู่และส่งค่า value กลับมาให้ มีอัลกอริทึมการ   ทำงานเป็นดังในตารางที่ 4.2

ตารางที่ 4.2  อัลกอริทึมดึงค่าออกจากสแตก

1.    ตรวจสอบว่าสแตกว่างหรือไม่ โดยเปรียบเทียบค่า Top กับขนาดอาร์เรย์

2.    ถ้าสแตกไม่ว่าง

2.1  ทำการดึงค่าในตำแหน่ง  Top ออกมาให้

2.2  ลดค่าของ Top โดยการลบ 1 ไม่เช่นนั้นแจ้งกลับมาว่าสแตกว่าง

        3.  isEmpty(stack)  ใช้ตรวจสอบว่าสแตกที่ใช้งานอยู่ว่างหรือไม่  ถ้าไม่มีค่าเก็บไว้เลยจะส่งค่าจริงกลับให้

                   

                เมื่อนำสแตกมาใช้งานตามลำดับดังในรูป (a) ถึง (g) มีการทำงานโดยใช้ชุดปฏิบัติการ Push และ Pop ดังนี้

(a)    เริ่มต้นสร้างสแตก  S ขึ้นมาทำงานจะได้เป็นสแตกว่าง  ไม่มีสมาชิกโดยตัวชึ้สแตก Top ยังไม่มีค่า

(b)   นำค่า  B เก็บต่อโดยใช้ Push(B) สแตก S = [A,B] ตัวชี้สแตก Top = B

          

(c)นำค่า C เก็บต่อโดยใช้ Push(C) สแตก S = [A,B,C]ตัวชี้สแตก Top =C

           

(d)    ต้องการดึงค่าออกมาโดยใช้ Pop( ) สแตก S = [A,B] ตัวชี้สแตกTop = B

                 

(e)ต้องการดึงค่าออกมาใช้ Push() สแตก S=[A,B] ตัวชี้สแตก Top =c

      

(f) นำค่า D, E เก็บต่อโดยใช้ Push(D) และ Push(E) ตามลำดับ สแตก S = [A,B,D,E] ตัวชี้สแตก Top = E

       

(g) ดึงค่าออกมา 3 ค่าโดยใช้ Pop( )  3  ครั้งและเก็บค่า F โดยใช้ Push(F) สแตก S = [A,F] ตัวชี้สแตก Top = F

                  

          จะเห็นว่าการทำงานของสแตกเมื่อมีค่าใดส่งเข้ามาเก็บเป็นตัวสุดท้ายก็จะอยู่บนสุด  ค่าที่ใส่ลงมาก่อนหน้านี้ก็จะถูกซ้อนทับตามลำดับ  หากมีการดึงค่าออกมาใช้ค่าที่อยู่บนสุดจะถูกดึงออกมาก่อน  ลักษณะที่ได้จึงเป็นการกลับกันของลำดับการใช้งานและเรียกว่าเข้าทีหลังออกก่อน

ตัวอย่างการใช้สแตก

                จากปัญหาในตอนต้นกล่าวถึงปัญหาการเปลี่ยนเลขฐาน  10  เป็นเลขฐาน  2   เนื่องจากการคำนวณเป็นการหารเลขฐาน  10  เศษที่เหลือจะได้เป็นเลขฐาน  2  เมื่อนำมาแสดงผลจะเป็นตัวเลขจากซ้ายไปขวา  แต่เลขฐาน  2  เป็นตัวเลขจากขวาไปซ้ายจึงเกิดการสลับด้านกัน  จึงนำสแตกมาช่วยแก้ปัญหานี้  ดังในตารางที่ 4.3 คือ โปรแกรม Stack.c

ตารางที่ 4.3 ตัวอย่างโปรแกรม Stack.c

                เป็นการสร้างสแตกขึ้นมาโดยใช้โครงสร้างข้อมูลเรคคอร์ด   และสร้างชุดปฏิบัติการให้กับสแตกขึ้นมาสำหนับเรียกใช้งานเพื่อ     แก้ใขการเปลี่ยนเลขฐาน  10  เป็นเลขฐาน  2  จากค่าที่ได้รับเข้าทางคีย์บอร์ด  สแตกทีได้เป็นแบบไดนามิกคือขอใช้พื้นที่หน่วยความจำให้กับสแตกตอนที่โปรแกรมทำงาน  ทำให้มีสแตกได้หลายตัวมาใช้งานพร้อมกันโดยที่ใช้ชุดปฏิบัติการเดียวกันจากตัวอย่างจะใช้สแตกเพียงตัวเดียว

การใช้สแตกแก้ปัญหาการแปลงนิพจน์คณิตศาสตร์

                คอมไพเลอร์จะแปลงคำสั่งจากภาษาระดับสูง  (High-level  Language)  ไปเป็นภาษาเครื่อง (Machine Language) ส่วนหนึ่งที่ต้องแปลงคือนิพจน์คณิตศาสตร์ เช่น X = A * B + C ซึ่งมีลักษณะที่เรียกว่า  Infix  Notation  มีเครื่องหมายคำนวณอยู่ระหว่างโอเปอแร้น (Operand) โดยแปลงไปเป็นนิพจน์แบบ Postfix  Notation มีเครื่องหมายคำนวณนำหน้าโอเปอแร้น แต่เนื่องจากนิพจน์แบบ Infix มีการนำเครื่องหมายวงเล็บเข้ามาใช้ทำให้ทิศทางการคำนวณเปลี่ยนไป   ดังในตารางที่ 4.4 เป็นตัวอย่างของการคำนวณแบบเดียวกัน

ตารางที่ 4.4  ลักษณะนิพจน์แบบ Infix, Posifix, และ Prefix Notation

การแปลงนิพจน์แบบ Infix เป็นแบบ  Postfix

          เมื่อพิจารณาการแปลงนิพจน์แบบ Infix เป็นแบบ Postfix เป็นขั้นตอนการแปลงโดยเริ่มต้นจากสแกนนิพจน์ Infix ทีละตัว  หากพบวงเล็บก็จะทำส่วนที่อยู่ในวงเล็บให้เสร็จก่อนเป็นนิพจน์ย่อย (Subexpression) ซึ่งจะได้เป็นอัลกอริทึมดังในตารางที่ 4.5

ตารางที่ 4.5  อัลกอริทึมการแปลงนิพจน์แบบ Infix เป็นแบบ Postfix

1. สร้างสแตกที่ว่างเปล่ายังไม่มีการเก็บค่า
2. ถ้าค่าในนิพจน์ Infix ยังไม่หมด หรือเกิดข้อผิดพลาด ให้ทำดังนี้

a.       รับค่า  (Token) ตัวถัดไปในนิพจน์  Infix (ประกอบด้วย ค่าคงที่ ตัวแปร เครื่องหมายคำนวณ วงเล็บเปิดและปิด

b.       ค่าที่รับเข้ามา ถ้าเป็น

b.1  โอเปอแร้น (ค่าคงที่,ตัวแปร)                               นำไปแสดงทางจอภาพ

b.2  วงเล็บเปิด                                                               ให้นำใส่ลงในสแตก (Push)

b.3  วงเล็บปิด                                                                 ดึงค่าออกจากสแตก (Pop) และนำไปแสดงทางจอภาพ  ทำจนกว่าจะพบวงเล็บเปิด

b.4  เครื่องหมายคำนวณ                                               ถ้าสแตกว่าง  หรือค่าที่รับมามี Precedence สูงกว่าค่าบนสแตกให้นำใส่ลงในสแตก (Push) ถ้าหากค่าที่รับมามี Precedence น้อยกว่าค่าบนสแตกให้ดึงค่าออกจากสแตก (Pop)

            3.  เมื่อทำจนค่าในนิพจน์ Infix หมด ให้ดึงค่าออกจากสแตก (Pop) แสดงทางจอภาพตามลำดับ จนกว่าสแตกว่าง

             จากอัลกอริทึมดังกล่าวเมื่อนำมาใช้กับตัวอย่างนิพจน์ 7*8-(2+3) จะได้เป็นลำดับขั้นตอนดังในรูปที่ 4.4 หรือเขียนเป็นแบบตารางได้ดังในตารางที่ 4.6

ตารางที่ 4.6 การแปลงนิพจน์ 7*8-(2+3) เป็นนิพจน์ Postfix

การหาค่าคำตอบจากการคำนวณนิพจน์ Postfix

                   จากการแปลงนิพจน์แบบ Infix เป็นแบบ Postfix ทำให้นิพจน์ที่ได้ไม่มีเครื่องหมายวงเล็บ  ต่อจากนั้นจะทำการหาค่าคำตอบโดยสแกนนิพจน์ Postfix ทีละตัวจากซ้ายไปขวา เมื่อใดที่พบโอเปอแร้นก็นำเก็บลงในสแตก  สุดท้ายคำตอบที่ได้จะอยู่ในสแตกเพียงค่าเดียวซึ่งจะได้เป็นอัลกอริทึมดังในตารางที่ 4.7

ตารางที่ 4.7  อัลกอริทึมการหาค่าคำตอบจากนิพจน์ Postfix

                จากอัลกอริทึมดังกล่าวเมื่อนำมาใช้กับตัวอย่างนิพจน์ 24*95+- จะเป็นไปตามลำดับขั้นตอนดังในรูปที่ 4.5 หรือเขียนเป็นแบบตารางได้ดังในตารางตารางที่ 4.8

    ตาราง 4.8 การหาค่าคำตอบจากนิพจน์