Stack and Queue Algorithm

Introduction: โครงสร้างข้อมูลแบบสแตก (Stack) เป็นโครงสร้างข้อมูลที่ใช้เป็นประโยชน์ในการอินเตอร์รัพต์ การกระโดดไปมาระหว่างโปรแกรมย่อย การเขียนโปรแกรมแบบเรียกใช้ตัวเอง (recursive) นอกจากนั้นแล้วโครงสร้างข้อมูลชนิดนี้มักจะใช้ช่วยในการเข้าไปในโครงสร้างแบบพิเศษ เช่น เครือข่าย หรือต้นไม้ โดยจะช่วยในการจำเส้นทาง และงานที่เรานำโครงสร้างแบบสแตกแล้วเราพบเห็นบ่อยๆ คือ การยกเลิกคำสั่ง (Undo) ในไมโครซอฟท์เวิร์ด สแตกเป็นโครงสร้างแบบเชิงเส้น ที่มีลักษณะที่ว่า การนำข้อมูลเข้าสู่สแตก (insertion) และการนำข้อมูลออกจากสแตก (deletion) สามารถจะทำได้ที่ปลายด้านหนึ่งของลิสท์ที่แทนสแตกเท่านั้น ดังนั้นอันดับของการนำสมาชิกเข้าและออกจากสแตกมีความสำคัญ คือ สมาชิกที่เข้าไปอยู่ในสแตกก่อนจะออกจากสแตกหลังสมาชิกที่เข้าไปใน สแตกทีหลัง นั่นคือ การเข้าทีหลังออกก่อน จึงเรียกลักษณะแบบนี้ว่า LIFO (Last In First Out) สแตกประกอบด้วยส่วนสำคัญ ๆ 2 ส่วน คือ 1. ตัวชี้สแตก หรือ Stack Pointer 2. ส่วนสมาชิกของสแตก หรือจะเรียกอีกอย่างว่า Stack Element โครงสร้างข้อมูลแบบสแตก (Queue) คิวเป็นโครงสร้างข้อมูลแบบหนึ่งซึ่งมีลักษณะที่ว่า ข้อมูลที่นำเข้าไปเก็บก่อนจะถูกนำออกมาทำงานก่อน ส่วนข้อมูลที่เข้าไปเก็บทีหลังก็จะถูกนำออกมาใช้งานทีหลัง ขึ้นอยู่กับลำดับการเก็บข้อมูล จะเรียกลักษณะการทำงานแบบนี้ว่า เข้าก่อนออกก่อน หรือ First In First Out (FIFO) เป็นโครงสร้างที่สามารถแทนด้วยอาร์เรย์ และจะต้องมีตัวชี้อีก 2 ตัว ได้แก่ ตัวชี้ F (Front Pointer) ชี้ไปที่สมาชิกตัวแรก และตัวชี้ R (Rear Pointer) ชี้ไปที่สมาชิกตัวสุดท้ายของคิว โดยที่เวลาข้อมูลจะเข้าสู่คิวจะเข้าทาง R ส่วนเวลาที่ข้อมูลจะออกจากคิวจะออกทาง F

Task: 1.ให้ค้นหาความหมาย รายละเอียด กระบวนการทำงานของข้อมูล แล้วทำรายงานกลุ่ม 2 เรื่อง คือ Stack และ Queue - ส่วนประกอบทั้ง 2 แบบ - การสร้างโครงสร้างข้อมูลทั้ง 2 แบบ - การดำเนินงานและ แบบ Algorithmทั้ง 2 แบบ - การประยุกต์การใช้งาน ทั้ง 2 แบบ - ตัวอย่าง Source Code พร้อมทั้งอธิบายประกอบความเข้าใจอย่างละเอียด ทั้ง 2 แบบ 2.ทำการสอบวัดผลทั้ง 2 แบบ

Process: - ค้นหาแหล่งข้อมูลจาก Internet - ค้นคว้าจากหนังสือตำราต่างๆ ในห้องสมุด - ดำเนินการประชุมกลุ่ม และให้สมาชิกแต่ละคนนำเสนอความคิดในกลุ่ม และสรุปรวมความคิดทั้งหมดให้เป็นหนึ่งเดียว - ดำเนินการสรุปความคิดนั้นและจัดทำเอกสารเอกสารเป็นรูปเล่มให้เรียบร้อยและนำส่งในห้องเรียน และให้ส่งไฟล์ไปยัง e-mail ของผู้สอนล่วงหน้า

Resources รายชื่อหนังสือประกอบการค้นคว้า 1. ขนิษฐา นามี (๒๕๔๘). โครงสร้างข้อมูลและอัลกอริธึม. นนทบุรี : ไอดีซีฯ. 2. เนรมิต ชุมสาย ณ อยุธยา (๒๕๔๙). เรียนรู้โครงสร้างข้อมูลและอัลกอริธึมด้วย Java. กรุงเทพฯ : ซีเอ็ด ยูเคชั่น. 3. จินดา ยาปนเวช (๒๕๔๕). คู่มือเรียนภาษา Pascal. กรุงเทพฯ : โปรวิชั่น. 4. วรเศรษฐ สุวรรณิก (๒๕๔๙). เขียนโปรแกรม Java เบื้องต้น. กรุงเทพฯ : ซีเอ็ดยูเคชั่น. 5. Clifford A. Shaffer. (2001). A Practical Introduction to Data Structures and Algorithm Analysis, New Jersey : Prentice-Hall. Internet http://e-learning.mfu.ac.th/mflu/1302251/index.html http://course.eau.ac.th/course/Download/0092021/Chapter1_New.pdf และสื่อด้านอื่นๆ

Evaluation: เกณฑ์การประเมิน (แบ่งเป็น 3 ระดับ ระดับต่ำ กลาง และสูง) แยกประเมินผลตามกระบวนการ ในขั้นภาระงาน (task) (ต่ำ)ทำได้ไม่ถึงร้อยละ70 ของหัวข้อทั้งหมด (กลาง)ทำได้ไม่ถึงร้อยละ80 ของหัวข้อทั้งหมด (สูง)ทำได้มากกว่าร้อยละ80ของหัวข้อทั้งหมด ในขั้นกระบวนการ (process) (ต่ำ)สามารถสรุปได้น้อยกว่า5หน้า (กลาง)สามารถสรุปได้มากกว่า5หน้าแต่น้อยกว่า8หน้า (สูง)สามารถสรุปได้มากกว่า8หน้า ในขั้นการประเมินผล (evaluation) (ต่ำ)สอบได้ร้อยละ50ขึ้นไป (กลาง)สอบได้ร้อยละ70ขึ้นไป (สูง)สอบได้ร้อยละ90ขึ้นไป ในขั้นการสรุป (conclusion) (ต่ำ)ผู้เรียนไม่ได้ร่วมสรุป (กลาง)ผู้เรียนร่วมสรุป (สูง)ผู้เรียนสรุป

Conclusion: จากการศึกษาตามกระบวนการศึกษา นักศึกษาจะทราบถึงลักษณะการทำงานของ Stack และ Queue พร้อมทั้งเรียนรู้ถึงส่วนประกอบที่จำเป็น การดำเนินการสร้าง algorithm ของการสร้าง เติม ลบข้อมูล กระบวนการดำเนินงาน และนำไปสู่การประยุกต์การใช้งานโครงสร้างข้อมูลทั้ง 2 แบบ ในการดำเนินงานจริง สามารถอธิบายได้ถึงขั้นตอนและกระบวนการ โดยการนำเสนอผ่านการเขียนโปรแกรม และ Algorithm