สำหรับวันนี้ผมจะเขียนเรื่องคิวและการใช้งานคิวด้วยภาษาจาวา ‣ คิว (Queue) เป็นโครงสร้างข้อมูลแบบเชิงเส้นซึ่งการเพิ่มข้อมูลจะกระทำที่ปลายข้างหนึ่งซึ่งเรียกว่า ส่วนท้าย (Rear) และการนำข้อมูลออกจะกระทำที่ปลายอีกข้างหนึ่งซึ่งเรียกว่า ส่วนหน้า หรือฟรอนต์ (Front) ลักษณะการทำงานของคิวเป็นลักษณะของการเข้าก่อน ออกก่อนหรือที่เรียกว่า FIFO (First In First Out)
ลักษณะของคิว
- โครงสร้างข้อมูลแบบคิวเป็นโครงสร้างเชิงเส้น
- มีทางเข้าและออก 2 ทาง
- มีการทำงานแบบลำดับ
- สามารถนำข้อมูลเข้าและนำข้อมูลออกสลับกันได้
- มีลำดับการทำงานแบบเข้าก่อนออกก่อน (FIFO)
ประเภทของคิว มี 3 ประเภท
- คิวธรรมดา (Queue)
- คิววงกลม (Circular Queue)
- คิวที่เรียงลำดับตามความสำคัญ (Priority Queue)
การดำเนินการของคิว
เมื่อนำเข้าข้อมูลจะต้องจัดเรียงในลักษณะการต่อท้ายกัน
- ข้อมูลที่อยู่ส่วนท้ายของการเก็บข้อมูล เรียกว่า Rear
- ข้อมูลที่อยู่ส่วนหัวของการเก็บข้อมูล ซึ่งจะเรียกว่า Front
- การนำข้อมูลเข้าไปในคิว เรียกว่า Insert (Enqueue)
- การนำข้อมูลออกจากคิว เรียกว่า Remove (Dequeue)
ตัวอย่างการเพิ่มสมาชิกใหม่ลงในคิว
List<String> listNames = Arrays.asList("Alice", "Bob", "Cole", "Dale", "Eric", "Frank");
Queue<String> queueNames = new LinkedList<>(listNames);
System.out.println("Old queue:"+queueNames);
//Add new element
queueNames.add("Mary");
queueNames.add("John");
System.out.println("New queue:"+queueNames);
ผลลัพธ์
Old queue:[Alice, Bob, Cole, Dale, Eric, Frank]
New queue:[Alice, Bob, Cole, Dale, Eric, Frank, Mary, John]
จะเห็นว่า สมาชิกใหม่ ที่เพิ่มเข้าไปในคิว จะไปต่อท้ายสมาชิกของคิวตามลำดับ
ตัวอย่างการนำสมาชิกออกจากคิว
List<String> listNames = Arrays.asList("Alice", "Bob", "Cole", "Dale", "Eric", "Frank");
Queue<String> queueCustomers = new LinkedList<>(listNames);
System.out.println("Old queue:"+queueCustomers);
String next = queueCustomers.remove();
System.out.println("Next customer is: "+ next);
System.out.println("New queue:"+queueCustomers);
ผลลัพธ์
Old queue:[Alice, Bob, Cole, Dale, Eric, Frank]
Next customer is: Alice
New queue:[Bob, Cole, Dale, Eric, Frank]
จากตัวอย่าง จะเป็นการนำสมาชิกออกจากคิวที่ส่วนหน้า ซึ่งก็คือ Alice
คิวธรรมดา (Queue)
คิวธรรมดา หมายถึง คิวที่มีการนำข้อมูลเข้าทางท้ายคิว (Rear) และนำข้อมูลออกทางหน้าคิว (Front) โดยถ้าท้ายคิวไปอยู่ที่ตำแหน่งท้ายสุดของคิวแล้ว ถึงแม้จะมีช่องว่างเหลือที่หัวคิวก็ไม่สามารถนำข้อมูลใหม่ไปเก็บได้ จนกว่าจะนำข้อมูลในคิวออกให้หมดก่อนจึงเริ่มนำข้อมูลใหม่ไปเก็บได้
การนำข้อมูลเข้า Enqueue
ก่อนนำสมาชิกเข้าคิว ต้องตรวจสอบว่าคิวเต็มหรือไม่ โดยที่ ถ้า rear = maxQ แสดงว่าคิวเต็ม (เมื่อ maxQ คือขนาดของคิว) การนำข้อมูลใหม่เข้ามาแถวคอย จะเพิ่มเข้ามาด้านหลังและจะนำเข้ามาเรื่อย ๆ จนเต็ม หรือเรียกว่า แถวคอยเต็ม (Queue Overflow) ดังนั้นการนำสมาชิกเข้าคิวจึงเป็นการเพิ่มค่าพอยน์เตอร์ rear หากมีสมาชิกในคิวเพียงค่าเดียวพอยน์เตอร์ rear และ front จะเท่ากัน
คิวแบบวงกลม (Circular Queue)
- เหมือนคิวธรรมดาคือมีตัวชี้ 2 ตัวคือ front และ rear สำหรับแสดงตำแหน่งหัวคิวและท้ายคิวตามลำดับ
- แตกต่างจากคิวธรรมดา คือ คิวธรรมดาเมื่อ rear ชี้อยู่ที่ตำแหน่งสุดท้ายของคิว จะทำให้ไม่สามารถเพิ่มข้อมูลเข้าไปในคิวได้อีก ทั้งที่บางครั้งยังมีที่ว่างเหลืออยู่ก็ตาม
- คิววงกลมจัดการปัญหานี้โดย กรณี rear ชี้อยู่ที่ตำแหน่งสุดท้ายของคิว ถ้าหากมีการเพิ่มข้อมูล ค่าของ rear จะสามารถวนกลับมาชี้ยังตำแหน่งแรกสุดของคิวได้
ดังนั้นคิววงกลมจะสามารถเพิ่มข้อมูลเข้าไปในคิวได้ จนกว่าคิวจะเต็มจริง ๆ
คิวลำดับความสำคัญ (Priority Queue)
- ใน คิวธรรมดา ข้อมูลที่เข้ามาก่อนจะมีสิทธิ์ออกก่อน (First In First Out:FIFO) อย่างไรก็ตาม มีบางครั้งที่เราต้องยกให้สมาชิกบางประเภทได้ทำงานก่อนทั้งที่มาทีหลัง เช่น การให้คิวงานที่เล็กกว่าได้ทำก่อน หรือ การให้สิทธิพิเศษแก่การทำงานบางประเภท
- คิวลำดับความสำคัญ ทำให้เราสามารถประยุกต์ใช้คิวได้ดีขึ้น เนื่องจากเพิ่มการให้ความสำคัญของสมาชิกที่แตกต่างกัน ส่งผลให้เราสามารถจัดเรียงคิวได้ใหม่ให้เหมาะสมกับการทำงานได้ เราใช้คิวลำดับความสำคัญในการจัดการทำงานการตรวจนับ
สำหรับเรื่องโครงสร้างข้อมูลคิว ผมขอจบเพียงเท่านี้ครับ