บทที่ 4 โครงสรางขอมูลแบบเชิงเสน (สแตก-Stack)

บทที่ 4 โครงสรางขอมูลแบบเชิงเสน (สแตก-Stack) 

    

             ความหมายของ Stack
             สแตกเปนโครงสรางขอมูลแบบหนึ่ง มีลักษณะคือขอมูลที่เก็บใน Stack จะเก็บใน ลักษณะวางทับกัน ขอมูลตัวแรกจะเป็นข้อมูลที่อยูลางสุดของ Stack และขอมูลตัวสุดทายจะเปน ขอมูลที่อยูบนสุดดังนั้นขอมูลที่นําเขาไปเก็บกอนจะออกมาทีหลังสวนขอมูลที่นําเขาไปเก็บทีหลัง จะออกมากอน จากคุณสมบัตินี้ทําใหสแตกไดชื่อวา เปนโครงสรางแบบ LIFO ( ไลโฟ ) Last - in First - out หรือ พูชดาวนลิสต 

       ( Pushdown List ) คือสมาชิกที่เขาลิสตหลังสุดจะออกจากลิสตกอน

             การจัดการ Stack

             ก็มีการใชรูปแบบพอยเตอรเมื่อ ทําการนําขอมูลเขา หรือนําขอมูลออกจะกระทําที่ปลาย ขางเดียวกันของสแตก ปลายขางนั้นเรียกว่า ท็อปของสแตก ( Top of Stack ) ซึ่งท็อปของสแตกนี้ จะเปนตัวชี้สมาชิกตัวสุดทายของสแตก

    

            โครงสรางของ Stack 

             ประกอบด้วยส่วนสําคัญ 2 สวนคือ ตัวชี้สแตก ( Stack Pointer ) และสวนสมาชิกของ สแตก ( Stack element ) ซึ่งสมาชิกของสแตกนี้จะเป็นข้อมูลชนิดเดียวกันทั้งหมดเชน ขอมูลที่ เปน เลขจํานวนเต็มเปนตน ตัวชี้สแตกจะเปนตัวควบคุมการนําสมาชิกเขาหรือออกจากสแตกและเปน ตัวบงบอกวา สแตกเต็มแล้วหรือยัง

              ซึ่งมีท็อป ( Top ) ชี้สมาชิกตัวบนสุดเมื่อ มีการนําขอมูลเขาสแตก ( Push ) สแตกท็อปจะเลื่อน ขึ้นหนึ่งตําแหนงเมื่อมีการนำขอมูลออกจากสแตก ( Pop ) สแตกท็อปจะเลื่อนลงหนึ่งตําแหนง 

                  จากรูป ( 1 ) เมื่อเพิ่มขอมูล E เขาสแตกและเมื่อดึงขอมลออกจากสแตก 

             รูปรางของสแตกไมจําเป็นต้องหันท็อปขึ้นเสมอไป แตไมวาจะอยูทิศทางใด ท็อปของ สแตกจะทําหนาที่ชี้สมาชิกตัวสุดทายของสแตก 

           Operation ของ Stack
1.    Push Stack เปนการเพิ่มขอม ูลเขาสแตกเรียกวา “พูชชงิ่ ” (Pushing)
2.    Pop Stack เปนการนําขอมูลออกจากสแตก เรียกวา “พ็อปปง” (Popping)

   
          ลําดับการเริ่มตนการคานวณ 

            อันดับ 1. เครื่องหมาย ( ) วงเล็บ 

            อันดับ 2. เครื่องหมาย ^ ยกกําลัง 

            อันดับ 3. เครื่องหมาย / หารและเครื่องหมาย * คูณ 

            อันดับ 4. เครื่องหมาย - ลบ และเครื่องหมาย + บวก