ไปหน้าแรก | สารบัญ | Laploy.com | ระเบียนบทความ | บทความจากลาภลอย
คิวสวยด้วย C#
บทความโดย : ลาภลอย วานิชอังกูร (laploy.com)
ในบทความตอนที่แล้วผู้เขียนเสนอวิธีสร้าง Stack ด้วยภาษา C# บทความตอนนี้ก็เป็นเรื่องของโครงสร้างข้อมูลอีกเช่นกัน แต่คราวนี้เราจะมาดูวิธีสร้าง “คิว” (Queue) โดยใช้ภาษา C# กันบ้าง สิ่งที่ท่านจะได้เรียนรู้จากบทความตอนนี้คือ
- หลักการทำงานของโครงสร้างข้อมูลแบบคิว
- วิธีนิยามคลาสคิวด้วยภาษา C#
- วิธีทำ constructor overloading
- วิธีใช้งาน generic queue ของ .NET Framework
แบบนี้ที่เรียกว่าคิว
โครงสร้างข้อมูลแบบคิว (queue data structure) มีหลักการทำงานเหมือนตอนเราไปเข้าแถวชำระเงินค่าของชำในร้านสะดวกซื้อ ผู้ที่เข้าไปในคิวคนแรกจะได้อยู่หน้าสุด ผู้ที่เข้าคิวภายหลังจะอยู่ต่อจากคนแรก (และถัดมาเรื่อย) ตามปรกติผู้ที่เข้าคิวก่อนจะได้ออกจากคิวก่อนเสมอ ตามหลักการที่เรียกว่า First in, first out หรือเรียกย่อว่า FIFO เมื่อคนแรกออกจากคิวไปแล้ว ผู้ที่อยู่ต่อจากคนแรกจะได้เลื่อนตำแหน่งมาเป็นคนแรกบ้าง
การเขียนโปรแกรมสร้างคิว เราจะใช้อาร์เรย์เป็นตัวเก็บพักข้อมูล และจะแตกต่างจากคิวของมนุษย์ ตรงแทนที่จะเป็นแถวตรง เรากลับทำเป็นวงกลม (Circular buffer) ข้อมูลแรกที่ออกจากคิวไปแล้วจะไม่ถูกลบจากอาร์เรย์ เราจะใช้วิธีเลื่อนตัวชี้หัวคิวและตัวชี้ท้ายคิว แทน การเลื่อนตัวชี้สองตัวนี้จะเป็นสิ่งกำหนดว่าหน่วยใดของอาร์เรย์ (หน่วยของอาร์เรย์คือ Array Element ต่อไปจะเรียกย่อว่า AE) มีตำแหน่งเป็นหัวคิวและท้ายคิว จุดสำคัญที่ต้องเข้าใจคือคิวไม่ใช่อาร์เรย์ คิวเป็นกลไกที่เราสร้างขึ้นโดยอาศัยอาร์เรย์เป็นที่เก็บพักข้อมูล
คิวในคอมพิวเตอร์ต่างจากคิวในซุปเปอร์มาร์เก็ตตรงที่เราจับส่วนหัวกับส่วนท้ายมาต่อกันเป็นวงกลม เลขศูนย์ถึงเจ็ดที่เห็นคือค่าดรรชนีของอาร์เรย์ ไม่ใช่ตำแหน่งของคิว ตำแหน่งของคิวจะถูกกำหนดโดยตัวชี้ซึ่งจะถูกปรับค่าทุกครั้งที่มีการเข้าคิวและออกคิว
การเข้าคิว
การนำข้อมูลใส่ในคิวเรียกว่าการเข้าคิว หรือ enqueue การเข้าคิวต้องนำข้อมูลไปต่อท้ายแถว เราจึงต้องสร้างตัวชี้ตำแหน่งท้ายแถวชื่อ back ตัวเลขที่มันเก็บคือค่าดรรชนีของอาร์เรย์ ยกตัวอย่างเช่นเมื่อโปรแกรมเริ่มทำงาน ค่าของ back จะเท่ากับ 0 เมื่อมีการเข้าคิวเราจะนำข้อมูลไปใส่ที่ AE 0 จากนั้นเราต้องเพิ่มค่า back ขึ้นหนึ่ง เมื่อมีการเข้าคิวอีกครั้งข้อมูลจะถูกเก็บไว้ที่ AE 1 และเพิ่มค่า back อีกเช่นนี้เรื่อยไป จนกระทั้งค่า back เท่ากับ AE สุดท้ายของอาร์เรย์ ค่า back จะกลับเป็นศูนย์ใหม่ วิธีทำให้ค่า back วนเป็นวงกลมเช่นนี้ทำได้โดยใช้วิธีหารเอาเศษ (หรือ modulo ในภาษา C# ใช้สัญลักษณ์ %) สูตรจะเป็นดังนี้
back = (back + 1) % size
ยกตัวอย่างเช่น หาก size เป็นแปด เมื่อโปรแกรมเริ่มทำงานค่าของ back จะถูกทำให้เป็นศูนย์ จากนั้นจะเพิ่มขึ้นหนึ่งทุกครั้งที่มีการเข้าคิว (คือกลายเป็น 1, 2, 3, 4… ไปจนถึง 6) เมื่อ back มีค่าเท่ากับ 7 หากนำมาแทนค่าในสูตรจะได้เป็น
back = (7 + 1) % 8
back = 8 % 8
back = 0
จะเห็นว่าค่าที่ได้จะกลายเป็น 0 เหมือนตอนเริ่มโปรแกรม จากนั้นเมื่อมีการเข้าคิวอีก ค่าของ back ก็จะกลายเป็น 1, 2, 3.. ไปเรื่อยๆ วนเวียนไปเช่นนี้ไม่มีวันจบ สิ่งสำคัญคือก่อนเข้าคิวต้องตรวจสอบก่อนว่าคิวเต็มแล้วหรือไม่
การออกคิว
การนำข้อมูลออกจากคิวเรียกว่า “การออกคิว” หรือ dequeue การออกคิวไม่จำเป็นต้องลบข้อมูลออกจากอาร์เรย์ เราเพียงแค่เพิ่มค่าตัวชี้หัวคิวก็พอ เราจึงต้องสร้างตัวชี้หัวคิวชื่อ front และเพิ่มค่าตัวแปรนี้ทุกครั้งที่มีการออกคิว เนื่องจากคิวมีการทำงานวนเป็นวงกลม การออกคิวจึงใช้สูตรคล้ายการเข้าคิวดังนี้
front = (front + 1) % size
ผู้เขียนจะไม่อธิบายสูตร เพราะเหมือนกับการเข้าคิว แต่สิ่งสำคัญคือ ก่อนที่โปรแกรมจะออกคิวมันต้องตรวจสอบให้แน่ใจก่อนว่าในคิวมีข้อมูลให้ออก ไม่ใช่ว่าในคิวว่างเปล่าแล้วเราพยายามออกคิว อย่างนี้ต้องเกิด error อย่างแน่นอน
นิยามคลาส Queue
ผู้เขียนนิยามคลาสสำหรับสร้างคิวชื่อคลาส Queue ไว้แล้ว เมื่อดูในโครงสร้างแบบ outline จะเป็นดังที่เห็นในภาพ ผู้เขียนแบ่งโค้ดออกเป็นกลุ่มๆ ตามประเภทของสมาชิก (โดยใช้การเว้นบรรทัด) จะเห็นว่าคลาส Queue มีสมาชิกหลายแบบคือ constant, ฟิลด์, constructor และเมธอด ซึ่งมีรายละเอียดดังต่อไปนี้
โครงสร้างแบบ outline ของคลาสคิว
Constant
ผู้เขียนนิยาม constant (ตัวคงค่า หรือตัวเก็บค่าคงที่) ชื่อ default_size ทำหน้าที่เก็บค่าโดยปริยายของขนาดคิว เพื่อป้องกันการเกิด error ในกรณีที่ผู้นำคลาสนี้ไปสร้าง object ลืมกำหนดขนาดของคิว
private const int default_size = 8;
อันที่จริง constant ไม่ใช่สมาชิกของคลาส เมื่อตัวแปลภาษาพบคำสั่ง const มันจะนำค่าของ constant ไปกำหนดให้โค้ดส่วนที่อ้างถึง constant นั้น ตัวแปลภาษาจะไม่จองเนื้อที่ในหน่วยความจำเพื่อเก็บข้อมูลของ constant (เหมือนอย่างที่ทำกับตัวแปร) constant จึงไม่มีตัวตนอยู่ในโปรแกรมที่คอมไพล์แล้ว ทำให้มันไม่เป็นสมาชิกของ object
ฟิลด์สมาชิก
ผู้เขียนกำหนดให้ฟิลด์ทุกตัวมี access modifier เป็นแบบ private โปรดสังเกตว่าเราสามารถละคำว่า private (ไม่ใส่) ก็ได้ เพราะในภาษา C# หากไม่กำหนด access modifier ตัวแปลภาษาจะถือว่าตัวแปรนั้นเป็น private ไปโดยปริยาย
private int size;
private int front;
private int back;
private int[] values;
ฟิลด์ size ทำหน้าที่เก็บขนาดของคิว ค่าของ size จะไม่เปลี่ยนแปลงตลอดการทำงาน ฟิลด์ front ทำหน้าที่เป็นตัวชี้ตำแหน่งแรกของคิว อย่าลืมว่าตำแหน่งแรกของคิวไม่ใช่ตำแหน่งแรกของอาร์เรย์ (คือ AE ที่ 0) เสมอไป แต่ตำแหน่งแรกของคิวจะเปลี่ยนไปเรื่อยๆ เมื่อมีการเข้า-ออกคิว เพราะคิวเป็นสิ่งที่มีพลวัต ฟิลด์ back ทำหน้าที่เป็นตัวชี้ท้ายแถวของคิว ค่าของมันจะเปลี่ยนแปลงไปเมื่อมีการเข้า-ออกคิวเช่นกัน สุดท้ายคือ values เป็นอาร์เรย์ทำหน้าที่เป็นตัวเก็บข้อมูลในคิว (เป็นตัวพักข้อมูลหรือ data buffer)
Default Constructor
ผู้เขียนนิยาม constructor (ต่อไปจะเรียกว่า mc) ไว้สองแบบ แบบแรกเป็นแบบไม่มีอาร์กิวเมนต์ เรียกว่า default mc มีโค้ดดังนี้
public Queue(): this(default_size)
{
}
จะเห็นว่า default mc ไม่มีโค้ดอะไร เพียงกำหนดให้มันไปเรียก mc แบบที่สองอีกทอดหนึ่ง ผลลัพธ์ของโค้ดนี้คือหาก CC สร้าง object โดยไม่ระบุขนาดของคิว โปรแกรมจะนำค่าโดยปริยาย (คือค่าจาก constant default_size) มาใช้เรียก mc ตัวที่สองที่จะอธิบายในหัวข้อต่อไป
(CC คือ Client Class หมายถึงคลาสที่นำคลาสนี้ไปสร้างออพเจ็กต์ใช้งาน)
Constructor overloading
mc ตัวที่สองเป็นแบบมีอาร์กิวเมนต์ สาเหตุที่ผู้เขียนทำ overload ก็เพื่อป้องกันไม่ให้เกิด error ในกรณีที่ CC สร้าง object โดยไม่กำหนดขนาดของคิว
public void Queue(int size)
{
this.size = size;
values = new int[size];
front = 0;
back = 0;
}
โค้ดบรรทัดแรก this.size = size อาจทำให้บางคนงง เพราะเข้าใจว่าเรานำค่าจากตัวแปรมากำหนดให้ตัวมันเอง อันที่จริงไม่ใช่ ตัวแปร this.size คือฟิลด์สมาชิก ส่วนตัวแปร size ที่อยู่ทางขวาของเครื่องหมายเท่ากับคือตัวแปรพารามิเตอร์ ซึ่งมีภาวะเป็นตัวแปรท้องถิ่นของคลานี้
นี่คือวิธีจัด “ขอบเขตของตัวแปร” (variable scope) ในภาษา C# จำง่ายๆ คือโค้ดทุกแห่งในคลาสามารถเข้าถึงฟิลด์ได้ทั้งหมด แต่ตัวแปรที่ถูกประกาศไว้ใน block ใด (block หมายถึงระหว่างเครื่องหมายปีกกาสองอัน) จะมีขอบเขตอยู่ภายใน block นั้นเท่านั้น
ด้วยเหตุนี้โค้ดบรรทัดแรก this.size = size จึงทำหน้าที่นำค่าที่ CC ส่งมา (ตอนสร้าง object) ไปกำหนดขนาดของคิว คำสั่งบรรทัดต่อมา values = new int[size] กำหนดขนาดของอาร์เรย์ (ซึ่งจะใช้เพื่อเป็นที่เก็บข้อมูล) ให้มีขนาดเท่ากันกับคิวด้วย และคำสั่งสองบรรทัดสุดท้าย กำหนดค่าเริ่มต้นให้แก่ฟิลด์ front และ back ให้เป็นศูนย์ เพราะเมื่อเริ่มต้นคิวจะว่างเปล่า หัวคิวและท้ายคิวจึงมีตำแหน่งเดียวกัน
การตรวจสอบว่าคิวเต็มหรือไม่
ก่อนเข้าคิวเราต้องดูว่าคิวเต็มหรือยัง ดังนั้นเราจึงจำเป็นต้องนิยามเมธอดชื่อ IsFull ซึ่งมีโค้ดดังนี้
public Boolean IsFull()
{
if ((back + 1) % size == front)
return true;
else
return false;
}
หัวใจของเมธอดนี้คือคำสั่ง if ทำหน้าที่ตรวจสอบว่าคิวเต็มหรือไม่ ซึ่งทำได้โดยดูว่าค่าของตัวชี้หัวคิว และตัวชี้ท้ายคิวกำลังจะทับกันหรือไม่ ลองดูตัวอย่างในภาพ
แสดงสภาพของอาร์เรย์และตัวชี้หัว-ท้ายคิวเมื่อคิวเต็ม
ในภาพนี้ front มีค่าเท่ากับ 5 นั้นคือหัวคิวอยู่ที่ AE5 ของอาร์เรย์ ข้อมูลแรกของคิวจึงอยู่ที่ AE5 ข้อมูลถัดไปของคิวจึงอยู่ใน AE6 และไล่ไปเช่นนี้ ขณะนี้คิวเต็มแล้ว back จึงอยู่ที่ AE4 เมื่อในค่าในตัวอย่างนี้มาแทนค่าตัวแปรในเงื่อนไขของคำสั่ง if จะได้เป็น
(back+1) % size == front
(4+1) % 8 == 5
5 % 8 == 5
5 == 5
ผลลัพธ์คือเงื่อนไขเป็นจริง แสดงว่าคิวเต็มแล้ว โปรแกรมจะส่ง return value เป็นบูลลีน true (จริง) ในกรณีที่คิวยังไม่เต็ม เงื่อนไขจะเป็นเท็จ โปรแกรมจะส่ง return value เป็น fault (เท็จ)
การตรวจสอบว่าคิวว่างเปล่าหรือไม่
เพื่อป้อนกันการ error เมื่อจะออกคิว เราจำเป็นต้องตรวจสอบว่าคิวว่างเปล่าหรือไม่เสียก่อน (หากคิวว่างเปล่าเราจะต้องไม่ทำการออกคิว) การตรวจสอบว่าคิวว่างเปล่าหรือไม่ทำได้ง่ายมาก เพราะหากคิวว่าง ตัวชี้ front และ back จะมีค่าเท่ากัน ดังนั้นเมธอด IsEmpty จึงมีโค้ดเพียงเท่านี้
public Boolean IsEmpty()
{
if (back == front)
return true;
else
return false;
}
เข้าคิวด้วยเมธอด EnQueue
การเข้าคิวทำได้ง่าย เพียงแค่เพิ่มค่าตัวชี้ท้ายคิว หรือฟิลด์ back จากนั้นใช้ back เป็นดรรชนีของอาร์เรย์ แล้วนำข้อมูลไปเก็บในอาร์เรย์ดังนี้
public void EnQueue(int x)
{
if (!IsFull())
{
back = (back + 1) % size;
values[back] = x;
}
}
จากโค้ดข้างบนให้สังเกตว่าเราจำเป็นต้องตรวจสอบก่อนว่าคิวเต็มหรือไม่ หากคิวเต็ม โค้ดที่เหลือในเมธอดจะไม่ทำงาน หากคิวยังไม่เต็ม เราจะเพิ่มค่า back แล้วทำ modulo เพื่อให้คิววนรอบอาร์เรย์เป็นวงกลมดังที่อธิบายไปแล้วตอนต้นบทความ
ออกคิวด้วยเมธอด DeQueue
การออกคิวทำได้โดยเพิ่มค่าตัวชี้หัวคิว หรือฟิลด์ front จากนั้นใช้มันเป็นดรรชนีของอาร์เรย์ แล้วนำข้อมูลไปเก็บในอาร์เรย์ดังนี้
public int DeQueue()
{
if (!IsEmpty())
{
front = (front + 1) % size;
return values[front];
}
return 0;
}
จากโค้ดข้างบนให้สังเกตว่าเราจำเป็นต้องตรวจสอบก่อนว่าคิวว่างหรือไม่ หากคิวว่าง คำสั่ง return บรรทัดล่างสุด (ก่อนวงเล็บปีกกาสุดท้าย) จะทำงานโดยส่ง return value เป็นศูนย์ หากคิวไม่ว่าง เราจะเพิ่มค่า front แล้วทำ modulo จากนั้นจะนำค่าใน AE ที่ชี้โดย front ส่งกลับไปเป็น return value
โปรแกรมทดสอบคิว
เมื่อนิยามคลาส Queue เสร็จแล้วเราต้องทดสอบการทำงานโดยเขียนโปรแกรมขึ้นดังนี้
static void Main(string[] args)
{
Queue myQueue = new Queue(5);
myQueue.EnQueue(10);
myQueue.EnQueue(20);
myQueue.EnQueue(30);
for (int i = 0; i < 3; i++)
Console.WriteLine(myQueue.DeQueue());
Console.ReadLine();
}
ผลลัพธ์การทำงานของโปรแกรมนี้คือ
10
20
30
โค้ดโดยสมบูรณ์ของคลาสคิว
เมื่อนำโค้ดทั้งหมดมารวมกันจะได้เป็นคลาสคิวที่สมบูรณ์ดังนี้
using System;
namespace NormalQueue
{
class Queue
{
private const int default_size = 8;
private int size;
private int front;
private int back;
private int[] values;
public Queue(): this(default_size)
{
}
public Queue(int size)
{
this.size = size;
values = new int[size];
front = 0;
back = 0;
}
public Boolean IsFull()
{
if((back+1) % size == front)
return true;
else
return false;
}
public Boolean IsEmpty()
{
if (back == front)
return true;
else
return false;
}
public void EnQueue(int x)
{
if (!IsFull())
{
back = (back+1) % size;
values[back] = x;
}
}
public int DeQueue()
{
if (!IsEmpty())
{
front = (front+1) % size;
return values[front];
}
return 0;
}
}
class Program
{
static void Main(string[] args)
{
Queue myQueue = new Queue(5);
myQueue.EnQueue(10);
myQueue.EnQueue(20);
myQueue.EnQueue(30);
for (int i = 0; i < 3; i++)
Console.WriteLine(myQueue.DeQueue());
Console.ReadLine();
}
}
}
คิวแบบ Generic
คลาส Queue ที่ผู้เขียนนิยามไว้ในหัวข้อที่ผ่านมา ใช้เพื่อศึกษาการทำงานของคิวเท่านั้น ในการใช้งานจริง .NET Framework มีคลาสไลบรารีที่จัดการคิวไว้ให้แล้ว (อยู่ใน namespace System.Collections.Generic) และดีกว่าคลาสที่เรานิยามในตัวอย่าง เพราะเป็นคิวแบบ Generic คือสามารถรับข้อมูล type อะไรก็ได้ โค้ดตัวอย่างการใช้งานเป็นดังนี้
static void Main(string[] args)
{
Queue<string> myQueue = new Queue<string>();
myQueue.Enqueue("abc");
myQueue.Enqueue("hello");
myQueue.Enqueue("thailand");
myQueue.Enqueue("bangkok");
while (myQueue.Count > 0)
Console.WriteLine(myQueue.Dequeue());
Console.ReadLine();
}
ผลลัพธ์การทำงานของโปรแกรมนี้คือ
abc
hello
thailand
bangkok
สรุปเรื่องการสร้างคิวในภาษา C#
การสร้างและใช้งานคิวในภาษา C# ทำได้ง่ายมากเพราะในคลาสไลบรารีของ .NET Framework มีคลาส Queue มาให้แล้ว ในบทความตอนนี้ผู้เขียนแสดงวิธีนิยามคลาส Queue ขึ้นเองเพื่อศึกษาการทำงานของคิวเท่านั้น
ผู้เขียนจัดทำโค้ดตัวอย่างประกอบบทความนี้ไว้เป็นไฟล์ชื่อ QInCSharp.zip (ภายในเป็น solution ที่สร้างจาก MS Visual Studio .NET 2005) ท่านสามารถดาวน์โหลดได้จากเว็บไซต์ของผู้เขียนที่ www.laploy.com (เลือกหัวข้อ download) หากท่านมีข้อสงสัยใดๆ โปรดโพสคำถามไว้ในเว็บบอร์ดที่เว็บไซต์ดังกล่าว
ลงทะเบียนโดยกรอกแบบฟอร์มลงทะเบียนด้านล่างของเพจนี้ 
OOP C# ASP.NET 