สแตค (Stack)

                สแตคเป็นโครงสร้างข้อมูลที่มีลักษณะแบบลำดับ (sequential) คือการกระทำกับข้อมูลจะกระทำที่ปลายข้างเดียวกันที่ส่วนปลายสุดของสแตค การกระทำกับข้อมูลของสแตคประกอบไปด้วยการนำเข้าข้อมูลเข้า (PUSH) ที่ส่วนบนสุดของสแตค และการนำข้อมูลออก (POP) ที่ส่วนบนสุดของสแตคเช่นกัน ในการจะ Push ข้อมูลเข้าก็ต้องตรวจสอบด้วยว่าข้อมูลในสแตคเต็มหรือไม่ หากสแตคเต็มก็จะไม่สามารถ Push หรือนำข้อมูลเข้าได้ เช่นเดียวกับการ Pop ข้อมูลออกก็ต้องตรวจสอบด้วยว่ามีข้อมูลอยู่ในสแตคหรือไม่ หากไม่มีข้อมูลอยู่ในสแตคหรือสแตคว่าง (empty stack) ก็ไม่สามารถ pop ได้

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

รูปแสดงลักษณะของสแตค ที่ประกอบด้วยข้อมูล A , B , C , D และ E มี TOP ที่ชี้ที่สมาชิกตัวบนสุดของสแตค   

Operation ของสแตค

  1. การเพิ่มข้อมูลลงในสแตค (pushing stack)
  2. การดึงข้อมูลออกจากสแตค (popping stack)

 

การเพิ่มข้อมูลลงในสแตค

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

      จากรูปแสดง การ Push ข้อมูล ABC ลงในสแตคที่มีการจองเนื้อที่ไว้ N ตัว โดยมี TOP ชี้ข้อมูลตัวที่เข้ามาล่าสุด โดยค่าของ TOP จะเพิ่มขึ้นทุกครั้งเมื่อมีข้อมูลเข้ามาในสแตค

 

การดึงข้อมูลออกจากสแตค

ก่อนที่จะดึงข้อมูลออกจากสแตคต้องตรวจสอบก่อนว่าสแตคมีข้อมูลอยู่หรือไม่ หรือว่าเป็นสแตคว่าง (Empty Stack)

 

การใช้ สแตค เพื่อแปลรูปนิพจน์ทางคณิตศาสตร์

รูปแบบนิพจน์ทางคณิตศาสตร์

• นิพจน์ Infix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่ระหว่างตัวดำเนินการ (Operands) เช่น A+B-C

• นิพจน์ Prefix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หน้าตัวดำเนินการ (Operands) เช่น +-AB

• นิพจน์ Postfix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หลังตัวดำเนินการ (Operands) เช่น AC*+

 

ลำดับการทำงานของตัวดำเนินการทางคณิตศาสตร์ (Operator Priority) 

  มีการลำดับความสำคัญของตัวดำเนินการจากลำดับสำคัญมากสุดไปน้อยสุด คือ ลำดับที่มีความสำคัญมากที่ต้องทำก่อน ไปจนถึงลำดับที่มีความสำคัญน้อยสุดที่ไว้ทำทีหลัง ดังนี้

 

ทำในเครื่องหมายวงเล็บ

เครื่องหมายยกกำลัง ( ^ )

เครื่องหมายคูณ ( * ) , หาร ( / )

เครื่องหมายบวก ( + ) , ลบ ( - )

 

ตัวอย่างนิพจน์ทางคณิตศาสตร์และลำดับการคำนวณ

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

  เราสามารถแปลงนิพจน์ Infix ให้เป็น Postfix ได้โดยอาศัยสแตคที่มีคุณสมบัติการเข้าหลังออกก่อนหรือ LIFO โดยมีอัลกอริทึมในการแปลงนิพจน์ ดังนี้ 

1. ถ้าข้อมูลเข้า (input) เป็นตัวถูกดำเนินการ (operand) ให้นำออกไปเป็นผลลัพธ์ (output)

2. ถ้าข้อมูลเข้าเป็นตัวดำเนินการ (operator) ให้ดำเนินการดังนี้

     2.1 ถ้าสแตคว่าง ให้ push operator ลงในสแตค

     2.2 ถ้าสแตคไม่ว่าง ให้เปรียบเทียบ operator ที่เข้ามากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตค

         2.2.1 ถ้า operator ที่เข้ามามีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตคให้ push ลงสแตค

         2.2.2 ถ้า operator ที่เข้ามามีความสำคัญน้อยกว่าหรือเท่ากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตค ให้ pop สแตคออกไปเป็นผลลัพธ์ แล้วทำการเปรียบเทียบ operator ที่เข้ามากับ operator ที่ตำแหน่ง TOP ต่อไป จะหยุดจนกว่า operator ที่เข้ามาจะมีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตค แล้วจึง push operator ที่เข้ามานั้นลงสแตค

3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิด ให้ push ลงสแตค

4. ถ้าข้อมูลเข้าเป็นวงเล็บปิด ให้ pop ข้อมูลออกจากสแตคไปเป็นผลลัพธ์จนกว่าจะถึงวงเล็บ เปิด จากนั้นทิ้งวงเล็บเปิดและปิดทิ้งไป

5. ถ้าข้อมูลเข้าหมด ให้ pop ข้อมูลออกจากสแตคไปเป็นผลลัพธ์จนกว่าสแตคจะว่าง

ตัวอย่างการแปลงนิพจน์ Infix เป็นนิพจน์ Postfix

นิพจน์ A + B * C

นิพจน์ (A * B) + (C / D)

นิพจน์ A / B + (C – D)

นิพจน์ (A + B) * ( C ^ D – E ) * F

โครงสร้างข้อมูลสแตก
        โครงสร้างข้อมูลที่รู้จักและนำมาใช้งานมากชนิดหนึ่งก็คือ  สแตก  ( 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. ถ้าสแตกไม่เต็ม

a.       เพิ่มค่าให้กับ Top โดยการบวก 1ฃ
b.      ทำการนำค่าที่ได้มาเก็บลงในสแตกในตำแหน่ง Top

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

้  มีอัลกอริทึมทำงานเป็นดังในตารางที่ 4.2

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

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

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

 


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

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


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


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


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


                           
( 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

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

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

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

Infix

Postfix

Prefix

A + ( B * C )
(A +  B )* C 
A +  B - C
(A + B) * ( C  -  D )
(A + B) *C  - (D  - E ) ) $ ( F + G )

ABC  * +
AB + C *
AB + C –
AB + CD - *
AB + C * DE – FG+$

+A*BC
*+ABC
-+ ABC
*+AB-CD
$-*+ABC-DE+FG

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

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

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

      a.       รับค่า  ( Token )  ตัวถัดไปในนิพจน์ Infix  ประกอบด้วย ค่าคงที่  ตัวแปร  เครื่องหมาย  คำนวณ  วงเล็บเปิดและปิด 
      b.      ค่าที่รับเข้ามา  ถ้าเป็น 
          i.      โอเปอแร้น  (ค่าคงที่ , ตัวแปร )   นำไปแสดงทางจอภาพ 
          ii.      วงเล็บเปิด    ให้นำไปใส่ลงสแตก ( Push ) 
          iii.      วงเล็บปิด   ดึงค่าออกจากสแตก ( Pop )  และนำไปแสดงทางจอภาพ  ทำจนกว่าจะพบวงเล็บเปิด  ไม่แสดงทางจอภาพ  หรือสแตกว่างไม่พบวงเล็บเปิดเกิดข้อผิดพลาด 
          iv.  เครื่องหมายคำนวณ     ถ้าสแตกว่าง  หรือค่าที่รับมามี  Precedence  สูงกว่า  ค่าบนสแตกให้นำใส่ลงในสแตก  ( Push ) ถ้าหากค่าที่รับมามี  precedence  น้อยกว่าค่าบนสแตกให้ดึงค่าออกมาจากสแตก ( Pop )  และนำไปแสดงทางจอภาพตามด้วยค่าที่รับมา

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




 

การหาค่าคำตอบจากการคำนวณนิพจน์  Postifix
            จากการแปลงนิพจน์แบบ Infix  เป็นแบบ Postfix  ทำให้นิพจน์ที่ได้ไม่มีเครื่องหมายวงเล็บ  ต่อจากนั้นจะทำการหาค่าคำตอบโดยสแกนนิพจน์  Postfix  ทีละตัวจากซ้ายไปขวา  เมื่อใดที่พบโอเปอรแร้นก็นำเก็บลงในสแตก  ถ้าพบโอเปอเรเตอร์เมื่อใด   ก็ดึงโอเปอแร้นสองค่าออกจากสแตกมาคำนวณด้วยโอเปอเรเตอร์ตัวนั้น  และใส่กลับลงไปในสแตก  สุดท้ายคำตอบที่ได้จะอยู่ในสแตกเพียงค่าเดียว  ซึ่งจะได้อัลกอริทึมในตารางที่ 4.7
ตารางที่ 4.7  อัลกอริทึมการหาค่าคำตอบจากนิพจน์  Postfix
1.      สร้างสแตกที่ว่างเปล่ายังไม่มีการเก็บค่า
2.      ทำงานต่อไปนี้ซ้ำจนกว่าถึงที่จุดสิ้นสุดของนิพจน์
a.       รับค่า ( Token )  ตัวถัดไปในนิพจน์ RPN ประกอบด้วย ค่าคงที่ ตัวแปร เครื่องหมายคำนวณ
b.      ค่าที่รับเข้ามา  ถ้าเป็นโอเปอแร้น  ให้นำใส่ลงในสแตก  ( push )  แต่ถ้าเป็นเครื่องหมายคำนวณให้ทำดังนี้ 
         i.      ดึงค่าออกมาสแตก  ( Pop ) สองค่า  ถ้าไม่ครบให้แจ้งเกิดข้อผิดพลาด        

         ii.      นำเครื่องหมายคำนวณทำการประมวลผลกับค่าทั้งสอง   

         iii.      นำผลลัพธ์ที่ได้ใส่กลับลงในสแตก  ( Push )

  1. เมื่อถึงจุดสิ้นสุดของนิพจน์  ค่าที่เป็นคำตอบจะอยู่บนสแตก  ซึ่งมีเพียงค่าเดียวเท่านั้น

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

นิพจน์  Postifix

ค่าที่ได้

สแตก

2        4  *  9  5  +  - 
4  *  9  5  +  -
*  9  5  +  - 
9  5  +  -
5  +  -
+  -
-

 

2        *  4  =  8

       9  +  5  =  14
      8  -  14  =  -  6

2
2        4
8
8        9
8     9    5
8     14
-  6
-  6