สร้าง Stack ด้วย C#

ไปหน้าแรก | สารบัญ | Laploy.com |  ระเบียนบทความ | บทความจากลาภลอย

สร้าง Stack ด้วย C#

บทความโดย : ลาภลอย วานิชอังกูร จากนิตยสาร Windows IT Pro ฉบับ July 2007

นักเขียนโค้ดจำนวนมากคิดว่าภาษา C# ใช้เขียนโปรแกรมสร้าง Stack ไม่ได้ การสร้าง Stack จำเป็นต้องเขียนด้วยภาษาซีหรือภาษา C++ เท่านั้น ความเข้าใจเช่นนั้นผิด เราสามารถใช้ภาษา C# สร้าง Stack ได้ และสนุกด้วย

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

จุดสำคัญในเรื่อง Stack คือ เมื่อเราต้องการใช้จาน เราจะต้องหยิบใบบนสุดไปใช้ก่อนเสมอ เราจะไม่พยายามหยิบใบที่อยู่ตรงกลาง หรือใบล่างสุดออกมา (หากต้องการทำเช่นนั้นต้องใช้คิวแบบอื่นที่ไม่ใช้ Stack ) หลักการทำงานเช่นนี้รู้จักกันในนามว่า “เข้าล่าสุดออกก่อน” หรือ LIFO (Last in First Out)

 

การทำงานของ Stack รู้จักกันในนามว่า “เข้าล่าสุดออกก่อน” หรือ LIFO (Last in First Out)เป็นโครงสร้างข้อมูลที่เราพบเห็นทั่วไปในวงการคอมพิวเตอร์

 

Stack เป็นโครงสร้างข้อมูลที่เราพบเห็นทั่วไปในวงการคอมพิวเตอร์ ตัวอย่างการใช้งาน Stack คือ การทำงานของไมโครโปรเซสเซอร์ที่ใช้ Stack เมื่อทำ interrupt และเรียกโปรแกรมย่อย การใช้ Stack เพื่อแก้ปัญหาในการค้นหาข้อมูล และการใช้ Stack ในตัวจัดการหน่วยความจำ (ส่วน CLR) ของ .NET เป็นต้น

 

Stack และ Array
Stack และอาร์เรย์เป็นสิ่งที่คู่กันจนแยกกันไม่ออก เพราะเมื่อเราสร้าง Stack เรามักใช้ array เพื่อเก็บข้อมูลของ Stack สิ่งนี้ทำให้หลายๆ คนสับสน เข้าใจผิดว่า array คือ Stack หรือ Stack คือ array อันที่จริงแล้วไม่ใช่ เพราะองค์ประกอบของ Stack นอกจากจะมี array แล้วยังต้องมีสิ่งอื่นๆ ด้วย เช่น ตัวชี้ยอด Stack ตัวกำหนดขนาดของ Stack และฟังก์ชันเพื่อนำข้อมูลเข้า-ออกจาก Stack เป็นต้น

การนำข้อมูลเข้าไปใส่ใน Stack จะใช้คำสั่ง Push เมื่อ Push แล้วข้อมูลจะถูกนำไปเก็บไว้ใน array และปรับเลื่อนตัวชี้ยอด Stack ขึ้น ในทางตรงกับข้าม การนำข้อมูลออกจาก Stack ใช้คำสั่ง Pop เมื่อ Pop แล้วข้อมูลชิ้นบนสุดจะถูกนำออกไป และตัวชี้ยอด Stack (Stack Pointer ต่อไปจะเรียก SP) จะถูกปรับลดลงหนึ่งหน่วย

ข้อมูลหนึ่งชิ้นของ Stack จะเก็บอยู่ใน Array หนึ่งหน่วยเรียกว่า Array element (ต่อไปจะเรียกย่อว่า AE) AE แต่ละตัวจะมีหมายเลขกำกับเรียกว่า Array Index (ต่อไปจะเรียกย่อว่า AI)

 

คลาส Stack2
ต่อไปเราจะนิยามคลาสชื่อ Stack2 เพื่อสาทิตการสร้าง Stack โดยใช้ภาษา C# โค้ดแบบย่อ (outline) ของคลาส Stack2 เป็นดังนี้

using System;

namespace StackTest
{
    class Stack2
    {
        private int size = 10;
        private int top;
        private string[] value;
        public Stack2(int size)
        private bool isFull()
        public void Push(string x)
        private bool isEmpty()
        public string Pop()
    }
}

จากโค้ดข้างบนจะเห็นว่าคลาส Stack2 มีสมาชิกทั้งสิ้น 8 ตัว สามตัวแรกเป็นฟิลด์สมาชิกของคลาส อีกห้าตัวที่เหลือเป็นเมธอดสมาชิก ขอให้สังเกตว่าฟิลด์ทั้งหมดเป็น instance field หรือ object ฟิลด์ คือเป็นฟิลด์ที่จะใช้เก็บข้อมูลของ object (ซึ่งจะถูกสร้างจากคลาสนี้) ฟิลด์เหล่านี้มี access modifier เป็นแบบ private ทำให้โค้ดภายนอก (หรือ client class คือคลาสที่สร้าง object จากคลาสนี้ ต่อไปจะเรียกย่อว่า CC) ไม่สามารถเข้าถึงได้ เพราะเราไม่ต้องการให้ CC เปลี่ยนแปลงค่าของฟิลด์เหล่านี้

โปรดสังเกตต่อไปอีกว่าเมธอดบางตัวมี access modifier เป็นแบบ private เพราะเป็นเมธอดที่เรานิยามขึ้นเพื่อให้โค้ดภายในคลาสนี้เรียกใช้เท่านั้น ไม่ต้องการให้ CC เรียกใช้ ส่วนเมธอดที่มี access modifier เป็นแบบ public เป็นเมธอดที่เราต้องการให้ CC สามารถเรียกใช้งานได้โดยตรง

สมาชิกแต่ละตัวมีหน้าที่ดังนี้

• size: กำหนดขนาดของ Stack
• top: เป็นตัวชี้ตำแหน่งยอดของ Stack (SP)
• value: เป็น array เก็บข้อมูลของ Stack
• Stack2: คือ method constructor
• isFull: ตรวจสอบว่า Stack เต็มหรือยัง
• Push: ใส่ข้อมูลใหม่
• isEmpty: ตรวจสอบว่า Stack ว่างเปล่าหรือไม่
• Pop: นำข้อมูลออกจาก Stack

ฟิลด์สมาชิกของคลาส Stack2
คลาส Stack2 มีฟิลด์สมาชิกสามตัวโดยมีรายละเอียดดังนี้
private int size = 10;
บรรทัดนี้ประกาศฟิลด์สมาชิกชื่อ size เป็นแบบเลขจำนวนเต็ม size ทำหน้าที่กำหนดขนาดของ Stack เราจะนำค่าของ size ไปกำหนดจำนวน AE ที่เราจะใช้เก็บข้อมูลใน Stack

private int top;

บรรทัดนี้ประกาศฟิลด์สมาชิกชื่อ top เป็นแบบเลขจำนวนเต็ม top ทำหน้าที่เป็นตัวชี้ยอดของ Stack หรือ SP ซึ่งจะเปลี่ยนแปลงตลอดเวลาเมื่อเราใช้งาน Stack

private string[] value;

บรรทัดนี้ประกาศฟิลด์สมาชิกชื่อ value ให้เป็น array แบบ string เราจะใช้ value เป็นที่เก็บข้อมูลของ Stack จำนวน AE ของ value ถูกกำหนดโดยฟิลด์ size

 

เมธอดสมาชิกของคลาส Stack2
ต่อไปนี้ผู้เขียนจะอธิบายโค้ดส่วนเมธอดสมาชิกทั้งห้าตัวของคลาส Stack2 โดยเริ่มจาก Method Constructor (ต่อไปจะเรียกย่อว่า MC) เป็นตัวแรก

        public Stack2(int size)
        {
            this.size = size;
            value = new string[size];
            top = -1;
        }

โค้ดที่เห็นข้างบนคือ MC ของคลาส Stack2 ซึ่งเป็นเมธอดที่ทำงานโดยอัตโนมัติเมื่อเราสร้าง object คลาสในภาษา C# จำเป็นต้องมี MC ทุกคลาส หากเราละไว้ ตัวแปลภาษา C# จะสร้าง MC ให้เราโดยอัตโนมัติ (เป็น MC ว่างๆ ที่ไม่มี argument เรียกว่า default MC)

MC ของคลาส Stack2 มีโค้ดเพียงสามบรรทัด ทำหน้าที่กำหนดค่าเริ่มต้นให้ object ที่เป็น Stack ที่เพิ่งถูกสร้างขึ้นใหม่ โค้ดสามบรรทัดนี้เป็นการเตรียมการให้ Stack พร้อมต่อการถูกนำไปใช้งาน

โค้ดบรรทัดแรกทำหน้าที่นำค่าที่ได้รับจากพารามิเตอร์มากำหนดให้ฟิลด์สมาชิกดังนี้

this.size = size;

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

value = new string[size];

บรรทัดนี้ทำหน้าที่กำหนดความลึกให้ array (กำหนดจำนวน AE) ค่าที่ใช้กำหนดคือ size ซึ่งเป็นตัวแปรพารามิเตอร์ของเมธอดนี้

top = -1;

คำสั่งนี้กำหนดค่า top ให้เป็นลบหนึ่งเพื่อเป็นเครื่องแสดงว่าขณะนี้ Stack ว่างเปล่า ไม่มีข้อมูล เป็นการกำหนดค่าเริ่มต้นให้แก่ SP

 

โค้ดภาษา C# เพื่อการ Push
การ Push ทำได้โดยนำข้อมูลไปใส่ใน array แล้วปรับค่า SP ให้เลื่อนขึ้น แต่ก่อนที่เราจะนำข้อมูลไปใส่ใน array เราจำเป็นต้องตรวจสอบก่อนว่า Stack เต็มแล้วหรือไม่ หาก Stack เต็มแล้วเราจะต้องยกเลิกการ Push

เพื่อให้โค้ดอ่านง่ายเราจึงนิยามโค้ดตรวจสอบการเต็มของ Stack แยกออกมาเป็นอีกเมธอดหนึ่งชื่อ isFull ดังนี้

        private bool isFull()
        {
            if (top < size - 1)
                return false;
            else
                return true;
        }

หัวใจของเมธอด isFull คือคำสั่ง if ทำหน้าที่ตรวจสอบว่าค่าของ SP มีค่าน้อยกว่าจำนวน AE -1 หรือไม่ หากน้อยกว่าแสดงว่า Stack ยังไม่เต็ม หากมากกว่าแสดงว่า Stack เต็มแล้ว สาเหตุที่ค่าของ size ต้องลบด้วยหนึ่งเพราะตัวเลขใน top เป็นตัวเลขที่เราจะนำไปใช้เป็น AI โดยตรง ในภาษา C# ค่า AI จะเริ่มจากศูนย์ จึงทำให้มันมีค่าน้อยกว่าจำนวน AE อยู่ 1 เสมอ

ผลลัพธ์จากการตรวจสอบว่า Stack เต็มหรือไม่ จะถูกส่งกลับไปยังโค้ดที่เรียกเมธอดนี้ด้วยค่าส่งกลับหรือ return value ที่เรากำหนดไว้ว่าเป็น bool หรือบูลีนซึ่งเป็นค่าทางตรรกะที่เป็นไปได้เพียงจริงหรือเท็จเท่านั้น

        public void Push(string x)
        {
            if (!isFull())
            {
                top++;
                value[top] = x;
            }
        }

เมธอด Push ทำหน้าที่ใส่ข้อมูลเข้าไปใน Stack ก่อนใส่ข้อมูลจะเรียกเมธอด isFull เพื่อตรวจสอบว่า Stack เต็มหรือยัง เครื่องหมายตกใจที่อยู่หน้าเมธอดใส่ไว้เพื่อกลับค่าตรรกะ ทำให้คำสั่ง if มีความหมายว่า “หาก Stack ยังไม่เต็มจงทำคำสั่งในวงเล็บปีกกา”

หาก Stack เต็มเมธอดจะหยุดการทำงานไปโดยไม่ดำเนินการใดๆ หากพบว่า Stack ยังไม่เต็มเราจะเพิ่มค่าของ top ขึ้นหนึ่งเพื่อเลื่อน SP ไปยัง AE ที่อยู่เหนือข้อมูลล่าสุดของ Stack จากนั้นนำข้อมูลที่ได้รับมาในพารามิเตอร์ x ไปใส่ไว้ในตำแหน่งนั้น

 

โค้ดภาษา C# เพื่อการ Pop
การ Pop มีการทำงานตรงข้ามกับ Push การ Pop ทำได้โดยอ่านข้อมูลตัวบนสุดของ Stack แล้วปรับตำแหน่งยอดของ Stack ให้ลดลงหนึ่ง แต่ก่อนจะ Pop ได้เราจะต้องแน่ใจเสียก่อนว่าใน Stack มีข้อมูลเหลืออยู่ให้ Pop เราจึงต้องนิยามเมธอดชื่อ isEmpty เพื่อใช้ตรวจสอบว่า Stack ว่างเปล่าหรือไม่ โดยมีโค้ดดังนี้

        private bool isEmpty()
        {
            if (top == -1)
                return true;
            else
                return false;
        }

จากโค้ดข้างบนจะเห็นว่าการตรวจทำได้ง่ายมากเพียงแค่ตรวจสอบค่าของ top ว่าเป็น -1 หรือไม่ สาเหตุที่เป็นเช่นนั้นเพราะ AE แรก (ล่างสุดของ Stack) ย่อมเป็นตำแหน่งที่ศูนย์เสมอ และทุกครั้งหลักจากที่เรา Pop แล้ว เราจะลดค่า top ลงหนึ่ง ด้วยเหตุนี้เมื่อเรา Pop ถึงข้อมูลตัวสุดท้ายค่า top จึงเปลี่ยนจากศูนย์เป็น -1 ไปโดยอัตโนมัติ

        public string Pop()
        {
            string retVal = "-";
            if (!isEmpty())
            {
                retVal = value[top];
                top--;
            }
            return retVal;
        }

โค้ดที่เห็นข้างบนคือเมธอด Pop ซึ่งทำหน้าที่นำข้อมูลออกจาก Stack คำสั่งบรรทัดแรก (ภายในวงเล็บปีกกา) ทำหน้าที่ประกาศตัวแปรท้องถิ่นชื่อ retVal เพื่อใช้เก็บพักข้อมูลที่จะส่งไปให้ CC เรากำหนดค่าเริ่มต้นให้ retVal เป็นตัวเคาะวรรค (white space) เพื่อส่งค่านี้กลับไปในกรณีที่ Stack ว่างเปล่า

คำสั่ง if ทำหน้าที่ตรวจสอบว่า Stack ว่างเปล่าหรือไม่ ขอให้สังเกตว่าเราต้องใช้เครื่องหมายตกใจเพื่อกลับตรรกะของ isEmpty คำสั่งบรรทัดนี้จึงมีความหมายว่า “ถ้า Stack ไม่ว่างเปล่า” หากการตรวจสอบได้ผลลัพธ์เป็นจริง (คือว่างเปล่า) เมธอดนี้จะจบการทำงานโดยส่งค่าตัวเคาะวรรคกลับไปเพื่อแสดงว่า Stack ว่าง

หากตรวจสอบแล้วพบว่าใน Stack มีข้อมูล โปรแกรมจะอ่านค่าจาก array มาใส่ในตัวแปร retVal เพื่อเตรียมส่งกลับให้ผู้เรียกเมธอด ถัดมาเราลดค่าฟิลด์ top ลงหนึ่งเพื่อปรับลดตัวชี้ยอด Stack ลงหนึ่งตำแหน่ง หากข้อมูลที่กำลัง Pop เป็นข้อมูลตัวสุดท้ายใน Stack ค่าของ top ก่อนปรับลดจะเป็นศูนย์ เมื่อโปรแกรมทำคำสั่ง top – – ค่าของ top จะกลายเป็น -1 ซึ่งเป็นเครื่องแสดงว่าบัดนี้ Stack ว่างเปล่าแล้ว

โปรแกรมทดสอบคลาส Stack2
เมื่อนิยามคลาส Stack2 เสร็จแล้วเราต้องสร้างโปรแกรมทดสอบหรือ client class โดยเขียนโค้ดสร้าง object Stack แล้วทดลอง Push และ Pop ข้อมูลดู โค้ดสำหรับทดสอบเป็นดังนี้

            // my custom stack test
            Stack2 myStack = new Stack2(5);
            myStack.Push("one");
            myStack.Push("two");
            myStack.Push("three");
            textBox1.Text = "My custom Stack\r\n";
            textBox1.Text += "==============\r\n";
            for (int i = 0; i < 3; i++)
                textBox1.Text += myStack.Pop() + "\r\n";

บรรทัดแรกสร้าง object และกำหนดให้มีตัวแปรอ้างอิง object ชื่อ myStack ซึ่งเป็น object ที่ถูกสร้างจากคลาส Stack2 ที่เรานิยามไว้ ให้สังเกตว่าเราใส่ค่า 5 เป็น argument ให้ MC ซึ่งจะถูกนำไปใช้กำหนดขนาดของ Stack

สามบรรทัดถัดไปเราทดลอง Push ข้อมูลลง Stack เป็นข้อความ one, two และ three ตามลำดับ ดังนั้น one จะอยู่ล่างสุดและ three จะอยู่บนสุดใน Stack

สองบรรทัดถัดไปแสดงข้อความว่า My custom Stack และขีดเส้นใต้ และสุดท้ายเราจัดตั้งคำสั่งวนซ้ำ (for loop) เพื่อทำงานซ้ำสามหน โดยแต่ละหนจะ Pop ค่าออกจาก Stack แล้วนำค่าที่ได้มาแสดงใน TextBox1

 

สร้าง Stack แบบ object จากคลาสของ .NET
ในคลาส Stack2 เรานิยามคลาส Stack ขึ้นด้วยตนเองทั้งหมด แต่ในการใช้งานจริงเราไม่จำเป็นต้องทำเช่นนั้นก็ได้ เพราะ .NET Framework จัดเตรียมคลาส Stack ไว้ให้แล้วใน namespace System.collections ที่เราสามารถนำมาใช้งานได้ทันทีดังนี้

            // .NET object stack test
            Stack myStack = new Stack();
            myStack.Push(11);
            myStack.Push(12);
            myStack.Push(13);
            textBox1.Text = ".NET Object Stack\r\n";
            textBox1.Text += "==============\r\n";
            foreach (Object obj in myStack)
                textBox1.Text += obj + "\r\n";

จะเห็นว่าวิธีเรียกใช้งานก็คลายๆ คลาส Stack2 ที่เรานิยามไว้ แต่มีข้อดีกว่าคือมีเมธอดเตรียมไว้ให้เราใช้มากมาย เช่นเมธอด Peek ทำหน้าที่ตรวจสอบข้อมูลตัวบนสุดของ Stack และเมธอด Clone ทำหน้าที่ทำสำเนา Stack เป็นต้น

 

สร้าง Stack แบบ Generic จากคลาสของ .NET
คลาส Stack2 มีข้อเสียร้ายแรงคือรับข้อมูลได้เพียงแบบ string เท่านั้น หากต้องการให้รับข้อมูลแบบอื่นเช่น int หรือ float เราต้องนิยามคลาสใหม่อีกหลายๆ คลาสเท่าจำนวนชนิดข้อมูลที่ต้องการ ซึ่งไม่ใช่วิธีทำงานที่ดีนัก ส่วนคลาส Stack ในหัวข้อก่อหน้านี้รับข้อมูลแบบ object จึงสามารถทำงานกับข้อมูลชนิดใดก็ได้ แต่ก็มีข้อเสียจะเกิดการ boxing และ unboxing เพื่อแปลงชนิดข้อมูลอยู่ตลอดเวลา จึงนับว่าเป็นวิธีที่ไม่มีประสิทธิภาพเช่นกัน

โชคดีใน .NET Framework เวอร์ชัน 2.0 ขึ้นไปมี Generic ที่ช่วยให้เรากำหนดชนิดข้อมูลที่จะใช้กับคลาสให้เป็น type อะไรก็ได้ ทำให้เรารับมือกับปัญหาเรื่อง type ได้สะดวกมาก และที่สะดวกมากยิ่งขึ้นไปอีกคือใน .NET Framework เวอร์ชัน 2.0 ขึ้นไปมีคลาส Stack แบบ Generic ไว้ให้แล้วใน namespace System.collections.Generic เราจึงสามารถนำมาใช้งานได้ทันทีดังนี้

            // .NET generic stack test
            Stack<string> myStack = new Stack<string>();
            myStack.Push("c1d0c2c1");
            myStack.Push("b7d8e0c3d5c2b9");
            myStack.Push("c5d4e9b9a8d5e8");
            textBox1.Text = ".NET Generic Stack\r\n";
            textBox1.Text += "==============\r\n";
            foreach (string number in myStack)
                textBox1.Text += number + "\r\n";
        }  

สรุปเรื่อง Stack ในภาษา C#
การสร้างและใช้งาน Stack ในภาษา C# ทำได้ง่ายมากเพราะในคลาสไลบรารีของ .NET Framework มีคลาส Stack มาให้แล้ว ในบทความตอนนี้ผู้เขียนแสดงวิธีนิยามคลาส Stack ขึ้นเอง เพียงเพื่อสาทิตวิธีทำงานภายในของ Stack

ผู้เขียนจัดทำโค้ดตัวอย่างประกอบบทความนี้ไว้เป็นไฟล์ชื่อ StackInCSharp.zip (ภายในเป็น solution ที่สร้างจาก MS Visual Studio .NET 2005) ท่านสามารถดาวน์โหลดได้จากเว็บไซต์ของผู้เขียนที่ http://www.laploy.com (เลือกหัวข้อ download) หากท่านมีข้อสงสัยใดๆ โปรดโพสคำถามไว้ในเว็บบอร์ดที่เว็บไซต์ดังกล่าว