การประยุกต์ใช้ Queue

นึกภาพก่อน

หยดหมึกลงบนกระดาษซับ หมึกจะแผ่ออกเป็นวงเท่า ๆ กันทุกทิศ จุดที่อยู่ใกล้จะเปียกก่อนจุดที่อยู่ไกล ถ้าจดไว้ว่าแต่ละจุดเปียกในรอบที่เท่าไร ตัวเลขนั้นคือระยะห่างจากจุดที่หยด

การหาระยะสั้นสุดในตารางใช้ความคิดเดียวกัน และ queue คือสิ่งที่ทำให้ "ใกล้ก่อน ไกลทีหลัง" เกิดขึ้นได้เอง เพราะช่องที่ถูกพบก่อนจะถูกนำมาขยายก่อน (FIFO)

Queue เป็นที่พักข้อมูล

Queue เหมาะกับสถานการณ์ที่ผู้ผลิตข้อมูลกับผู้ใช้ข้อมูลทำงานเร็วไม่เท่ากัน:

งานที่มาก่อนได้รับบริการก่อน และไม่มีงานใดหายแม้ผู้ใช้ข้อมูลจะช้ากว่า

หาระยะสั้นสุดในตาราง

โจทย์: ตารางมีช่องว่างและช่องกำแพง หาจำนวนก้าวน้อยสุดจากช่องต้นทางไปช่องปลายทาง เดินได้ 4 ทิศ (บน ล่าง ซ้าย ขวา)

วิธีทำ

1. ใส่เลข 0 ที่ช่องต้นทาง แล้ว enqueue ช่องนั้น
2. dequeue ช่องหนึ่งออกมา สมมติมีเลข k
3. ขยายไปช่องรอบข้างทั้ง 4 ทิศ เฉพาะช่องที่ ว่าง และ ไม่เลยขอบ: ใส่เลข k + 1 แล้ว enqueue
4. ทำซ้ำจนพบช่องปลายทาง หรือคิวว่าง

เลขในแต่ละช่องคือระยะสั้นสุดจากต้นทาง จากนั้นย้อนจากปลายทางตามเลขที่ลดลงทีละหนึ่งเพื่อหาเส้นทาง

โค้ดจากสไลด์

static void findPath(int[][] map, Pos source, Pos target) {
  map[source.row][source.col] = 0;    // ต้นทาง
  map[target.row][target.col] = -1;   // ปลายทาง
  Queue q = new ArrayQueue(map.length); q.enqueue(source);
  while (!q.isEmpty()) {
    Pos p = (Pos) q.dequeue();
    if (p.row == target.row && p.col == target.col) break;
    expand(map, q, p.row + 1, p.col, map[p.row][p.col] + 1);
    expand(map, q, p.row - 1, p.col, map[p.row][p.col] + 1);
    expand(map, q, p.row, p.col + 1, map[p.row][p.col] + 1);
    expand(map, q, p.row, p.col - 1, map[p.row][p.col] + 1);
  }
}
static void expand(int[][] map, Queue q, int r, int c, int k) {
  if (r < 0 || r >= map.length ||
      c < 0 || c >= map[r].length || map[r][c] != 0) return;
  map[r][c] = k;
  q.enqueue(new Pos(r, c));
}

จุดที่ควรอ่านให้ออก:

• (Pos) q.dequeue() ต้อง downcast เพราะคิวเก็บเป็น Object
• expand ตรวจสามอย่างก่อน: เลยขอบแถว, เลยขอบคอลัมน์, และช่องไม่ว่าง (กำแพง หรือเคยใส่เลขแล้ว)
• การใส่เลขลงในช่องทำหน้าที่ "จำว่ามาแล้ว" ไปในตัว ช่องเดียวจึงไม่ถูก enqueue ซ้ำ

ตัวอย่างไล่ทีละขั้น

ตาราง 3×3 ช่อง # คือกำแพง ต้นทาง S อยู่มุมซ้ายบน ปลายทาง T อยู่มุมขวาล่าง:

S . .
# # .
. . T

ผลในตาราง:

0 1 2
# # 3
. . 4

ระยะสั้นสุดคือ 4 ก้าว ช่อง (2,0) และ (2,1) ไม่ถูกใส่เลขเพราะโปรแกรมหยุดเมื่อถึงปลายทาง

ทำไมต้องเป็น Queue

ถ้าเปลี่ยนเป็น stack ช่องที่พบล่าสุดจะถูกขยายก่อน โปรแกรมจะพุ่งไปทางเดียวจนสุดแล้วค่อยย้อน เลขที่ใส่จึงไม่ใช่ระยะสั้นสุด Queue รับประกันว่าช่องระยะ k ทุกช่องถูกขยายก่อนช่องระยะ k + 1

จุดที่มักพลาด

1. ใส่เลขตอน dequeue แทนตอน enqueue

ต้องใส่เลขทันทีที่พบช่อง (ใน expand) ไม่อย่างนั้นช่องเดียวกันจะถูก enqueue ซ้ำจากหลายทิศ

2. ลืมตรวจขอบ

map[r][c] ที่ r หรือ c เลยขอบจะเกิด ArrayIndexOutOfBoundsException จึงต้องตรวจขอบก่อนอ่านค่า (ลำดับใน || สำคัญ: ตรวจขอบก่อน แล้วจึงตรวจ map[r][c])

3. คิดว่าขยายได้ 8 ทิศ

สไลด์ขยาย 4 ทิศเท่านั้น ไม่มีแนวทแยง

4. คิดว่าเลขในช่องคือจำนวนช่องที่เดินผ่าน

คือจำนวน ก้าว จากต้นทาง ต้นทางเป็น 0

5. ใช้ stack แทน

ได้เส้นทาง แต่ไม่รับประกันว่าสั้นที่สุด

ที่มา: QUEUE_6.pdf หน้า 20–33