STACK

   บทที่ 2

STACK

วัตถุประสงค์

•เข้าใจแนวคิดและหลักการของโครงสร้างข้อมูลแบบสแตก

•อธิบายหลักการทำงานของฟังก์ชันการดำเนินงานพื้นฐานของสแตกได้

•เข้าใจหลักการสร้างสแตกด้วยอาร์เรย์และลิงค์ลิสต์ได้

•สามารถแปลงนิพจน์ Infix ให้เป็น Postfix ได้

•เข้าใจหลักการรีเคอร์ซีฟ

ลักษณะของสแตก Stack

ลักษณะของสแตก Stack  

•สแตก เป็นโครงสร้างข้อมูลแบบเชิงเส้น

•โครงสร้างข้อมูลที่จัดเก็บเป็นแบบเรียงลำดับต่อเนื่องกันไป

•การเพิ่มหรือนำข้อมูลออกจากสแตกทำได้ที่จุดปลายของสแตกทางเดียว

•มาทีหลังแต่ออกก่อน (Last In – First Out : LIFO)

ส่วนประกอบสำคัญของสแตก

1.ตัวชี้สแตก หรือ Stack Pointer เป็นตัวควบคุมการนำสมาชิกเข้า หรือออกจากสแตก เป็นตัวบอกว่าสแตกนั้นเต็มหรือยัง

2.สมาชิกของสแตก หรือ Stack Element คือ สมาชิกของสแตก ซึ่งต้องเป็นข้อมูลชนิดเดียวกันทั้งหมด

3.ค่าสูงสุดของสแตก หรือ Max Stack เป็นค่าที่บอกว่าสแตกนี้สามารถเก็บข้อมูลได้มากที่สุดเท่าไหร่

การสร้างสแตก Stack implement

สามารถสร้างสแตกด้วยการแทนที่ข้อมูลสแตกได้ 2 วิธี คือ

1.การสร้างสแตกด้วยอาร์เรย์ เป็นการจัดสรรเนื้อที่หน่วยความจำแบบ Static ซึ่งต้องมีการกำหนดขนาดของสแตกเพื่อใช้งานล่วงหน้า

2.การสร้างสแตกด้วยลิงค์ลิสต์ เป็นการจัดสรรเนื้อที่หน่วยความจำแบบ Dynamic โดยจะจัดสรรหน่วยความจำเมื่อมีการใช้งานจริงเท่านั้น และยังสามารถเก็บข้อมูลต่างชนิดกันได้

การสร้างสแตก Stack implement

สามารถสร้างสแตกด้วยการแทนที่ข้อมูลสแตกได้ 2 วิธี คือ

1.การสร้างสแตกด้วยอาร์เรย์ เป็นการจัดสรรเนื้อที่หน่วยความจำแบบ Static ซึ่งต้องมีการกำหนดขนาดของสแตกเพื่อใช้งานล่วงหน้า

2.การสร้างสแตกด้วยลิงค์ลิสต์ เป็นการจัดสรรเนื้อที่หน่วยความจำแบบ Dynamic โดยจะจัดสรรหน่วยความจำเมื่อมีการใช้งานจริงเท่านั้น และยังสามารถเก็บข้อมูลต่างชนิดกันได้

การจัดการกับสแตก

ในการทำงานของสแตก ประกอบด้วย 2 กระบวนการ คือ การเพิ่มข้อมูลลงบนสแตก (Push Stack) และการดึงข้อมูลออกจากสแตก (Pop Stack)

การดำเนินงานของสแตก Stack operations

ประกอบด้วยฟังก์ชันพื้นฐาน ดังนี้

•ClearStack

•EmptyStack

•FullStack

•Push

•Pop

ฟังก์ชัน Clear stack

       ClearStack : เป็นการดำเนินการเพื่อลบข้อมูลออกจากสแตกให้หมด

กรณีใช้โครงสร้างข้อมูลอาร์เรย์ ต้องสั่งให้ช่องบนสุดของสแตกเป็น 0

  Stack.Top := 0;

      ClearStack : กรณีใช้โครงสร้างข้อมูลลิงค์ลิสต์ ต้องสั่งให้ตัวชี้สแตกไม่ชี้ไปที่ไหนเลย

  กำหนดค่าตัวชี้สแตก = Null

      EmptyStack : เป็นการดำเนินการเพื่อตรวจสอบว่าสแตกนั้นมีข้อมูลหรือไม่

กรณีใช้โครงสร้างข้อมูลอาร์เรย์ ต้องสั่งให้ตรวจสอบว่าที่ Top ของสแตกนั้นมีค่า = 0 หรือไม่

      EmptyStack := Stack.top := 0;

{ถ้าเป็นจริงจะส่งค่า True ออกมาให้โปรแกรมหลัก}

กรณีใช้โครงสร้างข้อมูลลิงค์ลิสต์ ให้ตรวจสอบว่าตัวชี้สแตกไม่ชี้ไปที่ไหน

       EmptyStack := Stack.Nil;

{ถ้าเป็นจริงคืนค่า True ถ้าไม่จริง คืนค่า False}

       FullStack : เป็นการดำเนินการเพื่อตรวจสอบว่าสแตกนั้นเต็มหรือไม่

ดำเนินการตรวจสอบเฉพาะข้อมูลอาร์เรย์ ต้องตรวจสอบว่า Top ของสแตกนั้นเป็นค่าสูงสุดที่ขอไว้หรือไม่

  FullStack := Stack.top := MaxStack;

ตัวอย่างการ push stack

          เป็นการทำงานของสแตกในการนำข้อมูลเข้าสู่สแตก โดยก่อนที่จะนำข้อมูลเข้านั้นต้องจัดการให้ตัวชี้สแตกให้ไปชี้ในตำแหน่งต่อไปของสแตกก่อน ซึ่งต้องเป็นช่องหรือตำแหน่งที่ยังว่างอยู่ แล้วจึงทำการ Push ข้อมูลลงไปในตำแหน่งที่ตัวชี้สแตกชี้อยู่

อัลกอริทึมในการ push stack

1.ตรวจสอบว่าสแตกเต็มหรือไม่ โดยเปรียบเทียบค่า Top กับขนาดของตัวแปรอาร์เรย์ที่ใช้เก็บ ถ้าไม่เต็ม ทำข้อ 2. ถ้าเต็ม ทำข้อ 4.

2.ขยับตำแหน่ง Top ไปยังตำแหน่งถัดไป (Top = Top +1)

3.ทำการนำค่าที่ได้มาเก็บไว้ยังตำแหน่งของ Top {push(value,stack);}

4.แจ้งผู้ใช้งานว่า สแตกเต็มไม่สามารถเก็บข้อมูลได้

5.จบการทำงาน

เปรียบเทียบประสิทธิภาพของการสร้างสแตกด้วย

อะเรย์และลิงค์ลิสต์

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

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

ตัวอย่าง

a)เริ่มต้นสร้างสแตก S ขึ้นทำงานจะได้เป็นสแตกว่าง ไม่มีสมาชิกโดยตัวชี้สแตก Top ยังไม่มีค่า 

  [    ]    ===> S = {}   

    <---- Top (Top = -1)     

b) นำค่า 'A' เข้ามาเก็บเป็นตัวแรกโดยใช้คำสั่ง push('A',S); ===> S = { 'A' } 

    [       A ]<---- Top (Top = 0) // ได้มาจาก Top = Top + 1; 

ตัวอย่าง

e) ต้องการดึงค่าออกมาโดยใช้คำสั่ง pop(S);   ===> S = { 'A','B' } 

    [       B ]<---- Top (Top = 1) // ได้มาจาก Top = Top - 1; 

    [       A ]     

f) นำค่า 'D', 'E' เก็บต่อโดยใช้คำสั่ง push('D',S); และ push('E',S);

===> S = { 'A','B','D','E' }        

  2. --> [       E ]<---- Top (Top = 3) // ได้มาจาก Top = Top + 1;           1. --> [       D ]<---- Top (Top = 2) // ได้มาจาก Top = Top + 1; 

    [       B ] 

    [       A ]

การประยุกต์ใช้งานสแตก

•การเรียงลำดับข้อมูลแบบย้อนกลับ (Reversing Data)

•การแตกข้อมูลออกเป็นส่วน ๆ (Parsing)

•การหน่วงเวลา (Postponement)

•การย้อนรอย (Backtracking Steps)

การใช้สแตกเพื่อแปลงนิพจน์ Infix เป็น Postfix

                                        Infix คือ นิพจน์ที่มีตัวดำเนินการ (Operator) อยู่ระหว่างตัวถูกกระทำ (Operand) เช่น A + B เครื่องหมาย  +  เป็นโอเปอเรเตอร์ระหว่างโอเปอร์แรนด์  A และ  B  ซึ่งเห็น ว่าเป็นนิพจน์ที่มนุษย์คุ้นเคย 

                                             ตัวดำเนินการ ก็คือ เครื่องหมายทางคณิตศาสตร์ สำหรับการคำนวณต่าง ๆ เรียงตามลำดับการดำเนินการก่อนหลัง (precedence) ได้แก่

  ยกกำลัง ^

  คูณ หาร * , /

  บวก ลบ + , -

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

นิพจน์ Infix, Postfix

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

  AB+  หมายถึง   A + B  AB/   หมายถึง   A / B

  AB-  A – B  AB^  A ^ B

  AB*  A * B

         ข้อดีของนิพจน์ postfix คือเป็นนิพจน์ที่มีการคำนวณตาม โอเปอร์เรเตอร์ที่มาก่อนหลัง เช่น นิพจน์ ABC*+  หมายถึง ทำการคูณแล้วจึงทำการบวก ซึ่งคือต้องคำนวณ B*C ก่อน แล้วจึงนำผลลัพธ์นั้นไปบวกกับ A ต่อไป

  

กฎการแปลงนิพจน์ Infix, Postfix ด้วยมือ

1.ให้ใส่เครื่องหมายวงเล็บให้กับทุก ๆ นิพจน์ด้วยการคำนึงถึงลำดับการคำนวณ เช่น เครื่องหมายคูณและหารต้องมาก่อนเครื่องหมายบวกและลบ

2.ทำการเปลี่ยนสัญลักษณ์ Infix ในแต่ละวงเล็บให้มาเป็นสัญลักษณ์แบบ Postfix โดยให้เริ่มจากนิพจน์ที่อยู่ในวงเล็บในสุดก่อน จากนั้นก็ดำเนินการแปลงให้เป็นนิพจน์ Postfix ด้วยการย้ายโอเปอเรเตอร์ตรงตำแหน่งวงเล็บนั้นไปยังตำแหน่งวงเล็บปิดของคู่นั้นๆ

3.ถอดเครื่องหมายวงเล็บทิ้งให้หมด

          จงแปลงนิพจน์ A + B * C มาเป็นนิพจน์ Postfix ด้วยมือ

1.ใส่วงเล็บให้หมดตามลำดับความสำคัญ

  (A + (B*C) )

2. พิจารณานิพจน์ที่อยู่วงเล็บในสุด โดยย้ายเครื่องหมาย * ไปข้างหลัง C

  (A + (BC*))

  จากนั้นย้ายโอเปอเรเตอร์ + ซึ่งอยู่ที่ตำแหน่งวงเล็บเปิดภายนอกไปยังตำแหน่งวงเล็บปิดภายนอกของคู่ตัวเอง

  (A(BC*)+)

3. ถอดเครื่องหมายวงเล็บทิ้งออกให้หมด

  ABC*+

        จงแปลงนิพจน์ 5 * 6 – 10 มาเป็นนิพจน์ Postfix ด้วยมือ

5 * 6 – 10   = ((5 * 6) – 10)

  = ((56*)-10)

  = ((56*)10-)

  = 56*10-

นิพจน์ Infix, Postfix

นิพจน์ Infix, Postfix

นิพจน์ Infix, Postfix

การนำสแตกมาใช้ในการแปลงนิพจน์ Infix, Postfix

1. ถ้าค่า input เป็น operand ให้นำค่าไปเป็น Output

2. ถ้าค่า input เป็น operator (เครื่องหมายคณิตศาสตร์) ให้พิจารณาดังนี้

   2.1 ถ้า สแตกว่าง ให้นำ operator ใส่สแตก

   2.2 ถ้า สแตกไม่ว่าง ให้นำ operator ไปเปรียบกับค่า operator ตัวบนในสแตก ถ้าค่า operator ที่เป็น input มีค่า precedence น้อยกว่าหรือเท่ากับค่า operator ตัวบนของสแตก ให้ดึง operator ตัวบนในสแตกไปเป็น output แล้วเปรียบเทียบกับ operator ในสแตกตัวถัดไป แล้วเปรียบเทียบเช่นเดียวกับก่อนหน้านี้  แต่ถ้า operator ที่เป็น input มีค่า precedence มากกว่าค่า operator ตัวบนของสแตก  ให้นำค่า operator ที่เป็น input ใส่สแตก

3. ถ้า input เป็น (  ให้ใส่ลงสแตก

4. ถ้า input เป็น ) ให้ดึงข้อมูลออกจากสแตกทีละตัวไปเป็น output จนกระทั่งพบ ( ในสแตก ให้ดึงออกมาทิ้งไป ไม่ต้องไปใส่เป็น output

5. ถ้า input หมด และสแตกยังมีข้อมูลอยู่ ให้ดึงข้อมูลออกจาก stack ที่ตัวไปเป็น output จนกระทั่งสแตกว่าง