โครงสร้างข้อมูลแบบคิว (Queue)

มาทำความรู้จักกับโครงสร้างข้อมูลแบบคิว (Queue)

สำหรับวันนี้ผมจะเขียนเรื่องคิวและการใช้งานคิวด้วยภาษาจาวา ‣ คิว (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) อย่างไรก็ตาม มีบางครั้งที่เราต้องยกให้สมาชิกบางประเภทได้ทำงานก่อนทั้งที่มาทีหลัง เช่น การให้คิวงานที่เล็กกว่าได้ทำก่อน หรือ การให้สิทธิพิเศษแก่การทำงานบางประเภท
  • คิวลำดับความสำคัญ ทำให้เราสามารถประยุกต์ใช้คิวได้ดีขึ้น เนื่องจากเพิ่มการให้ความสำคัญของสมาชิกที่แตกต่างกัน ส่งผลให้เราสามารถจัดเรียงคิวได้ใหม่ให้เหมาะสมกับการทำงานได้ เราใช้คิวลำดับความสำคัญในการจัดการทำงานการตรวจนับ

สำหรับเรื่องโครงสร้างข้อมูลคิว ผมขอจบเพียงเท่านี้ครับ

อ้างอิง: ดูบทความที่มีเนื้อหาโดยละเอียดได้ที่นี่


© 2017-2018 Solution Dee Co.,Ltd. All Rights Reserved.

Powered by Hydejack v7.3.0