14.5 queue และ deque

แถวซื้อชานมหน้าโรงเรียน คนมาใหม่ต่อท้ายแถว คนที่ได้ชานมคือคนหัวแถว ใครมาก่อนได้ก่อน โครงสร้างข้อมูลแบบนี้เรียกว่า queue (คิว) หลักของมันคือ FIFO ย่อมาจาก first in, first out เข้าก่อน ออกก่อน ตรงข้ามกับ stack ในหน้าที่แล้ว

โจทย์ที่ต้องจำลองการรอคิว เช่น ร้านค้า เครื่องพิมพ์ หรือเกมที่ผู้เล่นวนกันเล่นทีละคน ใช้ queue ตรงๆ และในบทที่ 27 queue จะเป็นหัวใจของ BFS ซึ่งใช้หาระยะทางที่สั้นที่สุดในตาราง ท้ายหน้ามี deque ซึ่งเป็นคิวที่เข้าออกได้ทั้งสองหัว

งานของ queue

ชื่อ	ทำอะไร
enqueue	ต่อท้ายคิว
dequeue	เอาคนหัวคิวออก
front	ดูว่าใครอยู่หัวคิว โดยไม่เอาออก
empty	ถามว่าคิวว่างไหม
size	ถามว่ามีกี่คน

ต่างจาก stack ตรงที่งานเกิดสองหัว เข้าทางท้าย ออกทางหัว จึงต้องมีตัวแปรสองตัว head คือช่องของคนหัวคิว และ tail คือช่องว่างช่องถัดจากคนท้ายคิว ซึ่งคนต่อไปจะมายืน

queue ด้วยอาเรย์

วิธีที่ง่ายที่สุดคือให้ทั้ง head และ tail เดินไปทางขวาอย่างเดียว คนที่ออกไปแล้วไม่ต้องลบ แค่เลื่อน head ผ่านไป ไม่ต้องเลื่อนคนที่เหลือมาข้างหน้าแบบหน้า 5.5 เลย

จำนวนคนในคิวคือ tail - head คิวว่างเมื่อ head == tail โปรแกรมนี้ใช้ลำดับคำสั่งเดียวกับโปรแกรม plates ในหน้า 14.4 ลองเทียบผลลัพธ์ดู

#include <stdio.h>

int queue[100000];
int head = 0, tail = 0;

void enqueue(int x)
{
    queue[tail] = x;
    tail++;
}

int dequeue(void)
{
    int x = queue[head];
    head++; // (1)!
    return x;
}

int front(void)
{
    return queue[head];
}

int queue_size(void)
{
    return tail - head;
}

int is_empty(void)
{
    return head == tail;
}

int main()
{
    enqueue(11);
    enqueue(12);
    enqueue(13);
    printf("front = %d\n", front());
    printf("dequeue = %d\n", dequeue());
    printf("dequeue = %d\n", dequeue());
    enqueue(14);
    printf("size = %d\n", queue_size());
    while (!is_empty()) {
        printf("dequeue = %d\n", dequeue());
    }
    return 0;
}

จำค่าหัวคิวไว้ก่อน แล้วเลื่อน head ไปคนถัดไป ช่องเดิมยังมีค่าค้างอยู่ แต่อยู่นอกคิวแล้ว

front = 11
dequeue = 11
dequeue = 12
size = 2
dequeue = 13
dequeue = 14

คำสั่งเหมือนกันทุกบรรทัด แต่ stack ได้ 13 12 14 11 ส่วน queue ได้ 11 12 13 14 ตามลำดับที่เข้ามาพอดี

ข้อแม้ของวิธีนี้คือ tail เดินไปข้างหน้าทุกครั้งที่มีคนเข้า ไม่เคยถอยกลับ อาเรย์จึงต้องมีช่องเท่ากับจำนวนครั้งที่ enqueue ทั้งหมด ไม่ใช่จำนวนคนที่อยู่ในคิวพร้อมกัน ถ้าโจทย์บอกว่ามีคำสั่งไม่เกินแสนคำสั่ง อาเรย์แสนช่องก็พอเสมอ โจทย์แข่งขันส่วนใหญ่เป็นแบบนี้ จึงใช้วิธีนี้ได้เกือบทุกครั้ง

queue วงกลม

แต่ถ้าที่มีจำกัดจริงๆ เช่น ร้านชานมมีเก้าอี้รอแค่ 3 ตัว ทั้งวันมีลูกค้าเป็นพันคน หรือโจทย์ที่คนออกจากหัวคิวแล้ววนกลับไปต่อท้ายซ้ำเป็นล้านรอบ tail จะเดินเลยท้ายอาเรย์ไปแม้คิวจะสั้นนิดเดียว วิธีแก้คือพอเดินถึงช่องสุดท้ายแล้ว ให้วนกลับไปช่อง 0 ซึ่งว่างแล้วเพราะคนตรงนั้นออกไปนานแล้ว อาเรย์จึงเหมือนต่อปลายเป็นวงกลม เรียกว่า circular queue

การวนกลับใช้ % จากหน้า 1.2 ถ้าอาเรย์มี capacity ช่อง ช่องถัดจาก i คือ (i + 1) % capacity ซึ่งเป็น i + 1 ตามปกติ ยกเว้นตอน i เป็นช่องสุดท้ายจะได้ 0

ในภาพ คิวคือ 104 105 106 ตามลำดับ ถึง 106 จะอยู่ช่องที่ index น้อยกว่าก็ตาม เพราะเดินจาก head ไปทางขวาแล้ววนกลับ

มีจุดที่ต้องคิดเพิ่มหนึ่งจุด ตอนคิวว่าง head == tail แต่ตอนคิวเต็มทุกช่อง tail ก็วนมาทับ head พอดี ได้ head == tail เหมือนกัน แยกสองกรณีนี้ไม่ออก วิธีที่อ่านง่ายที่สุดคือเก็บตัวแปร count นับจำนวนคนในคิวไว้อีกตัว

โปรแกรมนี้จำลองร้านชานมที่มีเก้าอี้รอ 3 ตัว คำสั่ง A x คือลูกค้าหมายเลข x มาถึง ถ้าเก้าอี้เต็มเขาจะกลับไป คำสั่ง S คือทำชานมเสร็จหนึ่งแก้ว ให้ลูกค้าหัวคิว โปรแกรมพิมพ์ head กับ tail ออกมาด้วย จะได้เห็นการวนกลับ

#include <stdio.h>

int seat[3];
int capacity = 3;
int head = 0, tail = 0, count = 0;

int main()
{
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        char command;
        scanf(" %c", &command);
        if (command == 'A') {
            int customer;
            scanf("%d", &customer);
            if (count == capacity) { // (1)!
                printf("%d leaves, no seat\n", customer);
            } else {
                seat[tail] = customer;
                tail = (tail + 1) % capacity; // (2)!
                count++;
                printf("%d waits, head %d tail %d\n", customer, head, tail);
            }
        } else {
            if (count == 0) { // (3)!
                printf("nobody to serve\n");
            } else {
                int customer = seat[head];
                head = (head + 1) % capacity;
                count--;
                printf("serve %d, head %d tail %d\n", customer, head, tail);
            }
        }
    }
    return 0;
}

เช็กเต็มก่อนใส่ทุกครั้ง ถ้าไม่เช็ก ลูกค้าใหม่จะไปนั่งทับคนหัวคิว
เลื่อน tail แบบวนกลับ head ก็เลื่อนด้วยสูตรเดียวกัน
เช็กว่างก่อนเอาออกทุกครั้ง เหมือน pop ของ stack

10
A 101
A 102
A 103
A 104
S
A 105
S
S
S
S

101 waits, head 0 tail 1
102 waits, head 0 tail 2
103 waits, head 0 tail 0
104 leaves, no seat
serve 101, head 1 tail 0
105 waits, head 1 tail 1
serve 102, head 2 tail 1
serve 103, head 0 tail 1
serve 105, head 1 tail 1
nobody to serve

ดูบรรทัดที่ 3 พอ 103 นั่ง tail วนกลับเป็น 0 ซึ่งเท่ากับ head ตอนนั้นคิวเต็ม ส่วนบรรทัดสุดท้ายก่อน nobody head กับ tail ก็เท่ากันที่ 1 แต่ตอนนั้นคิวว่าง ถ้าไม่มี count สองสถานการณ์นี้จะดูเหมือนกันทุกอย่าง ลูกค้า 105 นั่งช่อง 0 ที่ 101 เพิ่งลุกไป อาเรย์สามช่องจึงรับลูกค้าได้ไม่จำกัดตราบใดที่รอพร้อมกันไม่เกินสามคน

deque เข้าออกได้ทั้งสองหัว

deque อ่านว่า เด็ค ย่อมาจาก double-ended queue คือคิวที่เพิ่มและเอาออกได้ทั้งหัวและท้าย ใช้แทนได้ทั้ง stack และ queue ทำด้วย circular queue ได้เลย เพิ่มแค่สองงาน

เพิ่มที่หัว ถอย head ไปหนึ่งช่องแบบวนกลับ แล้วใส่ค่า
เอาออกที่ท้าย ถอย tail ไปหนึ่งช่องแบบวนกลับ แล้วอ่านค่า

การถอยแบบวนกลับต้องเขียน (head - 1 + capacity) % capacity ต้องบวก capacity ก่อน mod เพราะตอน head เป็น 0 ค่า head - 1 ติดลบ และหน้า 1.2 บอกไว้แล้วว่า % ของเลขติดลบได้ผลติดลบ

ตัวอย่าง ห้องฉุกเฉินมีหมอหนึ่งคน คนไข้ทั่วไป (N x) ต่อท้ายคิว คนไข้อาการหนัก (U x) ได้ไปอยู่หัวคิว หมอเรียกคนหัวคิว (D) และบางครั้งคนท้ายคิวรอไม่ไหวกลับบ้านไปก่อน (L)

#include <stdio.h>

int deque[100000];
int capacity = 100000;
int head = 0, tail = 0, count = 0;

void push_back(int x)
{
    deque[tail] = x;
    tail = (tail + 1) % capacity;
    count++;
}

void push_front(int x)
{
    head = (head - 1 + capacity) % capacity; // (1)!
    deque[head] = x;
    count++;
}

int pop_front(void)
{
    int x = deque[head];
    head = (head + 1) % capacity;
    count--;
    return x;
}

int pop_back(void)
{
    tail = (tail - 1 + capacity) % capacity; // (2)!
    count--;
    return deque[tail];
}

int main()
{
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        char command;
        scanf(" %c", &command);
        if (command == 'N' || command == 'U') {
            int patient;
            scanf("%d", &patient);
            if (command == 'N') {
                push_back(patient);
            } else {
                push_front(patient);
            }
        } else if (count == 0) {
            printf("no patient\n");
        } else if (command == 'D') {
            printf("doctor sees %d\n", pop_front());
        } else {
            printf("%d goes home\n", pop_back());
        }
    }
    return 0;
}

ถอยก่อนแล้วค่อยใส่ เพราะ head ชี้คนหัวคิวที่มีอยู่แล้ว ช่องว่างอยู่ก่อนหน้ามัน ครั้งแรกที่เรียก head เป็น 0 จะวนไปช่อง 99999
กลับด้านกับ push_back ทุกอย่าง tail ชี้ช่องว่าง คนท้ายคิวอยู่ช่องก่อนหน้ามัน

9
N 21
N 22
U 23
N 24
D
L
D
D
D

doctor sees 23
24 goes home
doctor sees 21
doctor sees 22
no patient

หลังสี่คำสั่งแรก คิวคือ 23 21 22 24 คนไข้ 23 มาทีหลังแต่ได้ตรวจก่อน และ 24 ออกทางท้ายโดยไม่ต้องรอ ในบทที่ 17 จะมี deque สำเร็จรูปของ C++ ให้ใช้ แต่ข้างในทำงานแบบเดียวกับที่เขียนเองตรงนี้

ลองทำให้พัง

แบบที่ 1 ลืมเลื่อน head

เขียน dequeue ให้คืนค่าหัวคิวแต่ลืมบรรทัด head++;

#include <stdio.h>

int queue[100000];
int head = 0, tail = 0;

void enqueue(int x)
{
    queue[tail] = x;
    tail++;
}

int dequeue(void)
{
    return queue[head];
}

int main()
{
    enqueue(11);
    enqueue(12);
    enqueue(13);
    printf("dequeue = %d\n", dequeue());
    printf("dequeue = %d\n", dequeue());
    printf("dequeue = %d\n", dequeue());
    printf("size = %d\n", tail - head);
    return 0;
}

dequeue = 11
dequeue = 11
dequeue = 11
size = 3

คนหัวคิวได้ชานมซ้ำไม่จบ คิวไม่สั้นลงเลย ถ้าโปรแกรมมีลูป while (!is_empty()) แบบโปรแกรม queue-basics ลูปจะไม่มีวันหยุด เพราะ head ไม่มีวันไล่ทัน tail ฟังก์ชันนี้กลายเป็น front ไปแล้ว ไม่ใช่ dequeue

แบบที่ 2 คิววงกลมเต็มแล้วดูเหมือนว่าง

ตัด count ทิ้งแล้วใช้ head == tail ตรวจว่าว่างแบบคิวธรรมดา

#include <stdio.h>

int seat[3];
int capacity = 3;
int head = 0, tail = 0;

void enqueue(int x)
{
    seat[tail] = x;
    tail = (tail + 1) % capacity;
}

int is_empty(void)
{
    return head == tail;
}

int main()
{
    enqueue(101);
    printf("after 101: empty = %d\n", is_empty());
    enqueue(102);
    printf("after 102: empty = %d\n", is_empty());
    enqueue(103);
    printf("after 103: empty = %d\n", is_empty());
    return 0;
}

after 101: empty = 0
after 102: empty = 0
after 103: empty = 1

มีคนรอครบสามคน แต่โปรแกรมบอกว่าว่าง ร้านจะไม่ทำชานมให้ใครเลย และถ้ามีลูกค้าคนที่สี่ เขาจะได้นั่งทับลูกค้า 101 เพราะไม่มีอะไรบอกว่าเต็ม ใช้ count เสมอ

แบบที่ 3 ถอยหลังโดยไม่บวก capacity

#include <stdio.h>

int main()
{
    int capacity = 8;
    int head = 0;
    printf("%d\n", (head - 1) % capacity);
    printf("%d\n", (head - 1 + capacity) % capacity);
    return 0;
}

-1
7

ถ้าใช้สูตรแรกใน push_front ครั้งแรกจะเขียนลง deque[-1] ซึ่งอยู่นอกอาเรย์ ผลเป็นได้ทุกแบบในหน้า 5.5 ตั้งแต่ค่าดูปกติไปจนถึงโปรแกรมพัง และ compiler ไม่เตือนอะไรเลย

สรุป

queue เข้าก่อนออกก่อน เข้าทางท้าย ออกทางหัว
queue ด้วยอาเรย์ใช้ head กับ tail ที่เดินไปข้างหน้าอย่างเดียว อาเรย์ต้องมีช่องเท่าจำนวน enqueue ทั้งหมด
ที่จำกัดหรือวนซ้ำมาก ใช้ circular queue เลื่อนด้วย (i + 1) % capacity และนับ count แยกว่างกับเต็ม
deque เพิ่มลบได้ทั้งสองหัว ถอยด้วย (i - 1 + capacity) % capacity
dequeue ต้องเลื่อน head เช็กว่างก่อนเอาออก และเช็กเต็มก่อนใส่

กลับไปเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด