Google    Youtube      Psv     สพม.11 

หน่วยที่4โครงสร้างข้อมูลสแตก

โครงสร้างสแตก

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

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

S = [s1 ,S2, … ,ST]

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

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

ST

S2

S1

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

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

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

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

ปัญหาที่ 4  รูปแบบปัญหาการทำงานบางอย่าง  เช่น  การทำงานของ  Switching Box ของเครือข่าย หรือรูปแบบการสลับตู้รถไฟบนราง  ดังในรูปที่ 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)   นำค่า  A  เข้ามาเก็บเป็นตัวแรกโดยใช้  Push(A) สแตก S = [A] ตัวชี้สแตก Top = A

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

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

(d)   ต้องการดึงค่าออกมาโดยใช้ 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  จากค่าที่ได้รับเข้าทางคีย์บอร์ด  สแตกทีได้เป็นแบบไดนามิกคือขอใช้พื้นที่หน่วยความจำให้กับสแตกตอนที่โปรแกรมทำงาน  ทำให้มีสแตกได้หลายตัวมาใช้งานพร้อมกันโดยที่ใช้ชุดปฏิบัติการเดียวกันจากตัวอย่างจะใช้สแตกเพียวตัวเดียว

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s