DTS07-06-08-2552

สรุปสิ่งที่ได้จากการเรียน เรื่อง Queue

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

เรียกลักษณะการทำงานแบบนี้ว่า เข้าก่อนออกก่อน หรือ First In First Out (FIFO) มีข้อกำหนดให้ชุดปฏิบัติการสามารถเพิ่มค่าเข้าไปในตอนท้ายของรายการเพียง ด้านเดียว เรียกว่า ส่วนหลัง ( Rear ) และลบค่าในตอนต้นของรายการเพียงด้านเดียว เรียกว่า ส่วนหน้า ( Front )

การดำเนินการพื้นฐานของ Queue ได้แก่
- การนำข้อมูลเข้าสู่ Queue เรียกว่า enqueue
- การนำข้อมูลออกจาก Queue เรียกว่า dequeue
- การนำข้อมูลที่อยู่ตอนต้นของ Queue มาแสดง เรียกว่า queue front

- การนำข้อมูลที่อยู่ตอนท้ายของ Queue มาแสดง เรียกว่า queue rear

การนำข้อมูลเข้าสู่โครงสร้างคิว (enqueue)

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

"ขั้นตอนการนำข้อมูลเข้าสู่โครงสร้างคิว" มีดังนี้
1. เมื่อมีข้อมูลเข้าสู่คิว ให้ตรวจสอบว่าคิวเต็มหรือไม่ ถ้าคิวเต็มไม่ให้มีการรับข้อมูล
2. ถ้าคิวไม่เต็มให้เลื่อนตำแหน่งพอยน์เตอร์ R แล้วนำข้อมูลเข้าสู่คิว
3. ตรวจสอบเงื่อนไขว่าถ้าเป็นข้อมูลตัวแรกในคิว ให้เปลี่ยนพอยน์เตอร์ F ให้ชี้ค่าแรก

การนำข้อมูลออกจากโครงสร้างคิว (dequeue)
เป็นการลบ ข้อมูลออกจากโครงสร้างคิวทางด้านหน้า ของโครงสร้างคิว โดยมีพอยน์เตอร์ F เป็นพอยน์เตอร์ชี้บอกตำแหน่งที่ข้อมูลอยู่ เมื่อมีการลบข้อมูล ออกจากโครงสร้างคิวเรียบร้อยแล้ว พอยน์เตอร์ F จะเลื่อนตำแหน่ง ไปยังตำแหน่งถัดไป
ข้อควรคำนึงถึง คือ เมื่อคิวว่าง (Empty queue) หรือไม่มีข้อมูลเหลืออยู่ จะไม่สามารถนำข้อมูลออกจากคิวได้อีก ซึ่ง จะทำให้เกิดปัญหา “underflow” ขึ้น

"ขั้นตอนการนำข้อมูลออกจากโครงสร้างคิว" มีดังนี้
1. ตรวจสอบว่าเป็นคิวว่าง (Empty Queues) หรือไม่
2. ถ้าคิวไม่ว่างให้นำข้อข้อมูลออกจากคิว ณ ตำแหน่งที่ F ชี้อยู่ จากนั้นก็ทำการเลื่อนตำแหน่งพอยน์เตอร์ F ไปยังตำแหน่งถัดไป
3. ถ้ามีข้อมูลอยู่เพียงตัวเดียว ให้กำหนดให้พอยน์เตอร์ F และ R เป็นศูนย์ (0)

ตัวอย่างการนำข้อมูลออกจากคิว (dequeue)

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

การดำเนินการเกี่ยวกับคิว ได้แก่

1.) Create Queue เป็นการจัดสรรหน่วยความจำให้กับ Head Node และให้ค่า pointer ทั้ง 2 ตัวมีค่าป็น null และจำนวนสมาชิกเป็นศูนย์

2.) Enqueue เป็นการเพิ่มข้อมูลเข้าไปในคิว ซึ่ง pointer rear จะเปลี่ยน

3.) Dequeue เป็นการนำข้อมูลออกจากคิว ซึ่ง pointer front จะเปลี่ยน

4.) Queue Front เป็นการนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดง

5.) Queue Rear เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง

6.) Empty Queue เป็นการตรวจสอบว่าคิวว่างหรือไม่

7.) Full Queue เป็นการตรวจสอบว่าคิวเต็มหรือไม่

8.) Queue Count เป็นการนับจำนวนสมาชิกที่อยู่ในคิว

9.) Destroy Queue เป็นการลบข้อมูลทั้งหมดที่อยู่ในคิว วิธีการคือ ต้องทำการ Dequeue ทีละตัว แล้วจึงจะ Destroy

2. การแทนที่ข้อมูลของคิวแบบอะเรย์

จาก การดำเนินการกับโครงสร้างคิวจะเห็นได้ว่า โครงสร้างคิวยังไม่มีประสิทธิภาพเพียงใดนัก เนื่องจากเมื่อมีการเพิ่มข้อมูลจนเต็ม (Full Queue) และมีการลบข้อมูลออกจากโครงสร้างคิวแล้ว พอยน์เตอร์ F จะยังคงอยู่ที่ตำแหน่งเดิม ไม่สามารถเปลี่ยนไปที่ตำแหน่งเริ่มต้นใหม่ได้จนกว่าจะมีการลบข้อมูลออกจาก คิวหมดแล้ว (Empty Queue) จึงจะสามารถกำหนดพอยน์เตอร์ข้อมูล F และ R ให้กลับไปยังตำแหน่งเริ่มต้นใหม่ได้ ทำให้เสียพื้นที่ของโครงสร้างคิวในตำแหน่งที่พอยน์เตอร์ F ผ่านมา ไปเนื่องจากต้องรอให้ตำแหน่งของพอยน์เตอร์ F ไปยังตำแหน่งสุดท้ายก่อน (เมื่อคิวว่าง) จึงจะสามารถใช้พื้นที่ดังกล่าวได้

ในกรณีที่เป็นคิวแบบวงกลม คิวจะเต็มก็ต่อเมื่อมีการเพิ่มข้อมูลเข้าไปในคิวเรื่อยๆ จนกระทั่ง rear มีค่าน้อยกว่า front อยู่ 1 ค่า คือ rear = front - 1

DTS06-29-07-2552

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

การดำเนินการเกี่ยวกับสแตก
1. Create stack จัดสรรหน่วยความจำให้แก่ head node และส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
2. Push stack โดยทั่วไปจะกระทำที่ต้นลิสต์ซึ่งถือว่าเป็นตำแหน่งโหนดบนสุดของสแตกหรือเป็นตำแหน่งที่พุชโหนดเข้าไปในสแตกหลังสุด เมื่อมีการพุชโหนดใหม่ลงในสแตกก็จะต้องปรับค่าพอยน์เตอร์ของโหนดใหม่ชี้ไปที่โหนดบนสุดในขณะนั้น และถ้า top เป็นพอยน์เตอร์ชี้ที่ตำแหน่งโหนดบนสุดในสแตก ให้ทำการปรับพอยน์เตอร์ top ชี้ไปที่โหนดใหม่ที่ทำการพุชลงไปแทน
3. Pop stack โหนดแรกที่จะถูกพ็อปออกมาคือโหนดที่อยู่บนสุดหรือโหนดแรกของลิงค์ลิสต์นั่นเอง ก่อนที่จะทำการพ็อปโหนดต้องตรวจสอบก่อนว่าสแตกว่างหรือไม่ โดยตรวจสอบจากค่าพอยน์เตอร์ที่ชี้ตำแหน่งโหนดบนสุดของสแตก ถ้ามีค่าเป็นนัลแสดงว่า สแตกว่าง และถ้าสแตกไม่ว่างก็สามารถทำการพ็อปโหนดออกจากสแตกได้
4. Stack top เรียกใช้รายการข้อมูลที่อยู่บนสุดของ stack (เป็นการคัดลอกโดยไม่มีการลบข้อมูลออกจากสแตก)
5. Empty stack ตรวจสอบว่า stack ว่างเปล่าหรือไม่ ถ้าไม่มีข้อมูลสแตกเหลืออยู่ เราก็ไม่สามารถทำการ Pop สแตกได้ ในกรณีเช่นนี้เรียกว่า "สแตกว่าง" (Stack Underflow) โดยการตรวจสอบว่าสแตกว่างหรือไม่ เราจะตรวจสอบตัวชี้สแตกว่าเท่ากับ 0 หรือ null หรือไม่ ถ้าเท่ากับ 0 แสดงว่าสแตกว่าง จึงไม่สามารถดึงข้อมูลออกจากสแตกได้
6. Full stack ตรวจสอบว่า stack เต็มหรือไม่ ถ้าไม่มีที่ว่างเหลืออยู่ เราก็จะไม่สามารถทำการ Push สแตกได้ ในกรณีเช่นนี้เราเรียกว่า "สแตกเต็ม" (Stack Overflow) โดยการตรวจสอบว่าสแตกเต็มหรือไม่ เราจะใช้ตัวชี้สแตก (Stack pointer) มาเปรียบเทียบกับค่าสูงสุดของสแตก (Max stack) หากตัวชี้สแตกมีค่าเท่ากับค่าสูงสุดของสแตกแล้ว แสดงว่าไม่มีที่ว่างให้ข้อเก็บข้อมูลอีก
7. Stack count ส่งค่าจำนวนรายการในสแตก หรือเป็นการนับจำนวนสมาชิกในสแตก
8. Destroy stack คืนหน่วยความจำของทุก node ในสแตกให้ระบบ หรือเป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
การแทนที่ข้อมูลของสแตกแบบอะเรย์ เนื่องจากอาร์เรย์เป็นโครงสร้างที่ต้องมีการกำหนดจองพื้นที่แน่นอน (static) จึงจำเป็นต้องมีการกำหนดขนาดพื้นที่จัดเก็บข้อมูลสูงสุดให้เหมาะสมเมื่อมีการ นำเอาข้อมูลเข้ามาก็จะนำเข้ามาจัดไว้ในอาร์เรย์แรกสุดจากนั้นจึงเรียงลำดับกัน ไปตามพื้นที่ที่กำหนด

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

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

1. การทำงานของโปรแกรมที่มีโปรแกรมย่อย
การทำงานของโปแกรมหลักที่เรียกใช้โปรแกรมย่อย และในแต่ละโปรแกรมย่อยมีการเรียกใช้โปรแกรมย่อยต่อไปอีก ลักษณะของปฏิบัติการแบบนี้ โครงสร้างข้อมูลแบบสแตกสามารถช่วยทำงานได้ โดยที่แต่ละจุดของโปรแกรมที่เรียกใช้โปรแกรมย่อยจะเก็บเลขที่ของคำสั่งถัดไปที่เครื่องต้องกลับมาทำงานไว้ในสแตก หลังจากเสร็จสิ้นการทำงานในโปรแกรมย่อยนั้นแล้ว จะทำการ popค่าเลขที่คำสั่งออกมาจากสแตก เพื่อกลับไปทำงานที่คำสั่งต่อจากคำสั่งที่เรียกใช้โปรแกรมย่อยนั้น จนกระทั่งโหนดในสแตกว่าง
2. การคำนวณนิพจน์ทางคณิตศาสตร์การเขียนนิพจน์คณิตศาสตร์เพื่อการคำนวณจะต้องคำนึงถึงลำดับความสำคัญของเครื่องหมายสำหรับการคำนวณด้วย โดยทั่วไปนิพจน์คณิตศาสตร์สามารถเขียนได้ 3 รูปแบบดังนี้
1. นิพจน์อินฟิกซ์ (infix expression) การเขียนนิพจน์ด้วยรูปแบบนี้ ตัวดำเนินการ (operator) อยู่ตรงกลางระหว่างตัวถูกดำเนินการ (operand) 2 ตัว
2. นิพจน์โพสฟิกซ์ (postfix expression) เป็นการเขียนนิพจน์ที่จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และตัวถูกดำเนินการตัวที่ 2 ก่อน ตามด้วยตัวดำเนินการ
3. นิพจน์พรีฟิกซ์ (prefix expression) เป็นการเขียนนิพจน์ที่จะต้องเขียนตัวดำเนินการก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และตัวถูกดำเนินการตัวที่ 2 ตามลำดับ