คิวเป็นการเก็บข้อมูลที่คล้ายกับสแต็คแต่เปลี่ยนจากเข้าหลังออกก่อน เป็นเข้าก่อนออกก่อนหรือ FIFO (First-In-First-Out) หรือก็คือคิวก็คือคิวที่ใช้กันอยู่ในชีวิตประจำวันเช่นการเข้าแถวซื้ออาหารมาก่อนก็จะได้ก่อน สิ่งคิวสามารถทำได้ก็เก็บข้อมูลเรียกว่า enqueue ลบข้อมูลเรียกว่า dequeue และดูข้อมูล เรียกว่า peek เหมือนเดิม

Queue

รูป5-1

            ต้องการเก็บข้อมูลเป็นชื่อของโซเชียลเน็ตเวิร์คต่างๆ  เมื่อทำการเพิ่ม(enqueue) “Line” ลงไปในคิว “Line” ก็จะไปอยู่บนสุดของคิว เมื่อต้องการลบข้อมูลด้วย dequeue() ข้อมูลที่ถูกเพิ่มเข้าไปตัวแรก ก็คือ “Twitter” จะถูกลบออกจากคิว เมื่อขอดูข้อมูลด้วย peek() ก็จะได้ข้อมูลตัวแรกสุดที่รอคิวจะถูกลบ ในภาพก็คือ “Facebook”

                เช่นเดียวกับสแต็ค คิวก็สามารถสร้างได้จาก list เช่น ArrayList หรือ LinkedList และ การเก็บข้อมูล collection เช่น Array แต่ถ้าสร้างด้วยอาร์เรย์ลิสต์ก็จะมีปัญหาเล็กน้อยตรงที่อาร์เรย์ลิสต์นั้นข้อมูลจะต้องเริ่มที่ช่อง 0 การ dequeue จะเอาข้อมูลที่ใส่เข้าไปก่อน เมื่อทำการลบข้อมูลช่อง 0 ก็จะทำให้ต้องมีการขยับข้อมูลทุกตัว

สร้างคิวด้วย ArrayList

                การสร้างคิวด้วยอาร์เรย์ลิสต์สามารถเรียกใช้งานเมท็อดของลิสต์ได้เลย

รูป5-2

บรรทัดที่ 3 สร้างคลาส QueueList สำหรับสร้างคิวด้วยอาร์เรย์ลิสต์

บรรทัดที่ 5 : สร้างอ็อปเจ็คของ ArrayList

บรรทัดที่ 6-8: สร้างคอนสตรัคเตอร์ของ QueueList

บรรทัดที่ 11 : สร้างเมท็อด enqueue สำหรับเพิ่มข้อมูลลงในคิว

บรรทัดที่ 13 : การเพิ่มข้อมูลลงในคิวซึ่งข้อมูลในคิวก็มาต่อท้ายเรื่อยๆสามารถเรียกเมท็อด add ของ ArrayList ได้เลย

บรรทัดที่ 16 : สร้างเมท็อด dequeue สำหรับลบข้อมูล

บรรทัดที่ 18-20 : สร้างตัวแปร t เก็บข้อมูลตัวแรกซึ่งได้จากการเรียก peek() ลบข้อมูลออกจากนั้นให้คืนค่า t ออกไป

บรรทัดที่ 23 : สร้างเมท็อด peek สำหรับเรียกดูข้อมูล

บรรทัดที่ 25: ใช้เมท็อด get สำหรับเรียกดูข้อมูล

บรรทัดที่ 28-30 : สร้างเมท็อด size คืนค่า size

ไพออริตี้คิว(Priority Queue)

            การเก็บข้อมูลแบบคิวคือการเก็บข้อมูลแบบมาก่อนได้ก่อน แต่อย่างไรก็ตามบางครั้งก็บางเหตุการณ์ที่ต้องการให้บางอย่างมีความสำคัญมากกว่าสิ่งอื่นๆ เช่น เวลาไปโรงบาลก็จะต้องให้ต่อแถวก็จริงแต่ถ้ามีอุบัติเหตุฉุกเฉินก็จำเป็นต้องให้หมอไปดูก่อน หลักการของ Priority Queue ก็เช่นเดียวกัน เป็นการเก็บข้อมูลไว้ตามความสำคัญของข้อมูล

เมท็อดที่มีใน Priority Queue

            เมท็อดใน Priority Queue เหมือนกับของคิว ได้แก่ enqueue, dequeue, peek โดยที่ enqueue จะเป็นการเพิ่มข้อมูลไว้ท้ายสุด ส่วน dequeue, peek จะลบและเรียกดูข้อมูลที่มีความสำคัญสุด

            Priority Queue สามารถสร้างได้จาก list โดยใน peek ให้หาค่ามากสุดใส่ในตัวแปร max จากนั้นเมื่อต้องการ dequeue, peek ให้เรียกจาก max มาใช้งาน หรือจะสร้างจากสิ่งที่เรียกว่า heap ก็ได้ โดยจะเสนอในแบบของ heap

ไบนารี ฮีป(binary heap)

            ลักษณะของไบนารีฮีปจะคล้ายกับต้นไม้ โดยการเรียงปมจะเรียงจากซ้ายไปขวา ฮีปจะเก็บข้อมูลตามความสำคัญ คือความสำคัญนั้นอาจจะเป็นตัวมากหรือตัวน้อยก็ได้ ถ้าเป็นตัวมากเรียกว่า ฮีปมากสุด(max heap)  และถ้าเป็นตัวน้อยเรียกว่า ฮีปน้อยสุด(min heap)

            ในกรณีของ max heap  กำหนดว่าโหนดพ่อต้องมีค่าไม่น้อยกว่าโหนดลูกทั้งสองข้าง กลับกับถ้าเป็น min heap คือโหนดพ่อต้องมีค่าน้อยกว่าโหนดลูกทั้งสอง

รูป5-3

            จากภาพจะเห็นว่า min heap ที่โหนดรากจะมีค่าน้อยกว่าโหนดลูกทางซ้ายและทางขวา ในขณะที่โหนดลูกของลูก(หมายเลข 4 5 6) ก็มีค่ามากกว่าโหนดลูกของรากด้วย(หมายเลข 2 3) ส่วน max heap ก็จะกลับกัน

            การเก็บข้อมูลของ heap จะเก็บข้อมูลแบบเรียงจากซ้ายไปขวา ในภาพ max heap จะได้ข้อมูลเรียงกันเป็น 17 15 10 6 10 7 ตามลำดับ ดังนั้นเราจึงสามารถคำนวณหาได้ว่าโหนดลูกของโหนดใดๆจะมีโหนดลูกเป็นหมายเลขอะไร และโหนดลูกใดๆจะมีโหนดพ่อเป็นหมายเลขอะไร โดยคำนวณดังนี้

            พ่อของโหนด x หาได้จาก             (x-1) / 2 เช่น โหนด 5 จะได้ (5-1)/2 = 2 ตามตามภาพ

            ลูกซ้ายของโหนด x หาได้จาก       2x + 1

            ลูกขวาของโหนด x หาได้จาก        2x + 2

การสร้าง max heap

รูป5-4

บรรทัดที่ 3 : import Comparator

บรรทัดที่ 5 : สร้างคลาส MaxHeap

บรรทัดที่ 7 : สร้างตัวแปร data เป็นอาร์เรย์ที่เก็บจำนวนเต็ม

บรรทัดที่ 8 : ตัวแปร size สำหรับเก็บขนาด

บรรทัดที่ 9 : สร้างตัวแปร comparator เป็นชนิดคลาส Comparator  ที่ import มาไว้เป็นตัวสำหรับเปรียบเทียบข้อมูลสองตัว หรือจะ implements อินเตอร์เฟสที่ชื่อ Comparable ก็ได้ โดยใน Comparable จะมีเมท็อดชื่อ compareTo

บรรทัดที่ 11 : สร้างคอนสตรัคเตอร์ของคลาส MaxHeap

รูป 5-5

บรรทัดที่ 18 – 20 : เมท็อด size สำหรับคืนค่าขนาดของฮีป

บรรทัดที่ 23-25 : เมท็อดคำนวณหาตำแหน่งของโหนดพ่อ ให้คืนค่าเป็นสูตร (x-1) / 2

บรรทัดที่ 28-30 : เมท็อดคำนวณหาตำแหน่งของโหนดลูกซ้าย ให้คืนค่าเป็นสูตร 2x+1

บรรทัดที่ 33-35 : เมท็อดคำนวณหาตำแหน่งของโหนดลูกขวา ให้คืนค่าเป็นสูตร 2x+2

รูป 5-6

บรรทัดที่ 38 : สร้างเมท็อด swap สำหรับการสลับโหนดสองโหนดรับพารามิเตอร์เป็นโหนดสองโหนดที่ต้องการสลับที่กัน

บรรทัดที่ 40 : สร้างตัวแปร t สำหรับเก็บข้อมูลของตัวแรก

บรรทัดที่ 41 : สลับตำแหน่งตัวแรกกับตัวที่สอง

บรรทัดที่ 42 : เอาสิ่งที่อยู่ใน t หรือก็คือข้อมูลตัวแรกไปไว้ในตัวที่สอง