Circular Queue

วันนี้ผมนำเสนอแปลกๆ นะ บทความวันนี้เสนอเรื่อง Circular Queue โดยนำเสนอในรูปแบบ Q&A นะครับ ลองติดดามได้นะครับ ^__^

Q: ทำไมถึงต้องมี Circular Queue
A: เพราะ ว่างการใช้ queue แบบเดิม จะทำให้เสียเนื้อที่ใส่ส่วนด้านหน้าไป โดยเปล่าประโยชน์ หลังจากที่ enqueue ออกแล้ว ถึงแล้วว่าจะมีการสร้าง queue ใหม่ชึ้นมา ระบบก็จะจองเนื้อที่ในหน่วงความจำใหม่แทน ลองดูแผนภาพประกอบ

Q: แล้วใช้ Circular Queue จะแก้ปัญหาในข้อที่แล้วได้อย่างไร
A: ลองเปลี่ยนวิธีการเขียนจากการเขียนที่เรามองว่าคิว คือ แถวยาวๆ มามองให้เป็นวงกลม โดยมีการปรับเปลี่ยนในส่วนของโปรแกรม เพื่อสามารถที่จะทำ Circular Queue ลองดูแผนภาพประกอบ

Q: แล้วเราจะรู้ได้อย่างไร ว่า Queue มันเต็ม หรือยัง หรือตอนนี้ยังใส่ได้อีกเท่าไหร่
A: ขอตอบแยกเป็นข้อๆ ดังนี้ครับ

• ถ้าเป็น array ลองใช้ค่า index ให้เป็นประโยชน์ หรือจะสร้างตัวแปรอีกอันนึงขึ้นมานับก็ได้
• ถ้าเป็น linked list ก็ต้องสร้างตัวแปรขึ้นมานับ ถึงแม้ว่าlinked list จะมีโอกาสที่จะเต็มยาก แต่ถ้าเป็นงานใหญ่ๆ ก็มีโอกาสเต็มได้เหมือนกัน

ลอง Implement Code

• ผมมีการใช้ interface queueADT เพื่อกำหนดกรอบการทำงานว่า Circular Queue มีการทำงานอะไรบ้าง โดยตัว Interface queueADT สามารถนำไปใช้ต่อได้ ถ้านำไป implement queue แบบอื่นๆครับ

public interface queueADT {
    public void enqueue(Object data)throws Exception;
    public Object dequeue()throws Exception;
    public boolean empty();
    public boolean full();
    public int length();
    public void clear();
}

• ต่อมาเป็นการ Implement ArrayCirQueue โดยมีการอธิบายรายละเอียดใน Session ถัดไปครับ

ArrayCirQueue implements queueADT
{
    Object Obj[];
    int total;
    int head,tail,qsize;
    ArrayCirQueue(int size)
    {
        Obj = new Object[size];
        this.qsize = size;
        head = -1;
        tail = 0; //ชี้ข้อมูลตัวแรก เพื่อที่จะได้เอาไปเข้าคิว
        total = 0;
    }
    public void enqueue(Object data)throws Exception
    {
        if(full())
        {
            throw new Exception("Queue is full");
        }
        else
        {
            Obj[tail] = data;
            tail = (tail+1)%qsize;
            total++;
            //System.out.println("head: "+head+" tail: "+tail+" total: "+total);
 
        }
 
    }
    public Object dequeue()throws Exception
    {
        Object data = null;
 
        if(empty())
            throw new Exception("Queue is empty");
        else
        {
            if(head==-1)
            {
                head++;
            }
            data = Obj[head];
            Obj[head] = null;
            head = (head+1)%qsize;
            total--;
            //System.out.println("head: "+head+" tail: "+tail+" total: "+total);
        }
        return data;
    }
    public boolean empty()
    {
        if(total==0)
            return true;
        else
            return false;
    }
    public boolean full()
    {
        if(total == qsize)
            return true;
        else
            return false;
    }
    public int length()
    {
        return total;
    }
    public void clear()
    {
        total = 0;
        head = -1;
        tail = 0; //ชี้ข้อมูลตัวแรก เพื่อที่จะได้เอาไปเข้าคิว
    }
}

อธิบาย Code ทีละส่วน

1. Data Member

Object Obj[]; //ประกาศให้มีข้อมูลเป็น Object ซึ่งถือว่าเป็น Class แม่ของ Object ทุกตัวใน java เพื่อที่จะรอรับข้อมูลได้ทุกรูปแบบ
int total; //นับจำนวนข้อมูลที่มีอยู่ใน queue
int head,tail,qsize; //ดูเพิ่มเติม

เพิ่มเติม: ใช้ head, tail และ qsize เป็นมือที่คอยจัดการภายใน queue ซึ่งจะมีชนิดข้อมูลแบบ integer เพื่อที่จะเก็บค่า index ของ array

2. Constructor

ArrayCirQueue(int size)
{
    Obj = new Object[size];
    this.qsize = size;
    head = -1;
    tail = 0; //ชี้ข้อมูลตัวแรก เพื่อที่จะได้เอาไปเข้าคิว
    total = 0;
}

3. Enqueue

public void enqueue(Object data)throws Exception
{
    if(full())
    {
        throw new Exception("Queue is full");
    }
    else
    {
        Obj[tail] = data;
        tail = (tail+1)%qsize; //ดูเพิ่มเติม
        total++;
        //System.out.println("head: "+head+" tail: "+tail+" total: "+total);
    }
}

เพิ่มเติม: เนื่องจากใน queue ข้อมูลจะเข้าทาง tail ทำให้ต้องมีการตรวจสอบว่า tail มันเกินขนาดของ array คือ ไม่ เพื่อไม่ให้เกิด ArrayOutofBound Exception และ ทำให้เป็นวงกลม โดยการ mod เพื่อที่จะเอาค่าเศษใช้ในการเลื่อน tail ไปในตำแหน่งเริ่มต้นของ Array ตามสูตร แต่ก็ต้องมีการตรวจสอบด้วยว่า queue เต็มหรือยังด้วย

tail = (tail+1) % qsize;

4. Dequeue

public Object dequeue()throws Exception
{
    Object data = null;
 
    if(empty())
        throw new Exception("Queue is empty");
    else
    {
        if(head==-1)//ตรวจสอบในกรณีที่ยังไม่มีการdequeue ออกมาก่อนเลย เพื่อที่จะได้เลื่อน head ไปชี้ข้อมูลตัวแรกของqueue
        {
            head++;
        }
        data = Obj[head];
        Obj[head] = null;
        head = (head+1)%qsize;
        total--;
        //System.out.println("head: "+head+" tail: "+tail+" total: "+total);
    }
    return data;
}

เพิ่มเติม: ลักษณะคล้ายกับ enqueue แต่จะเอาข้อมูลออกมาทาง head โดยเมื่อเอามาแล้วก็จะเพิ่มค่า head ไป โดย mod กับขนาดของ queue เพื่อไม่ให้มั่นใจว่าไม่เกิด exception และมีการตรวจสอบ queue ว่างด้วย

5. Empty & Full

public boolean empty()
{
    if(total==0)
        return true;
    else
        return false;
}
public boolean full()
{
    if(total == qsize)
        return true;
    else
        return false;
}

เพิ่มเติม: ใช้ค่าตัวแปร total มานับ และตรวจสอบ full

6. Length

public int length()
{
    return total;
}

7. Clear

public void clear()
{
    total = 0;
    head = -1;
    tail = 0; //ชี้ข้อมูลตัวแรก เพื่อที่จะได้เอาไปเข้าคิว
}

เพิ่มเติม: หลักการของมันก็ คือ ทำให้มือที่จัดการ คือ head และ tail มีค่า 0 และ -1 ตามลำดับ และไป set ค่า total = 0 โดยไม่ต้องสนใจข้อมูลที่อยู่ด้านในว่าจะต้องไปไล่ set ให้เป็น null