stact

บทที่ 4

stact

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

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

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

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

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

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

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

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

3.    ค่าสูงสุดของสแตก หรือ Max 

การสร้างสแตก 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;

ฟังก์ชัน Clear stack

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

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

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

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

          EmptyStack := Stack.top := 0;

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

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

          EmptyStack := Stack.Nil;

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

 empty stack

ฟังก์ชัน Full stackFullStack :

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

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

          FullStack := Stack.top := MaxStack;

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

ฟังก์ชัน push stack

ในกรณีที่ Push ข้อมูลลงสู่สแตกจนตัวชี้สแตกเท่ากับจำนวนช่องของสแตกแล้ว จะไม่สามารถทำการ Push ข้อมูลได้อีก จะเกิด Error ที่เรียกว่า Stack Overflow

 ในกรณีที่ Push ข้อมูลลงสู่สแตกจนตัวชี้สแตกเท่ากับจำนวนช่องของสแตกแล้ว จะไม่สามารถทำการ Push ข้อมูลได้อีก จะเกิด Error ที่เรียกว่า Stack Overflow

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

ในกรณีที่ Push ข้อมูลลงสู่สแตกจนตัวชี้สแตกเท่ากับจำนวนช่องของสแตกแล้ว จะไม่สามารถทำการ Push ข้อมูลได้อีก จะเกิด Error ที่เรียกว่า Stack Overflow

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

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

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

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

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

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

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

         

Begin

          IF Not FullStack(Stack) then

                   Begin

                             Stack.Top := Stack.Top+1;

                             Stack.info[Stack.Top] := PushData;

                   End

          Else

                   writeln(‘Stack Overflow’);

          End

การ Push Stack จากโครงสร้างข้อมูลลิงค์ลิสต์ ไม่ต้องตรวจสอบว่าสแตกเต็มหรือไม่ ให้ขอพื้นที่จากระบบแล้วสร้างข้อมูลต่อด้านหน้า

ฟังก์ชัน pop astack

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

การ Pop ข้อมูล จะนำข้อมูลส่วนบนสุดของสแตกออกไปทำงานตามความต้องการ แต่ไม่สามารถ Pop ข้อมูลออกจากสแตกที่ว่างเปล่าได้ เพราะจะเกิด Error ที่เรียกว่า Stack Underflow

อัลกอริทึม pop stack

1.    ตรวจสอบว่าสแตกว่างหรือไม่ โดยเปรียบเทียบค่า Top ว่ามีค่าเท่ากับ -1 หรือไม่ ถ้าไม่ว่าง ทำข้อ 2. ถ้าว่าง ทำข้อ 4. isEmpty(stack)

2.    ทำการดึงค่าในตำแหน่งของ Top ออกมาใช้งาน pop(stack)

3.    ขยับตำแหน่ง Top ให้ถอยหลังลงมา (Top = Top-1) ไปทำข้อ 5.

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

5.    จบการทงาน

อัลกอริทึม pop stack

Procedure Pop (Var Stack:StackType; Var PopData : integer);

Begin

          If Not EmptyStack(Stack) Then

                   Begin

                             PopData := Stack.info[Stack.Top];

                             Stack.Top := Stack.Top-1;

                   End;

          Else

                   writeln(‘Stack Underflow’);

End

กรณีข้อมูลแบบลิงค์ลิสต์

Begin

          IF Not EmptyStack(Stack) then

                   Begin

                             PopData := Stack^.Element;

                             DisposeNode := Stack;

                             Stack := Stack^.Next;

                             Dispose(DisposeNode);

                   End

          Else

                   writeln(‘Stack Underflow’);

End;

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

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

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

ตัวอย่าง

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

                   [    ]    ===> S = {}   

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

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

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

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

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

d) นำค่า 'C' เข้ามาเก็บต่อโดยใช้คำสั่ง push('C',S);  ===> S = { 'A','B','C' } 

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

                   [       B ] 

                   [       A ]

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

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

•       (Reversing Data)

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

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

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

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

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

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

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

          ยกกำลัง ^

          คูณ หาร * , /

          บวก ลบ + , -

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

ข้อเสียของนิพจน์ infix ที่ทำให้คอมไพเลอร์ยุ่งยาก คือ ลำดับความสำคัญของโอเปอร์เรเตอร์ (Precedence) ที่ต่างกัน เช่น เครื่องหมายยกกำลัง (^) มีความสำคัญมากกว่า เครื่องหมายคูณ (*) และหาร (/) และเครื่องหมายคูณและหารมี ความสำคัญมากกว่าเครื่องหมายบวก (+) และลบ (-)  เครื่องหมายใดมีลำดับความสำคัญมากกว่าจะถูกคำนวณก่อน (ถ้าไม่มีวงเล็บกำกับ)

เช่น  A +  B * C  เครื่องจะคำนวณ  B * C ก่อนแล้วนำผลลัพธ์นั้นไปบวกกับค่า A ซึ่งจะทำงานเหมือน กับ  A + (B * C)  ส่วนนิพจน์ใดที่มีโอเปอร์เรเตอร์ที่มีลำดับ ความสำคัญเท่ากัน การคำนวณจะกระทำจากซ้ายไปขวา เช่น  A – B + C จะทำ  A – B ก่อน  แล้วจึงนำผลลัพธ์นั้นไปบวกกับ ค่า  C

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

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

          AB-                         A – B            AB^                        A ^ B

          AB*                        A * B  

นิพจน์ 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 ด้วยมือ

จงแปลงนิพจน์ 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

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 จนกระทั่งสแตกว่าง