[Project Solution] Queue … step by step

บทความนี้เป็นบทความเก่า ย้ายบล๊อกมาจาก nartra.blogspot.com

Queue

ต้องการสร้างโปรแกรมสำหรับจำลองการเข้าแถวจ่ายเงินที่แคชเชียร์ เช่นตามซุปเปอร์มาร์เก็ตโดยมีกฎว่า

1.  จะมีแคชเชียร์หลักอยู่ 2 อันเสมอ
2. เวลาลูกค้าเดินมาถึงแคชเชียร์ (เพื่อจะจ่ายตังค์อ่ะนะ) ลูกค้าจะเลือกเข้าแถวที่สั้นที่สุด .. ถ้ามีแถวที่สั้นที่สุดหลายแถว (เช่น แถว 1 มีคนต่อแถวอยู่ 3 คน, แถว 2 มีคนต่อแถวอยู่ 3 คนเท่านั้นเลย จะเลือกเข้าแถวที่เลขน้อยกว่า ในกรณีนี้คือแถว 1 นะ)
3. แคชเชียร์แต่ละอัน รับลูกค้าได้อย่างมากสุดแค่ 5 คน
4. ถ้าลูกค้าเข้ามาเพิ่ม และแคชเชียร์ทุกตัวที่มีอยู่ในตอนนี้เต็มหมดแล้ว (ทุกแถวมี 5 คนเต็มเอี้ยด) จะมีการสร้างแถวแคชเชียร์ใหม่เพิ่มเข้ามาอีก 1 แถว
5. ถ้าแคชเชียร์คิดเงินลูกค้าเสร็จแล้วจะทำการลบลูกค้าออกจากหัวแถวไป .. ในกรณีนี้มีโอกาสที่แคชเชียร์ช่องนึงจะลบลูกค้าออกจากแถวไปจนไม่เหลือลูกค้าในแถวเลย เรียกว่ากลายเป็นแถวว่างกันเลยทีเดียว
6. ถ้าแคชเชียร์ลบลูกค้าออกไปจนกลายเป็นแถวว่าง และในตอนนั้นมีแถวว่างรวมทั้งหมดเกิน 3 แถว (รวมตัวมันเองที่เพิ่งจะว่างด้วย) .. แคชเชียร์ตัวที่เพิ่งจะว่างล่าสุดอ่ะ จะถูกลบทิ้งออกไป หายไปเลย
7. แต่ไม่ว่าจะยังไง ก็ห้ามลบแถวให้เหลือน้อยกว่า 2 (กลับไปดูข้อ 1)

โดยการสั่งว่ามีลูกค้าเพิ่มเข้ามาและแคชเชียร์คิดเงินเสร็จ (แล้วก็ลบลูกค้าออกจากคิวไป) จะแทนด้วยคำสั่งประมาณนี้
สมมุติให้คำสั่งจะถูกเก็บอยู่ใน text file ที่ชื่อว่า input.txt ละกัน

AddCustomer(10)
 0,1
 AddCustomer(2)
 AddCustomer(3)
 1,3
 0,4

• คำสั่ง AddCustomer(n) ใช้สำหรับบอกว่ามีลูกค้าเดินเข้ามาใหม่ n คน
• m,n ใช่สำหรับบอกว่า แคชเชียร์ตัวที่ m คิดเงินลูกค้าเสร็จแล้ว (และลบลูกค้าหัวแถวออกไป) จำนวนเท่ากัน n คน

ซึ่งคำสั่งจำลองเหตุการณ์พวกนี้อ่ะนะ ถ้าเอาไปรันแล้วจะให้ผลแบบนี้

POS 0 | 1 3 5 7 9
 POS 1 | 2 4 6 8 10
 =======================
 POS 0 | 3 5 7 9
 POS 1 | 2 4 6 8 10
 =======================
 POS 0 | 3 5 7 9 11
 POS 1 | 2 4 6 8 10
 POS 2 | 12
 =======================
 POS 0 | 3 5 7 9 11
 POS 1 | 2 4 6 8 10
 POS 2 | 12 13 14 15
 =======================
 POS 0 | 3 5 7 9 11
 POS 1 | 8 10
 POS 2 | 12 13 14 15
 =======================
 POS 0 | 11
 POS 1 | 8 10
 POS 2 | 12 13 14 15
 =======================

POS แทนแคชเชียร์ เบอร์ 0, 1, 2, .. ไปเรื่อยๆ
ซึ่งผลลัพท์จะแสดงสถานะของแคชเชียร์ทุกตัวที่มีอยู่ในตอนนั้นในแต่ละรอบ พร้อมจำนวนลูกค้าที่เข้าแถวอยู่
ลูกค้าจะแทนด้วย ตัวเลข อ่ะนะ คนที่หนึ่งก็เป็นเลข 1, คนต่อไปก็ 2 3 4 .. ไปเรื่อยๆ

หลักการ

คิว หรือ ที่ตำราไทยแปลว่า "แถวคอย"

คิวเป็น Data Structure ประเภทหนึ่ง ไม่ต้องอธิบายให้มากนักกับคิวเพราะเราเจอมันในชีวิตจริงอยู่แล้ว

เข้าแถวๆๆๆ

หลักการก็คือใครมาก่อน ก็ออกไปก่อน ใครมาหลักก็ออกไปที่หลัง ไม่ยากเลย หรือที่เราเรียกอีกแบบว่า FIFO (First-In, First-Out) ง๊ายง่าย

ถ้าพูดถึงสิ่งที่คิวน่าจะทำได้ก็คงมีจะมีประมาณ

• ใส่คนเพิ่มเข้าไป
• ถึงคนหัวแถวออกมา
• เช็กดูได้ว่าตอนนี้มีแถวมีกี่คน
• เช็กว่าแถวนี้เต็มรึยัง (ตามโจทย์ข้อนี้ ต้องมีความสามารถนี้ด้วย)

ซึ่งถ้าเขียนเป็น code ก็จะได้ประมาณนี้

public class Queue {
    public static final int MAX = 5;
    private ArrayList<Integer> q = new ArrayList<Integer>();
    
    public boolean enqueue(int n) {...}

    public int dequeue() {...}

    public int size() {...}

    public boolean avairable() {...}
}

ก็คือมี enqueue (เพิ่มคนเข้าไป), dequeue (ดึงหัวแถวออกมา), size (ถามขนาดว่าตอนนี้มีกี่คน), avairable (เช็กว่าใส่คนเข้าไปเพิ่มได้มั้ย ถ้าตอนนี้มีคนอยู่ 5 คนก็จะใส่ไม่ได้ไรเงี้ยอ่ะนะ)

ซึ่งจากโค้ดข้างบน MAX จะแทนจำนวนที่แคชเชียร์คิวนึงสามารถรับคนได้มากที่สุด ส่วนการเก็บคน (ลูกค้า) ในที่นี้ใช้ ArrayList ซึ่งเก็บ Integer (ตามโจทย์จะใช้ตัวเลขรันไปเรื่อยๆ แทนลูกค้าแต่ละคน)
สาเหตุที่ใช้ ArrayList แทน Array ก็เพราะว่าจำนวนคนในคิวมีการเปลี่ยนแปลงได้ ขนาดไม่เท่าเดิมตลอดเวลาจึงใช้ ArrayList ที่ไม่ฟิคเรื่องขนาดน่าจะดีกว่า

ส่วนการเพิ่มคนเข้าไปวิธีการทำก็คือรันคนใหม่ไป (เป็นหมายเลข Integer อ่ะนะ) แต่รับไปแล้วก็เช็กก่อนว่าตอนนี้คิวเรามันเต็มไปแล้วรึเปล่า ถ้าไม่เต็มก็ .add เข้าไปใน ArrayList ตัวเมื่อกี้นะ แต่ถ้ามันล้นแล้วก็อย่าใส่เข้าไป
ป.ล.จริงๆ method นี้สามารถเขียนแบบ void ก็ได้ แต่ในที่นี้จะใช้ boolean เพื่อส่งค่าตอบกลับด้วยว่ามันใส่เข้าไปในคิวได้รึเปล่า

public boolean enqueue(int n) {
    if (q.size() < MAX) {
        q.add(n);
        return true;
    }
    else {
        return false;
    }
} 

ต่อไปคือการดึงคนออกมาจากหัวแถว ก็เช็กก่อนว่าตอนนี้มีคนอยู่ในแถวม๊ะ (มีคนให้ดึงออกมารึเปล่านั่นแหละ) ถ้ามีก็ดึงออกมาแล้วลบข้อมูลตำแหน่งที่ 0 ซึ่งเป็นตำแหน่งหัวแถวทิ้งไป (ก็คนถูกดึงออกไปแล้วอ่ะนะ)

public int dequeue() {
    if (q.size() > 0) {
        int result = q.get(0);
        q.remove(0);
        return result;
    }
    else {
        return -1;
    }
}

ต่อไปคือการถามว่าตอนนี้มีคนกี่คนในแถว ก็ไม่ยากเลย ใน ArrayList เรามีอยู่เท่าไหร่ก็เท่านั้นแหละ

public int size() {
    return q.size();
}

ส่วนตัว avairable คือการเช็กว่าคิวนี้เหลือที่มั้ย ดังนั้นถ้าจำนวนคนใน ArrayList เรามันน้อยกว่าจำนวนมากสุดที่รับได้ก็ถือว่ามันยังว่างอยู่ ใส่คนเพิ่มมาได้เลยนะถ้าอยากใส่

public boolean avairable() {
    return q.size() < MAX;
}

ส่วนอันสุดท้ายอันนี้เป็นอันแถม เป็น method สำหรับปริ้นข้อมูล (หมายเลขลูกค้าในคิวนั่นแหละ) ออกมา ซึ่งก็วน loop ไปให้ครบทุกตัวก็จบแล้ว

public void display() {
    System.out.print("POS " + serial_number + " | ");
    for (int i = 0; i < q.size(); i++) {
        System.out.print(q.get(i) + " ");
    }
    System.out.println();
} 

กลับมาที่ main

อ่านคำสั่งว่าต้องทำอะไรบ้างจาก text file

เพราะว่าคำสั่งของเราอยู่ใน text file เราเลยต้องอ่านคำสั่งพวกนั้นมาก่อน ซึ่งถ้าจะทำให้ง่ายก็ควรอ่านมาแล้วสร้างเป็น array ของ String ไปเลย จะได้เอาไปใช้ต่อได้ง่าย
ก็จัดการสร้าง method ใน class หลักที่จะใช้เรียกซะ

String[] readfile(String filename) {
    String[] result;
    try {
        Scanner scan = new Scanner(new FileReader(filename));
        ArrayList<String> readtext = new ArrayList<String>();
        while (scan.hasNextLine()) {
            readtext.add(scan.nextLine());
        }
        result = new String[readtext.size()];
        result = readtext.toArray(result);
    }
    catch (Exception e) {
        result = new String[0];
    }
    return result;
}

ทำการประมวลผลคำสั่งว่ามันเป็น enqueue หรือ dequeue

String[] commands = readfile("index.txt");

commands[0]เก็บค่า: AddCustomer(10)
 commands[1]เก็บค่า: 0,1
 commands[2]เก็บค่า: AddCustomer(2)
 commands[3]เก็บค่า: AddCustomer(3)
 commands[4]เก็บค่า: 1,3
 commands[5]เก็บค่า: 0,4

int UNKNOWN = 0, ENQUEUE = 1, DEQUEUE = 2;

int typeOfCommand(String str) {
    str = str.trim();
    String enqueue_format = "^(AddCustomer)\\([0-9]+\\)$";
    String dequeue_format = "^([0-9]+)(,)([0-9]+)$";

    Pattern pattern;
    Matcher matcher;

    pattern = Pattern.compile(enqueue_format);
    matcher = pattern.matcher(str);
    if (matcher.find()) {
      return ENQUEUE;
    }

    pattern = Pattern.compile(dequeue_format);
    matcher = pattern.matcher(str);
    if (matcher.find()) {
      return DEQUEUE;
    }

    return UNKNOWN;
}

enqueue_format = "^(AddCustomer)\\([0-9]+\\)$";

dequeue_format = "^([0-9]+)(,)([0-9]+)$";

matcher = pattern.matcher(str)

UNKNOWN, ENQUEUE, DEQUEUE แล้วแต่ว่าตรงกับรูปแบบไหน

ประกาศค่าตัวแปรที่จะต้องใช้กันสักหน่อย

private static int order_of_queue = 0;
private ArrayList<Queue> cashiers = new ArrayList<Queue>();

แล้วก็มาถึงการเขียน main

class Main{
     private static int order_of_queue = 0;
     private ArrayList<Queue> cashiers = new ArrayList<Queue>();
     private static String[] readfile(String filename) {...}
     private static int UNKNOWN = 0, ENQUEUE = 1, DEQUEUE = 2;
     private static int typeOfCommand(String str) {...}
 
     public static void main(String[] args){
         int customer_no = 1;
         //เดี๋ยวทำต่อตรงนี้นะ
     }
}

//สร้างคิวแรก
 cashiers.add(new Queue(order_of_queue++));
//สร้างคิวที่สอง
 cashiers.add(new Queue(order_of_queue++));

public int serial_number;public Queue(int serialNumbar) {
    serial_number = serialNumbar;
}

for (i = 0; i < copmmands.length; i++) {
    switch (typeOfCommand(copmmands[i])) {
        case ENQUEUE:            
          //มีการเพิ่มลูกค้ามาใหม่
          break;
        case DEQUEUE:
          //ลบลูกค้าออกไปจากแถว
          break;
    }
}

enqueue

int n = Integer.parseInt(copmmands[i].replace("AddCustomer(", "").replace(")", ""));
for (c = 0; c < n; c++) {
    int position_to_enqueue = 0;
    for (j = 0; j < cashiers.size(); j++) {
        if (cashiers.get(j).size() < cashiers.get(position_to_enqueue).size() && cashiers.get(j).avairable()) {
            position_to_enqueue = j;
        }
    }
    if (!cashiers.get(position_to_enqueue).enqueue(customer_no)) {
       cashiers.add(new Queue(order_of_queue++));
       cashiers.get(cashiers.size() - 1).enqueue(customer_no);
    }
    customer_no++;
}

if( enqueue ไม่ได้ ){
 สร้างแถวใหม่
}

if( ! cashiers.get(position_to_enqueue).enqueue(customer_no)){
 cashiers.add(new Queue(order_of_queue++));
}

cashiers.get(cashiers.size() - 1).enqueue(customer_no);

dequeue

String[] pos_and_n = cmd[i].split(",");
pos = Integer.parseInt(pos_and_n[0]);
n = Integer.parseInt(pos_and_n[1]);
for (j = 0; j < cashiers.size(); j++) {
 if (cashiers.get(j).serial_number == pos) {
 for (k = 0; k < n; k++) {
  cashiers.get(j).dequeue();
 }
 //removeEmptyQueue(j);
 }
}

int empty = 0;
for (i = 0; i < cashiers.size(); i++) {
 if( cashiers.get(i).size() == 0 ){
  empty++;
 }
}
if (empty > REMOVE_EMPTY_N && cashiers.size() > MIN_CASHIER) {
 cashiers.remove(j); //jก็คือตำแหน่งแคชเชียร์สุดท้ายที่ลบลูกค้าออก
}

• จำนวนแถวว่างมากกว่า REMOVE_EMPTY_N (ในกรณีนี้คือ 2)
• จำนวนแคชเชียร์ในตอนนี้มากกว่าจำนวนน้อยสุด MIN_CASHIER ที่โจทย์อนุญาต(ในกรณีนี้คือ 2 อีกเหมือนกัน)

for (i = 0; i < copmmands.length; i++) {
  switch (typeOfCommand(copmmands[i])) {
    //นั่นแหละ
  }
}

โดยการเติม

for (j = 0; j < cashiers.size(); j++) {
  cashiers.get(j).display();
}
System.out.println("=======================");

ถือจบทุกอย่าง เรียบร้อย ดูไม่ยากเนอะ (แค่เยอะ) 555

* ขอไม่รวม code ให้ละกัน ลองอ่านตามดูแล้วทำไปเรื่อยๆ step by step