โครงสร้างข้อมูลแบบ Queue
โครงสร้าง Queue เป็น list ของ Element (รายการ) ที่มีการเพิ่ม 1 ทางและลบข้อมูลออก 1 ทางมีคุณสมบัติที่เข้าก่อนออกก่อน FIFO (First in First out)
การสร้าง Queue
ในการสร้าง Queue สามารถจัดเก็บได้หลายลักษณะ แต่ทั่วไปจะใช้การเก็บแบบ list ทางเดียวหรือArray แบบต่อเนื่องโดยต้องใช้ pointer อีก 2 ตัว ชื่อว่า F (front pointer) เป็นตัวชี้ที่เก็บตำแหน่งส่วนหน้า และ R (rear pointer) เป็นตัวชี้ที่เก็บตำแหน่งส่วนท้าย โดยข้อมูลจะเข้าไปทาง rear หรือส่วนท้ายและจะออกจาก Queue ทาง front หรือส่วนหน้าการดำเนินงานของคิว(Queue Operations) 1. ฟังก์ชั่น Enqueue ฟังก์ชั่น Enqueue เป็นการนำข้อมูลเพิ่มเข้าไปในคิว โดยหลังจากที่ข้อมูลได้เพิ่มเข้าไปในคิวแล้วสมาชิกใหม่ที่เพิ่มเข้าไปจะนำไป ต่อจากส่วน Rear ซึ่งการเพิ่มข้อมูลเข้าไปในคิวก็ไม่ได้แตกต่างไปจากสแต็กตรงที่จะต้องมี พื้นที่ว่างพอที่จะใส่สมาชิกใหม่เข้าไป ดังนั้นหากมีพื้นที่ไม่เพียงพอต่อการเพิ่มสมาชิกใหม่เข้าไปในคิวก็จะเกิด สถานะ Overflow 2.ฟังก์ชั่น Dequeue ฟังก์ชั่น Dequeue เป็นการลบข้อมูลออกจากคิว โดยข้อมูลที่อยู่ส่วน Front จะถูกคืนค่าส่งไปยังยูสเซอร์หรือโมดูลที่เรียกใช้จากนั้นก็จะนำข้อมูลนี้ออก จากคิวในกรณีที่มีการเรียกใช้ฟังก์ชั่นนี้และหากภายในคิวไม่มีข้อมูล ก็จะทำให้เกิดสถานะ Underflow 3.ฟังก์ชั่น Queue Front ฟังก์ชั่น Queue Front ข้อมูลที่อยู่ส่วน Front นั้น สามารถดึงขึ้นมาใช้งานได้ด้วยฟังก์ชั่น Queue Frontฟังก์ชั่นดังกล่าวจะทำการคืนค่าข้อมูลกลับไปยังผู้เรียกใช้โดยไม่มีการ เปลี่ยนแปลงใด ๆ ในคิวอย่างไรก็ตามหากในคิวว่างเปล่า และมีการเรียกใช้งานฟังก์ชั่นนี้ ก็จะทำให้เกิดสถานะของข้อผิดพลาดที่เรียกว่าUnderflow
คิว (Queue) เป็นโครงสร้างข้อมูลที่รู้จักและนำมาใช้งานมากเช่นเดียวกับสแตก (Stack) และมีลักษณะเป็นรายการในแนวเชิงเส้น (Linear List) เช่นกัน มีข้อกำหนดให้ชุดปฏิบัติการสามารถเพิ่มค่าเข้าไปในตอนท้ายของรายการเพียงด้านเดียว เรียกว่า ส่วนหลัง (Rear) และลบค่าในตอนต้นของรายการเพียงด้านเดียว เรียกว่าส่วนหน้า (Front) ซึ่งกำหนดคิวเป็นรูปแบบดังนี้
Q = [Q1, Q2, . . . , QT]
โดย Front (Q) คือ Q1 และ Rear (Q) คือ QT มีจำนานสมาชิกในคิวเท่ากับ T ดังในรูปที่ 5.1 โดยลักษณะมีตัวชี้ส่วนหน้าอยู่ด้านซ้ายและตัวชี้ด้านท้ายอยู่ด้านขวา และอาจกลับด้านกันก็ได้ให้ตัวชี้ส่วนหน้าอยู่ด้านขวาและตัวชี้ส่วนท้ายอยู่ด้านซ้าย
โครงสร้าง Queue เป็น list ของ Element (รายการ) ที่มีการเพิ่ม 1 ทางและลบข้อมูลออก 1 ทางมีคุณสมบัติที่เข้าก่อนออกก่อน FIFO (First in First out)
การสร้าง Queue
ในการสร้าง Queue สามารถจัดเก็บได้หลายลักษณะ แต่ทั่วไปจะใช้การเก็บแบบ list ทางเดียวหรือArray แบบต่อเนื่องโดยต้องใช้ pointer อีก 2 ตัว ชื่อว่า F (front pointer) เป็นตัวชี้ที่เก็บตำแหน่งส่วนหน้า และ R (rear pointer) เป็นตัวชี้ที่เก็บตำแหน่งส่วนท้าย โดยข้อมูลจะเข้าไปทาง rear หรือส่วนท้ายและจะออกจาก Queue ทาง front หรือส่วนหน้าการดำเนินงานของคิว(Queue Operations) 1. ฟังก์ชั่น Enqueue ฟังก์ชั่น Enqueue เป็นการนำข้อมูลเพิ่มเข้าไปในคิว โดยหลังจากที่ข้อมูลได้เพิ่มเข้าไปในคิวแล้วสมาชิกใหม่ที่เพิ่มเข้าไปจะนำไป ต่อจากส่วน Rear ซึ่งการเพิ่มข้อมูลเข้าไปในคิวก็ไม่ได้แตกต่างไปจากสแต็กตรงที่จะต้องมี พื้นที่ว่างพอที่จะใส่สมาชิกใหม่เข้าไป ดังนั้นหากมีพื้นที่ไม่เพียงพอต่อการเพิ่มสมาชิกใหม่เข้าไปในคิวก็จะเกิด สถานะ Overflow 2.ฟังก์ชั่น Dequeue ฟังก์ชั่น Dequeue เป็นการลบข้อมูลออกจากคิว โดยข้อมูลที่อยู่ส่วน Front จะถูกคืนค่าส่งไปยังยูสเซอร์หรือโมดูลที่เรียกใช้จากนั้นก็จะนำข้อมูลนี้ออก จากคิวในกรณีที่มีการเรียกใช้ฟังก์ชั่นนี้และหากภายในคิวไม่มีข้อมูล ก็จะทำให้เกิดสถานะ Underflow 3.ฟังก์ชั่น Queue Front ฟังก์ชั่น Queue Front ข้อมูลที่อยู่ส่วน Front นั้น สามารถดึงขึ้นมาใช้งานได้ด้วยฟังก์ชั่น Queue Frontฟังก์ชั่นดังกล่าวจะทำการคืนค่าข้อมูลกลับไปยังผู้เรียกใช้โดยไม่มีการ เปลี่ยนแปลงใด ๆ ในคิวอย่างไรก็ตามหากในคิวว่างเปล่า และมีการเรียกใช้งานฟังก์ชั่นนี้ ก็จะทำให้เกิดสถานะของข้อผิดพลาดที่เรียกว่าUnderflow
คิว (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
