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

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

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

 

 

 

 

 

 

          สมาชิก Q1 จะเข้ามาก่อนสมาชิก QJ สำหรับ I < J และ QI ซึ่งอยู่ในคิวนานที่สุดและถูกลบออกจากคิวก่อนสมาชิก
ที่เข้ามาหลัง
          ลักษณะของคิวถูกนำมาใช้แก้ไขปัญหาต่างๆในแอปพลิเคชั่นต่างๆ เช่น จำลอง (Simulation) การทำงานของระบบจริงในกิจกรรมแบบเข้าก่อนออกก่อน เช่น การเข้าแถวเพื่อนซื้อของหรือชำระเงินเพื่อตรวจสอบการให้บริการเพียงพอหรือไม่ การนำคิวไปใช้ในการสำรวจพิจารณา (Observation) ตามปริมาณรถติดเพื่อควบคุมไฟจราจรตามทางแยก การนำหลักการของคิว (Queuing Theory) มาใช้ เช่น การส่งข้อมูลข่าวสารในเครือข่าย การส่งแฟ้มข้อมูลไปยังพริ้นเตอร์เพื่อพิมพ์งานตามลำดับคิว หรือรูปแบบการสลับตู้รถไฟบนราง ดังในรูปที่ 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

 

 

 

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

 

 

 

 

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

 

 

 

 

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

 

 

 

 

 

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

 

 

 

 

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

 

 

 

         การทำงานของคิวเมื่อมีค่าใดส่งเข้ามาเก็บเป็นตัวแรกก็จะอยู่ส่วนหน้า ค่าถัดมาก็จะต่อท้ายไปเรื่อยๆ จนตัวสุดท้ายคือส่วนหลัง หากมีการดึงค่าออกมาใช้ ค่าที่อยู่ส่วนหน้าจะถูกดึงออกมาก่อน ลักษณะที่ได้จึงเป็นลำดับการใช้งานทั่วไปและเรียกว่าเข้าก่อนออกก่อน
         ในการสร้างคิวมาใช้งานโดยพื้นฐานจะใช้อาร์เรย์เก็บค่าสมาชิก มีตัวแปร 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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

คิววงกลม

          แทนที่จะใช้คิวเป็นเชิงเส้นแบบแนวตรงดังที่ผ่านมา ก็มาใช้เป็นคิววงกลม (Circular Queue) ในลักษณะของเส้นรูปวงแหวนเพื่อแก้ไขปัญหาดังกล่าว โดยสมมุติให้อาร์เรย์เป็นวงกลมที่สมาชิกตัวแรกต่อจากสมาชิกตัวสุดท้าย เมื่อเก็บค่าถึงสมาชิกตัวสุดท้ายก็จะเก็บวนต่อไปยังสมาชิกตัวแรก ดังนั้น ในการเพิ่มค่าให้กับ Front และ Rear จะอยู่ในขอบเขตขนาดของอาร์เรย์และให้สมาชิกที่เข้ามาต่อจากตำแหน่งสุดท้ายของอาร์เรย์วนกลับไปยังตำแหน่งแรกโดยการหารเหลือเศษ (Modulo) ด้วย maxSize ดังในรูปที่ 5.4 เป็นตัวอย่างจากรูปที่ 5.3 ที่เปลี่ยนเป็นคิววงกลม ทำให้เพิ่มค่าต่อไปได้และไม่ต้องขยับถอยกลับมา

 

 

 

 

 

 

 

 

 

 

 

         สิ่งที่ต้องพิจารณาเมื่อคิวว่างเปล่าสามารถทราบได้จาก Front กับ Rear มีค่าเท่ากัน เช่น เดียวกันเมื่อคิวเต็ม Rear จะวนกลับมาจนมีค่าเท่ากับ Front ทำให้เกิดความสับสนได้ว่าเมื่อ Front และ Rear มีค่าเท่ากันจะเป็นสถานะของคิวว่างหรือคิวเต็ม อย่างไรก็ตามก็สามารถหลีกเลี่ยงปัญหานี้ได้โดยให้สมาชิกที่อยู่ก่อนหน้าสมาชิกในตำแหน่ง Front เป็นตำแหน่งช่องว่างเสมอซึ่งทำให้ทราบว่าคิวเต็มก็ต่อเมื่อ (Rear+1) % maxSize = Front ดังใน รูปที่ 5.5 อย่างไรตามทำให้จำนวนสมาชิกที่เก็บค่าได้เหลือเพียง maxSize -1

 

 

 

 

 

 

 

 

          ดังนั้น ชุดปฏิบัติการของคิววงกลมจึงมีการปรับปรุงการทำงานได้เป็นอัลกอริทึมดังในตารางที่ 5.1 สำหรับการเพิ่มค่าลงในคิวด้วย Insert และตารางที่ 5.2 สำหรับการดึงค่าออกจากคิวด้วย Remove ในการตรวจสอบคิวว่างยังคงใช้ isEmpty เหมือนเดิมเมื่อคิวว่างก็ต่อเมื่อค่าของ Front และ Rear เท่ากัน

     

 

 

 

 

 

 

 

 

 

 

 

 

 

คิวลำดับความสำคัญ

         คิวอาจมีการจัดลำดับความสำคัญของสมาชิกจึงมีการสร้างเป็นคิวลำดับความสำคัญ (Priority Queue) เช่น ในระบบปฏิบัติการจะให้โปรเซสที่มีความสำคัญที่สุดทำงานก่อน แต่เนื่องจากโปรเซสที่เข้ามาไม่ได้เรียงตามความสำคัญ ซึ่งการจัดลำดับมี 2 แบบ คือ ให้ความสำคัญ จากค่าน้อยไปหาค่ามาก (Ascending) และจากค่ามากไปหาค่าน้อย (Descending) โดยส่วนใหญ่ใช้ค่ามากมีความสำคัญมากกว่า ในการเพิ่มสมาชิกเข้ามาในคิวไม่จำเป็นต้องเข้ามาตามลำดับความสำคัญอาจสลับไปมาได้ แต่การนำออกมาจากคิวจะต้องตามลำดับความสำคัญ ดังนั้น ในการลบสมาชิกออกจากคิวจึงต้องมีการทำงาน 2 เรื่อง คือ ต้องหาสมาชิกที่มีความสำคัญมากที่สุด ทำให้ต้องเข้าไปเรียกใช้งานสมาชิกทุกตัว และเมื่อลบสมาชิกออกจากคิวในช่วงกลางจะต้องทำการขยับสมาชิกตัวถัดไปมาอยู่แทน
         ในการแก้ไขปัญหาทั้งสองเรื่องมีอยู่หลายวิธี เช่นกำหนดตัวแปรให้ชี้ไปยังตำแหน่งสมาชิกที่สำคัญที่สุด หลังจากที่ถูกลบออกไปก็เป็นตำแหน่งว่างทำให้ไม่ต้องขยับสมาชิกตัวอื่นเมื่อเพิ่มสมาชิกใหม่ก็เก็บไว้ตำแหน่งนี้แทน แต่มีข้อเสียก็คือต้องค้นหาสมาชิกที่สำคัญที่สุดทุกครั้งที่มีการลบเช่นเดิม การทำงานแบบนี้จะทำเมื่อมีการลบสมาชิกออกจากคิว แต่มีวิธีที่เหมาะสมกว่าคือการจัดให้สมาชิกทุกตัวเรียงในคิวตามลำดับ โดยสมาชิกในตำแหน่ง Front มีความสำคัญสูงที่สุดและลดหลั่นลงมาจนถึงตำแหน่ง Rear ที่มีความสำคัญน้อยที่สุดการทำงานจะทำเมื่อมีการเพิ่มสมาชิกใหม่เข้ามาในคิว ส่วนการลบสมาชิกในคิวไม่ต้องทำงานเพิ่มเติมดังที่ผ่านมาเพื่อหาสมาชิกที่สำคัญที่สุด เพราะสมาชิกที่ Front จะสำคัญที่สุดสามารถลบออกไปได้ทันที เมื่อใดที่มีสมาชิกใหม่เพิ่มเข้ามาจะทำการจัดเรียงตามลำดับโดยการหาตำแหน่งที่ถูกต้องให้กับสมาชิกใหม่

 


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

          สมมุติให้ระบบคอมพิวเตอร์มีการรับงานเข้ามาเพื่อให้ทำงานโดยมีการกำหนดลำดับความสำคัญ (Priority) ให้แต่ละงานซึ่งมีค่าตั้งแต่ 0 ถึง 10 งานที่มีความสำคัญสูงสุดคือ 10 จะถูกเรียกให้ทำงานก่อน ถ้างานที่มีความสำคัญเท่ากัน งานที่เข้ามาก่อนจะถูกทำงานก่อน (First – Come First – Served, FCFS) โดยระบบปฏิบัติการจะใช้คิวลำดับความสำคัญเป็นตัวควบคุมงาน
(Job Control Block) เมื่อเขียนเป็นโปรแกรมจะได้ดังในตารางที่ 5.3 คือโปรแกรม PrioQue.c
            ตารางที่ 5.3 คือโปรแกรม PrioQue.c

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

          การสร้างคิวลำดับความสำคัญในตัวอย่างเป็นการทำงานของงานที่เข้ามาโดยขึ้นกับความสำคัญ แต่ละงานที่ชื่อกำหนดเป็นตัวอักษรตัวเดียวมีค่าได้ตั้งแต่ A ถึง Z และค่าความสำคัญมีได้ตั้งแต่ 0 น้อยที่สุดจนถึง 10 มากที่สุด การเพิ่มงานเข้ามาในคิวไม่ต้องเรียนตามความสำคัญ แต่เมื่อเก็บในคิวจะมีการจัดเรียงลำดับที่ใช้วิธีการจัดเรียงลำดับความสำคัญ แต่เมื่อเก็บในคิวจะมีการจัดเรียงลำดับที่ใช้วิธีการจัดเรียงลำดับข้อมูล (Sorting) มาช่วย จะเห็นว่าการลบงานออกจากคิวยังคงเหมือนเดิม

บทที่ 1 บทที่ 2 บทที่ 3 บทที่ 4 บทที่ 6 บทที่ 7 บทที่ 8 บทที่ 9 บทที่ 10 บทที่ 11 บทที่ 12
gO h0mE

 

 

 

 

 

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