Google    Youtube      Psv     สพม.11

          หน่วยที่5โครงสร้างข้อมูลคิว

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

วัตถุประสงค์เชิงพฤติกรรม(Behavioral Objectives)

หลังจอกศึกษาจบบทเรียนนี้แล้ว นักศึกษาจะมีความสามารถดังนี้

(After studying this chapter, you will be able to)

1.ศึกษาการปฏิบัติการของคิว

2.แสดงตัวอย่างคิววงกลม

3.ยกตัวอย่างคิวลำดับความสำคัญ

4.แสดงตัวอย่างการใช้คิวลำดับความสำคัญ

5.จัดบอร์ดเชิงปฏิบัติการ “โครงสร้างข้อมูลคิว”

6.สนทนาเชิงปฏิบัติการ “ตัวอย่างการใช้คิวลำดับความสำคัญ”

7.อธิบายคำศัพท์ได้ 8 คำ

คิว (Queue) เป็นโครงสร้างข้อมูลที่รู้จักและนำมาใช้งานมากเช่นเดียวกับสแตก (Stack) และมีลักษณะเป็นรายการในแนวเชิงเส้น (Linear List) เช่นกัน มีข้อกำหนดให้ชุดปฏิบัติการสามารถเพิ่มค่าเข้าไปในตอนท้ายของรายการเพียงด้านเดียว เรียกว่า ส่วนหลัง (Rear) และลบค่าในตอนต้นของรายการเพียงด้านเดียว เรียกว่าส่วนหน้า (Front) ซึ่งกำหนดคิวเป็นรูปแบบดังนี้

Q = [Q1, Q2, . . .  , QT]

โดย Front (Q) คือ Q1 และ Rear (Q) คือ QT มีจำนานสมาชิกในคิวเท่ากับ T ดังในรูปที่ 5.1 โดยลักษณะมีตัวชี้ส่วนหน้าอยู่ด้านซ้ายและตัวชี้ด้านท้ายอยู่ด้านขวา และอาจกลับด้านกันก็ได้ให้ตัวชี้ส่วนหน้าอยู่ด้านขวาและตัวชี้ส่วนท้ายอยู่ด้านซ้าย

Front                                                                                                 Rear

รูปที่ 5.1 ตัวอย่างลักษณะของคิวที่มีตัวชี้ส่วนหน้าอยู่ด้านซ้ายและตัวชี้ส่วนท้ายอยู่ด้านขวา

                สมาชิก Q1 จะเข้ามาก่อนสมาชิก QJ สำหรับ I < J   และ QI ซึ่งอยู่ในคิวนานที่สุดและถูกลบออกจากคิวก่อนสมาชิกที่เข้ามาหลัง

ลักษณะของคิวถูกนำมาใช้แก้ไขปัญหาต่างๆในแอปพลิเคชั่นต่างๆ เช่น จำลอง (Simulation) การทำงานของระบบจริงในกิจกรรมแบบเข้าก่อนออกก่อน เช่น การเข้าแถวเพื่อนซื้อของหรือชำระเงินเพื่อตรวจสอบการให้บริการเพียงพอหรือไม่ การนำคิวไปใช้ในการสำรวจพิจารณา(Observation) ตามปริมาณรถติดเพื่อควบคุมไฟจราจรตามทางแยก การนำหลักการของคิว (Queuing Theory) มาใช้ เช่น การส่งข้อมูลข่าวสารในเครือข่าย การส่งแฟ้มข้อมูลไปยังพริ้นเตอร์เพื่อพิมพ์งานตามลำดับคิว หรือรูปแบบการสลับตู้รถไฟบนราง ดังในรูปที่ 5.2

รูปที่ 5.2 ตัวอย่างการใช้คิวแก้ปัญหาการสลับตู้รถไฟบนราง

ปัญหาต่างๆเหล่านี้สามารถแก้ไขโดยใช้โครงสร้างคิวที่มีลักษณะการทำงานในรูปแบบที่เรียกว่าเข้าก่อนออกก่อน (First-In-First-Out, FIFO)หรือเข้ามาก่อนได้บริการก่อน (First-Come-First-Served, FCFS) เมื่อค่าใหม่เข้ามาก็จะไปต่อเป็นส่วนท้ายแทนค่าเดิมที่เก็บอยู่ส่วนท้ายก่อนหน้านี้ไปเรื่อยๆ ถ้าเป็นการดึงค่าออกจากคิวก็จะนำค่าแรกสุดที่อยู่ในคิวดึงออกมาให้ก่อนสมาชิกตัวถัดไปส่วนหน้าแทน

การปฏิบัติการของคิว

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

1.CreateQueue () ใช้สร้างคิวใหม่ขึ้นมาใช้งานและกำหนดค่าเริ่มต้นต่างๆ

2.Insert (value, queue) ใช้เพิ่มค่าใหม่เก็บลงในคิวที่ใช้งานอยู่ และขยับตำแหน่งใหม่ให้กับส่วนท้าย

3.Remove (queue) ใช้ดึงค่าออกจากคิวที่ใช้งานอยู่และส่งค่า value กลับมาให้และขยับไปยังตำแหน่งถัดไปให้เป็นส่วนหน้า

4. isEmpty(stack) ใช้ตรวจสอบว่าคิวที่ใช้งานอยู่ว่างหรือไม่ ถ้าไม่มีค่าเก็บไว้เลยจะส่งค่าจริงกลับมาให้

การนำคิวมาใช้งานเป็นไปตามลำดับดังในรูป (a) ถึง (g) มีการทำงานโดยใช้ชุดปฏิบัติการดังนี้

(a) เริ่มต้นสร้างคิว Qขึ้นมาทำงาน Create Queue (Q) ได้เป็นคิวว่างไม่มีสมาชิกโดยตัวชี้ส่วนหน้าและส่วนท้ายยังไม่มีค่า

(b) นำค่า A เข้ามาเก็บเป็นตัวแรกโดยใช้ Insert (A) ได้คิว Q = [A] ตัวชี้Front = A,

Rear =A

A

 

Front             Rear

(c) นำค่า B เก็บต่อโดยใช้ Insert (B) ได้คิว Q = [A,B] ตัวชี้ Front=A, Rear =B

B

 

A

 

Front                            Rear

(d) นำค่า C เก็บต่อโดยใช้ Insert (C) ได้คิว Q = [A, B, C] ตัวชี้ Front=A, Rear =C

C

 

B

 

A

 

Front                                     Rear

(e) ต้องการดึงค่าออกมาโดยใช้ Remove () ได้คิว Q = [ B, C] ตัวชี้ Front=B, Rear =C

C

 

B

 

Front                                     Rear

(f) นำค่า D, E เก็บต่อโดยใช้ Insert (D) และ Insert (E) ได้คิว Q = [B, C, D, E] ตัวชี้ Front=B,

B         C

 

C

 

D

 

E

 

Rear =E

Front                                                        Rear

(g) ดึงค่าออกมา 3 ค่า โดยใช้ Remove () 3 ครั้งและเก็บค่า F โดยใช้ Insert (F) ได้คิว Q = [ E, F] ตัวชี้ Front=E, Rear =F

F

 

E

 

Front                                 Rear

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

ในการสร้างคิวมาใช้งานโดยพื้นฐานจะใช้อาร์เรย์เก็บค่าสมาชิก มีตัวแปร Front และ Rear เป็นตัวชี้ตำแหน่งส่วนหน้าและส่วนท้ายคิว จึงเกิดความลำบากเมื่อการเก็บค่าเข้ามาจนถึงสมาชิกตัวสุดท้ายของอาร์เรย์ ทำให้เพิ่มค่าใหม่เข้ามาอีกไม่ได้ ถ้าหากมีการเพิ่มเข้ามาอีกจะเกิดลักษณะการล้นของข้อมูลในคิว (Queue Overflow) และเมื่อใดมีการดึงค่าในส่วนหน้าออกมาก็ทำให้พื้นที่ส่วนหน้าของอาร์เรย์เกิดว่างและใช้งานไม่ได้ ทำให้ต้องปรับปรุงโดยย้ายค่าที่มีอยู่ส่วนท้ายกลับไปไว้ส่วนหน้าของอาร์เรย์เพื่อนำพื้นที่ว่างกลับมาใช้งานได้ แต่เป็นค่าใช้จ่ายที่ต้องทำงานเพิ่มโดยเฉพาะคิวที่มีขนาดใหญ่ ดังในรูปที่ 5.3 เป็นตัวอย่างคิวที่ใช้อาร์เรย์ขนาดเท่ากับ 5 โดยเพิ่มค่า Insert(70),Insert(80) และ Insert(50) ตามลำดับในรูป (a) จากนั้นดึงออกมา 2 ค่าโดยใช้ Remove() 2 ครั้งได้เป็นรูป (b) และเพิ่มค่า Insert(90) Insert(60) ในรูป (c) เนื่องจากไม่สามารถเพิ่มค่าใหม่ได้อีกจึงต้องขยับค่าที่เก็บอยู่ไปทางซ้ายในรูป (d) พร้อมกับกำหนดค่าตำแหน่งใหม่ให้กับ ตัวแปร Front และ Rear

(a)

Front                                    Rear

(b)

Front          Rear

(c)

Front                                        Rear

(d)

Front                                        Rear

รูปที่ 5.3 เป็นตัวอย่างคิวที่ใช้อาร์เรย์ในการเก็บค่ากับปัญหาที่เกิดขึ้น

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s