วันพุธที่ 26 สิงหาคม พ.ศ. 2552

DTS 07-05-08-2552

สรุป เรื่อง Queue

โครงสร้างข้อมูลของ Queue

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

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

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

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

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

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

--การนำข้อมูลเข้าสู่คิว จะไม่นำเข้าในขณะที่คิวเต็มหรือไม่มีที่ว่าง
ถ้าพยายามนำข้อมูลเข้าจะเกิดการผิดพลาดที่เรียกว่า overflow


--การนำข้อมูลออกจากคิว จะไม่สามารถนำอะไรออกจากคิวที่ว่างได้
ถ้าพยายามจะเอาออกจะเกิดการผิดพลาดที่เรียกว่า underflow


--จุดเด่นของคิว

คิวสามารถจัดการการเข้า-ออกของข้อมูล

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



วันจันทร์ที่ 3 สิงหาคม พ.ศ. 2552

DTS 06-29-07-2552

สรุป stack (ต่อ)

การแทนที่ข้อมูลของสแตกแบบอะเรย์

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


หลักการดำเนินการสำหรับแปลง infix เป็น postfix

1.พิจารณานิพจน์ infix หากเป็น operand ให้นำออกไปที่ผลลัพธ์
2.พิจารณานิพจน์ infix หากเป็น operator ให้นำมาเปรียบเทียบ
ความสำคัญ หากสแตกว่างไม่มีตัวดำเนินการใ้ห้ push ลงสแตก
ถ้ามีตัวดำเนินการอยู่ให้เปรียบเที่ยบความสำคัญ ถ้าตัวดำเนินการ
ที่เข้าไปใหม่มีความสำคัญน้อยกว่าให้ pop ตัวดำเนินการก่อนหน้า
ไปไว้ในผลลัพธ์แต่ถ้ามีความสำคัญมากกว่าก็ให้วางต่อไว้ในสแตก


สำหรับเครื่องหมาย +-*/ เรียกว่า operator
สำหรับตัวอักษร ABCD เรียกว่า operand