DTS 07-05/08/2552

Queue

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

การทำงานของคิว
การใส่สมาชิกตัวใหม่ลงในคิว
เรียกว่า Enqueue ซึ่งมีรูปแบบคือ
enqueue (queue, newElement)
หมายถึง การใส่ข้อมูล
newElement ลงไปที่ส่วนเรียร์
การนำสมาชิกออกจากคิว เรียกว่า
Dequeue ซึ่งมีรูปแบบคือ
dequeue (queue, element)
หมายถึง การนำออกจากส่วนหน้า
ของคิวและให้ ข้อมูลนั้นกับ element
การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดงจะ
เรียกว่า Queue Front
แต่จะไม่ทำการเอาข้อมูลออกจากคิว

การนำข้อมูลที่อยู่ตอนท้าย
ของคิวมาแสดงจะ เรียกว่า
Queue Rear แต่จะไม่ทำ
การเพิ่มข้อมูลเข้าไปในคิว

การแทนที่ข้อมูลของคิว
สามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของคิวแบบอะเรย์

การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
จะประกอบไปด้วย 2 ส่วน คือ
1. Head Node
จะประกอบไปด้วย 3 ส่วนคือ
พอยเตอร์จำนวน 2 ตัว คือ Front และ rear
กับจำนวนสมาชิกในคิว
2. Data Node จะประกอบไปด้วย
ข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป

การดำเนินการเกี่ยวกับคิว ได้แก่
1. Create Queue 6. Empty Queue
2. Enqueue 7. Full Queue
3. Dequeue 8. Queue Count
4. Queue Front 9. Destroy Queue
5. Queue Rear

การประยุกต์ใช้คิว
คิวถูกประยุกต์ใช้มากในการจำลองระบบงาน
ธุรกิจ เช่น การให้บริการลูกค้า ต้องวิเคราะห์จำนวน
ลูกค้าในคิวที่เหมาะสม
ว่าควรเป็นจำนวนเท่าใด เพื่อให้ลูกค้าเสียเวลาน้อย
ที่สุด ในด้านคอมพิวเตอร์ ได้นำคิวเข้ามาใช้ คือ
ในระบบปฏิบัติการ (Operation System) ในเรื่อง
ของคิวของงานที่เข้ามาทำงาน (ขอใช้ทรัพยากร
ระบบของ CPU) จะจัดให้งานที่เข้ามาได้ทำงาน

DTS-06-29/07/2552

5.Empty Stack

เป็นการตรวจสอบการว่างของ
สแตก เพื่อไม่ให้เกิดความผิดพลาด
ในการนำข้อมูลออกจากสแตกที่
เรียกว่า Stack Underflow

6. Full Stack
เป็นการตรวจสอบว่าสแตกเต็ม
หรือไม่ เพื่อไม่ให้เกิดความ
ผิดพลาดในการนำข้อมูลเข้าสแตกที่
เรียกว่า Stack Overflow

7. Stack Count
เป็นการนับจำนวนสมาชิกในสแตก

8. Destroy Stack
เป็นการลบข้อมูลทั้งหมดที่อยู่ใน
สแตก

การดำเนินการเกี่ยวกับสแตก
การดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack 5. Empty Stack
2. Push Stack 6. Full Stack
3. Pop Stack 7. Stack Count
4. Stack Top 8. Destroy Stack

การประยุกต์ใช้สแตก
การประยุกต์ใช้สแตก จะใช้ในงานด้าน
ปฏิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการ
ทำงานต้องการเก็บข่าวสารอันดับแรกสุดไว้ใช้
หลังสุด เช่น การทำงานของโปรแกรม
แปลภาษานำไปใช้ในเรื่องของการโปรแกรมที่
เรียกใช้โปรแกรมย่อย การคำนวณนิพจน์ทาง
คณิตศาสตร์ และรีเคอร์ชั่น (Recursion)
การทำงานของโปรแกรมหลักที่เรียกใช้โปรแกรมย่อย
และในแต่ละโปรแกรมย่อยก็มีการเรียกใช้โปรแกรมย่อย
ต่อไปอีก สแตกจะสามารถเข้ามาช่วยในการทำงาน คือ
แต่ละจุดของโปรแกรมที่เรียกใช้โปรแกรมย่อยจะเก็บ
เลขที่ของคำสั่งถัดไปที่เครื่องต้องกลับมาทำงานไว้ใน
สแตก หลังจากเสร็จสิ้นการทำงานในโปรแกรมย่อยแล้ว
จะทำการ pop ค่าเลขที่คำสั่งออกมาจากสแตก เพื่อกลับไป
ทำงานที่คำสั่งต่อจากคำสั่งที่เรียกใช้โปรแกรมย่อย

ตัวอย่างนิพจน์คณิตศาสตร์ในรูปแบบต่าง ๆ
นิพจน์ Infix นิพจน์ Postfix นิพจน์ Prefix
A+B-C AB+C- - +ABC
A+B*C-D/E ABC*+DE/- - +A*BC/DE
A*B+C-D/E AB*C+DE/- - +*ABC/DE

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

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

ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์
Postfix
1. อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็น
ตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับ
ความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบ
กับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่
บนสุดของสแตก
- ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัว
ดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรใน
นิพจน์ Postfix
4. ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตก
แต่มีผลให้ตัวดำเนินการอื่น ๆ ถูก pop ออกจากสแตก
นำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ pop
วงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ