krukanchana - โครงสร้างข้อมูลแบบ Stack

โครงสร้างข้อมูลแบบ Stack

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

การกระทำ(Operation) ที่เกี่ยวข้องกับโครงสร้างข้อมูลแบบ Stack

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

- การนำข้อมูลเข้าไปในกองซ้อน (Push)

กระทำที่ส่วนบนของสแตก (Top) ซึ่งต้องมีการตรวจสอบก่อนว่าสแตกเต็มหรือไม่ เป็นการดำเนินการที่นำข้อมูลเข้าไปเก็บไว้ด้านบนสุดของกองซ้อน (Top of the Stack) เรื่อย ๆ จนกว่ากองซ้อนไม่สามารถนำข้อมูลเข้าไปเก็บได้จะเรียกว่า กองซ้อนเต็ม (Stack Full)

- การนำข้อมูลออกจากกองซ้อน (Pop)

การทำงานจะตรงข้ามกับ Push จะดึงเอาข้อมูลที่อยู่บนสุดออกมาก่อน แต่ก่อนที่จะดึงจะมีการตรวจสอบว่ากองซ้อนว่างหรือไม่ ถ้าว่างจะไม่สามารถนำข้อมูลออกได้ แสดงว่ากองซ้อนว่าง (Stack Empty)ถ้าไม่ว่างจะนำเอาข้อมูลออกแล้วเลื่อนตัวชี้ไปยังตำแหน่งถัดลงไป

การสร้างสแตก (CREATE)

หมายถึง การแทนที่ข้อมูลของ stack ด้วย array ซึ่ง เป็นการจัดสรรเนื้อที่หน่วยความจำแบบ static นั่นคือ มีการกำหนดขนาดของ stack ล่วงหน้าว่ามีขนาดเท่าใด และจะมีการจัดสรรเนื้อที่หน่วยความจำให้เลย

- การแทนที่โครงสร้างข้อมูลแบบกองซ้อนด้วยแถวลำดับ

แบบลำดับจะต้องมีการจองพื้นที่หน่วยความจำไว้ล่วงหน้า ว่าจะมีขนาดเท่าใด โดยแถวลำดับนี้จะปิดปลายด้านหนึ่งไว้ เพื่อให้ข้อมูลเข้า-ออกทางเดียว ปฏิบัติการมี 4 ขั้นตอนคือ

1. การสร้าง

2. การ Push

3. การ Pop

4. การ แสดง

(Last In First Out /LIFO) หมายถึง ข้อมูลที่นำเข้าเป็นลำดับสุดท้ายจะถูกนำออกจากสแตกเป็๋นลำดับแรก

รูปที่ 1 การPush ข้อมูลลงในสแต็ก

1. ฟังก์ชัน Push ทำหน้าที่เพิ่มข้อมูลเข้าไปในชั้นบนสุดของแสต็กปัญหาของการ Push ก็คือต้องมีความมั่นใจว่าภายในสแต้กนั้นมีพื้นที่ว่างพอที่จะบรรจุข้อมูลใหม่ลงไปได้ถ้าหาก สแต็กหรือมีพื้นที่ว่างไม่เพียงพอ จะทำให้เกิดสถานะโอเวอร์โฟลว์ (Overflow State) ส่งผลให้ไม่สามารถใส่ข้อมูลใหม่เข้าไปในสแต็กได้อีก ซึ่งโดยทั่วไปเราจะใช้ฟังก์ชัน fullStack ในการตรวจสอบว่าสแต็กเต็มหรือไม่ โดยพิจารณาจากรูปที่ 1 ที่แสดงถึงฟังก์ชัน Push ด้วยการใส่ข้อมูลลงในสแต็ก

รูปที่ 2 การ Pop ข้อมูลออกจากสแต็ก

2. ฟังก์ชัน Pop เป็นฟังก์ชันคืนค่าข้อมูลที่อยู่บนสุดของสแต็กส่งคืนให้กับผู้ใช้ พร้อม ทั้งลบข้อมูลรายการนั้นออกไปด้วย ส่งผลให้ข้อมูลรายการถัดไปกลีบมาอยู่ในสถานะบนสุดอีกครั้ง และเมื่อรายการสุดท้ายในสแต็กได้ถูกนำออกไปทั้งหมด สแต็กดังกล่าวก็จะถูกกำหนดให้อยู่ในสถานะว่าง (Empty State) แต่หากในขณะนั้นมีการเรียกใช้ฟังก์ชัน Pop บนสแต็กว่างเปล่าจะทำให้เกิดสถานะอันเดอร์โฟลว์(Underflow State) ดังนั้นเมื่อต้องการ Pop ข้อมูลออกจาก สแต็ก จึงจำเป็นต้องตรวจสอบก่อนว่าสแต็กนั้นว่างหรือไม่ ซึ่งโดยทั่วไปเราจะใช้ฟังก์ชัน empty Stack ในการตรวจสอบว่าสแต็กว่างหรือไม่ โดยพิจารณาจากรูปที่ 2 ที่แสดงถึงฟังก์ชัน Pop ด้วยการนำข้อมูลออกจากสแต็ก

รูปที่ 3 การอ่านข้อมูลด้วย Stack Top

3. ฟังก์ชัน Stack Top ฟังก์ชันนี้จะมีความคล้ายคลึงกับฟังก์ชัน Pop ที่คืนค่าข้อมูล ด้วยการคัดลอกข้อมูลบนสุดของสแต็กส่งคืนให้กับผู้ใช้ แต่จะแตกต่างตรงที่ฟังก์ชัน Stack Top นั้น จะคืนค่าข้อมูลไปยังผู้ใช้งานเท่านั้น โดยไม่มีการลบข้อมูลออกจากสแต็กแต่อย่างใด กล่าวคือ หน้าที่ของฟังก์ชัน StackTop นั้นก็คือการอ่านข้อมูลบนสแต็กที่อยู่ลำดับบนสุดของสแต็กนั่นเอง โดยพิจารณาจากรูปที่ 3 ที่แสดงถึงฟังก์ชันStack Topด้วยการอ่านข้อมูลจากสแต็กที่อยู่ใน ลำดับสุดส่งคืนกลับไปยังผู้ใช้เพื่อนำไปใช้งานต่อไป

รูปที่ 4 การสร้างสแต็กด้วยอาร์เรย์

การสร้างสแต็กด้วยอาร์เรย์

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

อย่างไรก็ตาม การเลือกโครงสร้างข้อมูลแบบอาร์เรย์มาสร้างสแต็กนั้น จะมีข้อเสียอยู่หลายประการด้วยกัน คือ

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

การสร้างสแต็กด้วยลิงก์ลิสต์

การสร้างสแต็กด้วยโครงสร้างข้อมูลแบบลิงก์ลิสต์จัดเป็นอีกวิธีหนึ่งที่มีประสิทธิภาพสูงซึ่งลิงก์ลิสต์จะจัดสรรหน่วยความจำแบบไดนามิก (Dynamic) ดังนั้นจึงไม่ต้องกำหนดขนาดคงที่อย่างเช่นอาร์เรย์ กล่าวคือหน่วยความจำจะถูกจัดสรรเมื่อมีการใช้งานจริงเท่านั้น อีกทั้งยังสามารถจัดเก็บข้อมูลต่างชนิดกันได้ นอกจากนี้แล้ว การสร้างสแต็กด้วยลิงก์ลิสต์ สแต็กจะไม่มีวันเต็มต่อเมื่อยังมีเนื้อที่เพียงพอต่อการจัดสรรได้อยู่
ส่วนประกอบสำคัญของลิงก์ลิสต์ก็คือ โครงสร้างสองส่วนที่มีความแตกต่างกันคือ ส่วนหัว(Head) และส่วนข้อมูล (Data Node) โดยโครงสร้างส่วนหัวจะประกอบไปด้วย Metadataที่เป็นข้อมูลเพื่อใช้อธิบายข้อมูลอีกทีหนึ่ง และพอยน์เตอร์ที่อยู่ส่วนบนสุดของสแต็ก สำหรับส่วนข้อมูลจะประกอบด้วยข้อมูลพอยน์เตอร์ที่ใช้เชื่อมโยงไปยังโหนดถัดไปในสแต็ก พิจารณาจากรูปที่ 6 ที่แสดงถึงการสร้างสแต็กด้วยด้วยลิงก์ลิสต์ โดยรูปที่ 5 นั้นคือแนวความคิดของสแต็ก และเป็นรูปแบบของการสร้างสแต็กด้วยลิงก์ลิสต์ในเชิงกายภาพ

รูปที่ 5 การสร้างสแต็กด้วยลิงก์ลิสต์

การสร้างกองซ้อนด้วยแถวลำดับ

เป็นการเตรียมเนื้อที่ในหน่วยความจำไว้สำหรับเก็บข้อมูล

ตัวอย่างในภาษาซี คือ

int Stack[4];

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

การแสดงข้อมูลที่อยู่ในกองซ้อนด้วยแถวลำดับ

จะเป็นการดึงข้อมูลตั้งแต่ตำแหน่งแรกจนถึงตำแหน่งที่ Top ชี้อยู่ออกมาแสดงหรือจะกลับกันคือ นำข้อมูลจากตำแหน่ง Top ชี้อยู่จนถึงตำแหน่งที่ 0 ออกมาแสดง

การสร้าง stack ด้วย Link List

หมายถึง การแทนที่ข้อมูลของ stack ด้วย Link list ซึ่งเป็นการจัดสรรเนื้อที่หน่วยความจำแบบ Dynamic นั่นคือ หน่วยความจำจะถูกจัดสรรเมื่อมีการของใช้จริงๆ ระหว่างการประมวลผลโปรแกรมผ่านตัวแปรชนิด Pointer

เป็นการแทนที่ที่มีความยืดหยุ่นมาก เนื่องจากไม่ต้องกำหนดหรือจองหน่วยความจำล่วงหน้า ข้อมูลที่เก็บในกองซ้อนมีจำนวนเท่าใดก็ได้ การปฏิบัติการมี 4 ขั้นตอนคือ การสร้าง, การ Push, การ Pop และการแสดง

- การทดสอบว่า stack ว่างหรือไม่(EMPTY)

- การทดสอบว่า stack เต็มหรือไม่(FULL)

- การทำให้ stack เป็น stack ว่าง(CLEAR)

โพลิชโนเตชัน(Polish Notation)

เป็นวิธีการจัดรูปแบบของสมการใหม่ โดยการย้ายตำแหน่งของเครื่องหมายและตัวดำเนินการ เช่น 2*3 เขียนเป็น *23 เป็นต้น โดยมีรูปแบบการเขียนสมการ ดังนี้

Prefix : การเขียนสมการโดยให้เครื่องหมายอยู่หน้าตัวดำเนินการ
เช่น * + 5 3 2

Infix : การเขียนสมการโดยให้เครื่องหมายอยู่ระหว่างตัวดำเนินการ
เช่น (5+3)*2

Postfix : การเขียนสมการโดยให้เครื่องหมายอยู่หลังตัวดำเนินการ
เช่น 5 3 + 2 *

Algorithm การคำนวณแบบ Postfix

ให้อ่านข้อมูลจากซ้ายไปขวาทีละตัว ถ้าพบตัวถูกดำเนินการ(ตัวเลข) ให้ push stack ถ้าพบตัวดำเนินการ(เครื่องหมาย) ให้ pop item บนสุดของ stack 2 ตัว แล้วทำการคำนวณตามเครื่องหมายที่พบ แล้วนำผลลัพธ์ที่ได้ push stack ทำซ้ำจนกระทั่งหมดข้อมูล

- Algorithm การคำนวณแบบ Postfix

วิธีการเปลี่ยน Infix เป็น Postfix

Algorithm การเปลี่ยน Infix เป็น Postfix

ให้ EXP เป็นสมการคณิตศาสตร์ที่เป็น Infix และ Stack เป็น stack ใด ๆ NEXP เป็นสมการที่เป็น Postfix

1. ใส่ “(“ เข้าไปใน Stack

2. อ่าน EXP จากซ้ายไปขวา

2.1 ถ้าพบตัวถูกดำเนินการ(ตัวเลข) ให้ใส่เข้าไปใน NEXP

2.2 ถ้าพบ “(“ ให้ push ใส่ stack

2.3 ถ้าพบตัวดำเนินการ(เครื่องหมาย) ให้ทำดังนี้

- ให้ pop ตัวดำเนินการ ทุกตัวที่มีลำดับความสำคัญกว่าตัวดำเนินการที่พบใน 2.3 ออกมาใส่ใน NEXP ให้หมด

- นำตัวดำเนินการที่พบใน 2.3 push เข้าใน stack แทนที่

2.4 ถ้าพบ “)” ให้ทำดังนี้