DTS07-05-08-2552

สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง Queue

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

การทำงานของคิว
1.การใส่ข้อมูลตัวใหม่ลงในคิว เรียกว่า Enqueue ก่อนที่จะใส่ข้อมูลลงไปต้องตรวจสอบก่อนว่าคิวเต็มหรือไม่ ถ้าพยายามใส่ข้อมูลลงไปอาจเกิดข้อผิดพลาด ที่เรียกว่า overflow
2.การนำสมาชิกออกจากคิว เรียกว่า Dequeue จะไม่สามารถนำข้อมูลออกจากคิวที่ว่างได้ ถ้าพยายามนำข้อมูลออกอาจเกิดข้อผิดพลาดที่เรียกว่า underflow
3.การนำข้อมูลที่อยู่ตอนต้นของคิวหรือข้อมูลที่อยู่ลำดับแรกมาแสดง เรียกว่า Queue Front เพื่อรู้ว่าข้อมูลตัวต่อไปคืออะไร
4.การนำข้อมูลที่อยู่ตอนท้ายของคิว หรือข้อมูลที่เข้ามาตัวสุดท้ายมาแสดง เรียกว่า Queue Rear เพื่อรู้ว่า
ข้อมูลตัวสุดท้ายคืออะไร
การแทนที่ข้อมูลของคิว มี 2 วิธี คือ
1.การแทนที่ข้อมูลของคิวแบบอะเรย์ มีการกำหนดขนาดของคิวไว้ล่วงหน้าว่ามีขนาดเท่าไร และจะมีการจัดสรรเนื้อที่หน่วยความจำให้เลย เมื่อพื้นที่ของอะเรย์มีพื้นที่ว่าง อาจหมายความว่า พื้นที่ว่างนั้นเคยเก็บข้อมูลแล้วกับพื้นที่ว่างนั้นยังไม่เคยเก็บข้อมูลมาก่อน
*** กรณีที่ Front ไม่ได้อยู่ช่องแรก พื้นที่ว่างจะไม่สามารถใช้งานได้อีก จะแก้โดยใช้คิวแบบวงกลม คือ ช่องสุดท้ายต่อกับช่องแรก คิวแบบวงกลมจะเต็มก็ต่อเมื่อ rear มีค่าน้อยกว่า front
2.การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์ ประกอบไปด้วย 2 ส่วน คือ Head Node มี 3 ส่วนมีพอยเตอร์ 2 ตัว และจำนวนสมาชิก กับ Data Node จะมีข้อมูล และพอยเตอร์ชี้ตัวถัดไป

การดำเนินการเกี่ยวกับคิว
1.Create Queue คือการสร้างคิวขึ้นมา แล้วจัดสรรหน่วยความจำให้กับ Head Node และพอยเตอร์มีค่าเป็น Null
2.Enqueue คือ การเพิ่มข้อมูลลงไปในคิวโดยการเพิ่มจะเพิ่มจากส่วนท้าย
3.Dequeue คือ การนำข้อมูลในคิวออก จะออกโดยข้อมูลที่เข้าไปตัวแรกจะออกก่อน
4.Queue Front คือ การนำข้อมูลตัวแรกที่เข้าไปในคิวออกมาแสดง
5.Queue Rear คือ การนำข้อมูลตัวสุดท้ายที่เข้ามาในคิวออกมาแสดง
6.Empty Queue คือ เป็นการตรวจสอบว่าคิวนั้นยังคงว่างอยู่หรือไม่
7.Full Queue คือ เป็นการตรวจสอบว่าคิวนั้นเต็มหรือไม่
8.Queue Count คือ เป็นการนับจำนวนข้อมูลที่อยูในคิว ว่ามีจำนวนเท่าไร
9.Destroy Queue คือ การลบข้อมูลที่อยูในคิวทิ้ง

การประยุกต์ใช้คิว จะถูกประยุกต์ใช้มากในระบบธุรกิจ เช่นการให้บริการลูกค้า คือลูกค้าที่มาก่อนย่อมต้องได้รับบริการก่อน และในด้านคอมพิวเตอร์ในระบบปฏิบัติงาน (Operating System) คือจัดให้งานที่เข้ามา ได้ทำงานตามความสำคัญ (Priority)
***เช่น สมมติว่า Priority มีงาน 3 ระดับ เรียงจากมากไปหาน้อยระบุโดยตัวเลข เลข 1 มากสุดเรื่อยไปจนถึง 3 น้อยสุด ถ้ามีงาน A,B,C เข้ามาขอใช้ CPU โดยมี Priority เป็น 4,2,1, ตามลำดับ ที่นี้งาน C จะถูกนำไปทำงานก่อน ตามด้วย B และ A

DTS06-30-07-2552

สรุปเนื้อหาบทเรียน "Data Structure"

เรื่อง Stack (ต่อ)

สแตก มี 2 วิธี คือ

การแทนที่ข้อมูลของสแตกด้วยอาร์เรย์
การแทนสแตกด้วยโครงสร้างอาร์เรย์นั้น เนื่องจากอาร์เรย์เป็นโครงสร้างที่ต้องมีการกำหนดจองพื้นที่เท่ากับขนาดที่ใหญ่ที่สุด(static) จึงจำเป็นต้องมีการกำหนดขนาดพื้นที่จัดเก็บข้อมูลสูงสุดให้เหมาะสมเมื่อมีการนำเอาข้อมูลเข้ามาก็จะนำเข้ามาจัดไว้ในอาร์เรย์แรกสุดจากนั้นจึงเรียงลำดับกันไปตามพื้นที่ที่กำหนด

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

การดำเนินงานเกี่ยวกับสแตก
1.Create Stack เป็นการสร้างสแตกขึ้นมาแล้วกำหนดค่าเริ่มต้นต่าง ๆ
2.Push Stack เป็นการนำข้อมูลมาใส่ลงในสแตก
3.Pop stack เป็นการนำข้อมูลที่อยู่บนสุดออกจากสแตก
4.Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตกแต่ ไม่มีการลบข้อมูลที่คัดลอกออกจากสแตก
5.Empty Stack เป็นการตรวจสอบว่าสแตกว่างหรือไม่ เพื่อไม่ให้เกิดข้อผิดพลาดที่เรียกว่า stack underflow
6.Full Stack เป็นการตรวจสอบว่าสแตกนั้นเต็มหรือไม่ เพื่อไม่ให้เกิดข้อผิดพลาดที่เรียกว่า stack overflow
7.Stack Count เป็นการนับข้อมูลในสแตกว่ามีจำนวนเท่าไหร่
8.Destroy Stack เป็นการลบข้อมูลในสแตกออกทั้งหมด

การคำนวณนิพจน์ทางคณิตศาสตร์ แบ่งเป็น 3 ประเภทคือ
1. นิพจน์ Infix คือ นิพจน์ที่มีเครื่องหมายดำเนินการ(operator)อยู่กึ่งกลางตัวถูกดำเนินการ (operand) เช่น A + B
2. นิพจน์ Postfix คือ นิพจน์ที่มีเครื่องหมายดำเนิน(operator)การอยู่ด้านหลังตัวถูกดำเนินการ (operand) เช่น AB+
3. นิพจน์ Prefix คือ นิพจน์ที่มีเครื่องหมายดำเนินการ(operator)อยู่ด้านหน้าตัวถูกดำเนินการ (operand) เช่น -AB

*** เครื่องหมายดำเนินการ (operand) ได้แก่เครื่องหมาย + - * ^ ตัวถูกดำเนินการ ได้แก่ สัญลักษณ์แทนค่าตัวเลข เช่น A B C D
หรือตัวแปรอื่น

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

ลำดับความสำคัญของตัวดำเนินการ
+ -
* /
(
)

ขั้นตอนการแปลง infix เป็น postfix
1.อ่านอักขระใน infix
2.ถ้าเป็น operand ย้ายไปใส่ใน postfix
3.ถ้าเป็น operator จะต้องดูลำดับความสำคัญของตัวดำเนินการด้วยแล้วใส่ลงในสแตกที่เก็บตัวดำเนินการ ถ้ามีค่ามากกว่าให้ push ถ้ามีค่าน้อยกว่าหรือเท่ากันให้ pop ออกแล้วไปเรียงต่อตัวอักษรใน postfix
4.ตัวดำเนินการที่เป็น ) จะไม่ถูก push แต่จะทำให้ตัวดำเนินการตัวอื่นถูก pop ออกมาแล้วไปเรียงต่อใน postfix
5.เมื่ออ่านอักขระใน infix หมด ให้ pop ตัวดำเนินการทุกตัวมาเรียงต่อใน postfix
*** ถ้าเจอเครื่องหมาย + - หลังเครื่องหมาย * / ให้ pop เครื่องหมายในสแตกออก
ถ้าเจอเครื่องหมาย * / หลังเครื่องหมาย + - ให้ push ลงในสแตก

การคำนวณค่า postfix
1.อ่านตัวอักษรจาก postfix ที่ละตัว
2.ถ้าเป็น operand ให้ push ไปเรื่อยๆ
3.ถ้าเป็น operator ให้ pop ตัวอักษรออก 2 ตัว แล้วทำการคำนวณตัวที่ถูก pop ที่หลังจะเป็นตัวตั้งแล้วนำ push ผลลัพธ์ลงไป