Queue

Queue

 
      เป็นโครงสร้างข้อมูล ( data structure ) ชนิดหนึ่ง  มีรูปแบบของการเข้าออก
 ของข้อมูล  โดยที่ปลายด้านหนึ่งของคิวจะเป็นทางสำหรับข้อมูลที่จะนำเข้ามา
 เก็บในคิว  เรียกปลายด้านนี้ว่า Rear  ส่วนปลายอีกด้านจะเป็นทางสำหรับนำข้อ
 มูลออก  เรียกปลายด้านนี้ว่า Front  ยกตัวอย่างของคิวที่เห็นได้ชัดเจนในชีวิตประ
 จำวัน  เช่น  การเข้าแถวซื้อบัตรเข้าชมภาพยนต์  โดยผู้ที่มาเข้าแถวเป็นอันดับแรก
 ก็จะเป็นผู้ที่ได้ซื้อก่อน  ซึ่งเทียบได้กับด้าน Front  ส่วนผู้ที่จะมาซื้อคนต่อไปก็ต้อง
 เข้าไปต่อแถวเป็นคนสุดท้าย  ซึ่งเทียบได้กับด้าน Rear  ลักษณะเช่นนี้จึงมีชื่อเรียก
 อีกอย่างคือ FIFO  ย่อมาจาก First In First Out ( หมายถึงเข้าก่อนออกก่อนนั่นเอง )
      ในระบบ computer คิวถูกนำมาใช้ในงานที่ต้องมีการรอเข้าทำงาน  เช่น  printer
 ที่ใช้กันอยู่ก็จะเป็นในลักษณะคิวเช่นกัน  คือ  งานไหนที่ส่งมายัง printer ก่อนก็จะ
 ถูก print ก่อน  ส่วนงานอื่นๆ ก็จะทยอยเข้ามาใช้ printer เป็นตามลำดับ  หรือ  ในขณะ
 ที่เราใช้ program  พวก  word processor  ในขณะที่เราพิมพ์ข้อความ  หากขณะนั้น
 cpu time ถูกใช้โดย program อื่นๆ   ตัวอักษรที่เราพิมพ์เข้าไป ก็จะถูกเก็บในลักษณะ
 ของคิวอีกเช่นกัน  คือ  จะรอจนกว่าตัว program จะได้เข้าไปใช้งาน cpu  ตัวอักษรที่
 เก็บในคิวจึงจะถูกนำออกมา
  เริ่มต้น ก่อนที่เราจะนำคิวไปใช้งาน จะต้องมีการจองเนื้อที่ใน memory เพื่อที่จะใช้
 เป็นที่เก็บข้อมูลต่อไป  ซึ่งตรงนี้ถ้าหากเราจองเนื้อที่ไว้มากเกิน  จะทำให้เสียเนื้อที่ของ
 memory ไปโดยเปล่าประโยชน์ซึ่งตรงนี้เราอาจนำโครงสร้างข้อมูลแบบอื่นมาช่วยอีก
 แต่ในที่นี้จะยังไม่กล่าวถึง ขนาดของเนื้อที่ในการจองในที่นี้ขอใช้แทนด้วย maxSize

Enqueue

 
      เป็นฟังก์ชั่นพื้นฐานของโครงสร้างข้อมูลแบบคิว เหมือนกับการที่เราไปเข้าแถว
 ต่อซื้อของ  เริ่มต้นหลังจากที่สร้างคิวขึ้นมาแล้ว  ขั้นตอนต่อไปคือการนำข้อมูลใส่
 ในคิว  ซึ่งในการใส่ข้อมูลลงในคิวจะใส่เข้าทางด้าน Rear โดยจะต้องทำการ check
 ก่อนทุกครั้งว่าคิวที่จะนำข้อมูลนี้ใส่ลงไปว่างหรือไม ่  ถ้าคิวว่างก็ให้ทำการใส่ข้อมูล
 ลงไปในคิว  แต่ถ้าเกิดคิวที่จะใส่ข้อมูลนั้นเต็ม คือ มีข้อมูลเท่ากับจำนวนข้อมูลมาก
 สุด( maxSize )ที่ได้กำหนดไว้ในตอนที่สร้างคิวขึ้นมา  จะเกิดเหตุการณ์ที่เรียกว่า
 overflow ในการเพิ่มข้อมูลลงในคิวจะทำให้ค่าของ rear เลื่อนขึ้นหนึ่งตำแหน่ง
 
  Algorithm ของฟังก์ชั่น enqueue( queue, data ) 
 if parameter equal null => return error
 
 if queue's elements equal queue's max size => return overflow error
 
 queue[ rear ] = data
 
 rear = rear + 1
 
 if rear equal queue's max size => rear = 0
 

 

Dequeue

 
      เป็นฟังก์ชั่นในการนำข้อมูลออกจากคิว ซึ่งจะมีการทำงานตรงข้ามกับ enqueue
 เนื่องจากฟังก์ชั่น dequeue จะนำข้อมูลออกทางด้าน front หลังจากนั้นจะส่งข้อมูล
 ที่ได้ต่อไปยังตัวที่เรียกอีกทีหนึ่ง ก่อนที่เราจะนำข้อมูลที่อยู่ในคิวออกนั้น จำเป็น
 ต้อง check ก่อนว่าคิวนั้นมีข้อมูลอยู่หรือไม่ เพราะถ้าเราเรียกฟังก์ชั่น dequeue
 ในขณะที่ไม่มีข้อมูลอยู่ภายในคิว จะทำให้เกิด underflow ในการนำข้อมูลออกจาก
 คิวจะทำให้ค่าของ front เลื่อนขึ้นหนึ่งตำแหน่ง
 
  Algorithm ของฟังก์ชั่น dequeue( queue ) 
 if queue's element equal zero => return underflow error
 
 reciever = queue[ front ]
 
 front = front - 1
 
 if front equal queue's max size => front = 0
 
 return reciever to caller function
 

 

QueueFront

 
  เป็นฟังก์ชั่นในการเรียกดูค่าที่อยู่ในตำแหน่ง front จะคล้ายกันกับฟังก์ชั่น
 dequeue  แต่ฟังก์ชั่น queueFront จะเป็นการ copy ค่าออกมาโดยจะไม่เลื่อน
 ค่าของ front ทำให้  คิวไม่มีการเปลี่ยนแปลง

  Algorithm ของฟังก์ชั่น queueFront( queue ) 
 if queue's element equal zero => return empty queue error
 
 reciever = queue[ front ]
 
 return reciever to caller function
 

 

QueueRear

 
      เป็นฟังก์ชั่นที่ copy ค่าข้อมูลที่อยู่ที่ตำแหน่ง rear ของคิว

  Algorithm ของฟังก์ชั่น queueFront( queue ) 
 if queue's element equal zero => return empty queue error
 
 reciever = queue[ front ]
 
 return reciever to caller function
 

 

EmptyQueue

 
  ในการเรียกใช้ฟังก์ชั่นต่างๆ ที่ต้องมีการ check ก่อนว่าคิวนั้นๆ เป็นคิวว่างหรือไม่
 จึงมีฟังก์ชั่นในการ check โดยจะเป็นจริง  ก็ต่อเมื่อคิวนั้นเป็นคิวว่าง
 ไม่เช่นนั้นแล้วจะเป็นเท็จ

  Algorithm ของฟังก์ชั่น emptyQueue( queue ) 
 if queue's element equal zero => return true
 
 return false
 

 

FullQueue

 
  การทำงานจะตรงข้ามกับฟังก์ชั่น emptyQueue โดยฟังก์ชั่น fullQueue
 จะเป็นจริงก็ต่อเมื่อ จำนวนสามชิกที่มีอยู่ในคิวต้องไม่เกินจำนวนข้อมูลที่
 คิวจะรับได้ ไม่เช่นนั้นจะเป็นเท็จ

  Algorithm ของฟังก์ชั่น emptyQueue( queue ) 
 if queue's element equal queue's max size => return true
 
 return false
 

 

Circular Queue

 
      ดังตัวอย่างการเข้าคิวซื้อบัตรเข้าชมภาพยนต์ พอคนแรกซื้อเสร็จคนต่อ
 มาก็จะเดินร่อนเข้าไปแทนที่คนที่หนึ่ง จำนวนคนที่เข้าแถวซื้อจะถูกจำกัด
 ด้วยจำนวนบัตรที่มีในแต่ละรอบ แต่ในระบบ computer ข้อมูลที่จะถูกเก็บอยู่
 ในคิวจะถูกจำกัดโดย resourceหรือ memory ของระบบนั้น การที่เราทำการ
 ใส่ข้อมูลลงไปในคิว เพื่อที่จะใช้ memoryให้เพียงพอกับที่เรากำหนดไว้ วิธีการ
 หนึ่งคือการที่เราเลื่อนข้อมูลที่เหลืออยู่ในคิวมายังปลายด้านที่จะนำข้อมูลออก
 เพื่อที่จะได้มีที่ว่างสำหรับการนำข้อมูลมาใส่ต่อไปซึ่งเป็นวิธีที่ใช้ได้เฉพาะกับ
 ข้อมูลที่มีจำนวนน้อย เนื่องจากหากข้อมูลมีจำนวนมากเป็นพันเป็นหมื่นข้อมูล
 การที่เราจะทำการเลื่อนข้อมูลนั้นจะทำให้เสียเวลามาก จึงมีแนวคิดในการใส่
 ข้อมูลขึ้นมาใหม่ ซึ่งเรียกว่า Circular Queue
      โดยการทำงานส่วนใหญ่ของ Circular Queue จะยังคงเหมือน Queue แต่
 ต่างกันที่หากคิวนั้นมีข้อมูลตัวสุดท้ายอยู่ที่ตำหน่งท้ายสุดของคิว( maxSize )
 และเราทำการใส่ข้อมูลลงไปในคิวอีก ข้อมูลที่ใส่ลงไปใหม่นั้นจะถูกเก็บไว้ใน
 ตำแหน่งเริ่มต้นของคิว และหากเราใส่ข้อมูลลงไปอีก ข้อมูลก็จะถูกใส่ลงไปใน

คิวเต็ม
คิวต่อจากข้อมูลที่แล้ว แต่ทุกกรณีที่กล่าวมานั้นคิวที่ใช้ต้องไม่ใช่