วันอังคารที่ 11 เมษายน พ.ศ. 2560
บทที่ 4
Stack
ลักษณะของสแตก Stack
สแตก
เป็นโครงสร้างข้อมูลแบบเชิงเส้น
โครงสร้างข้อมูลที่จัดเก็บเป็นแบบเรียงลำดับต่อเนื่องกันไป
การเพิ่มหรือนำข้อมูลออกจากสแตกทำได้ที่จุดปลายของสแตกทางเดียว
มาทีหลังแต่ออกก่อน
(Last In – First Out : LIFO)
ส่วนประกอบสำคัญของสแตก
1.ตัวชี้สแตก หรือ Stack Pointer เป็นตัวควบคุมการนำสมาชิกเข้า หรือออกจากสแตก
เป็นตัวบอกว่าสแตกนั้นเต็มหรือยัง2.สมาชิกของสแตก หรือ Stack Element คือ สมาชิกของสแตก
ซึ่งต้องเป็นข้อมูลชนิดเดียวกันทั้งหมด3.ค่าสูงสุดของสแตก
หรือ Max
Stack เป็นค่าที่บอกว่าสแตกนี้สามารถเก็บข้อมูลได้มากที่สุดเท่าไหร่
การสร้างสแตก
Stack implement
สามารถสร้างสแตกด้วยการแทนที่ข้อมูลสแตกได้
2 วิธี คือ
1.การสร้างสแตกด้วยอาร์เรย์ เป็นการจัดสรรเนื้อที่หน่วยความจำแบบ
Static ซึ่งต้องมีการกำหนดขนาดของสแตกเพื่อใช้งานล่วงหน้า
2.การสร้างสแตกด้วยลิงค์ลิสต์ เป็นการจัดสรรเนื้อที่หน่วยความจำแบบ Dynamic โดยจะจัดสรรหน่วยความจำเมื่อมีการใช้งานจริงเท่านั้น
และยังสามารถเก็บข้อมูลต่างชนิดกันได้
ฟังก์ชัน push stack
เป็นการทำงานของสแตกในการนำข้อมูลเข้าสู่สแตก
โดยก่อนที่จะนำข้อมูลเข้านั้นต้องจัดการให้ตัวชี้ส
แตกให้ไปชี้ในตำแหน่งต่อไปของสแตกก่อน
ซึ่งต้องเป็นช่องหรือตำแหน่งที่ยังว่างอยู่ แล้วจึงทำการ
Push ข้อมูลลงไปในตำแหน่งที่ตัวชี้สแตกชี้อยู่
จบการทำงาน
ตัวอย่างการ
push stack
อัลกอริทึมในการ
push stack
1.ตรวจสอบว่าสแตกเต็มหรือไม่
โดยเปรียบเทียบค่า Top
กับขนาดของตัวแปรอาร์เรย์ที่ใช้เก็บ
ถ้าไม่เต็ม ทำข้อ 2. ถ้าเต็ม ทำข้อ 4.
2.ขยับตำแหน่ง
Top ไปยังตำแหน่งถัดไป (Top = Top +1)
3.ทำการนำค่าที่ได้มาเก็บไว้ยังตำแหน่งของ
Top {push(value,stack);}
4.แจ้งผู้ใช้งานว่า
สแตกเต็มไม่สามารถเก็บข้อมูลได้
จบการทำงาน
อัลกอริทึม
pop stack
1.ตรวจสอบว่าสแตกว่างหรือไม่
โดยเปรียบเทียบค่า Top
ว่ามีค่าเท่ากับ -1 หรือไม่ ถ้าไม่ว่าง
ทำข้อ 2. ถ้าว่าง ทำข้อ 4. isEmpty(stack)
2.ทำการดึงค่าในตำแหน่งของ
Top ออกมาใช้งาน pop(stack)
3.ขยับตำแหน่ง
Top ให้ถอยหลังลงมา (Top = Top-1) ไปทำข้อ 5.
4.แจ้งผู้ใช้งานว่า
สแตกว่างไม่สามารถดึงข้อมูลไปใช้งานได้
5.จบการทงาน
กรณีข้อมูลแบบลิงค์ลิสต์
Begin
IF Not EmptyStack(Stack) then
Begin
PopData := Stack^.Element;
DisposeNode := Stack;
Stack := Stack^.Next;
Dispose(DisposeNode);
End
Else
writeln(‘Stack Underflow’);
End;
เปรียบเทียบประสิทธิภาพของการสร้างสแตกด้วยอะเรย์และลิงค์ลิสต์
•การแทนที่ข้อมูลสแตกด้วยอะเรย์ มีข้อจำกัด สำหรับขนาดของสแตกและจะต้องจองเนื้อที่เท่ากับขนาด
ที่
ใหญ่ที่สุดของสแตกไว้เลย เพราะเป็นการจัดสรรเนื้อที่ใน
หน่วยความจำแบบสแตติก
•การแทนที่ข้อมูลสแตกด้วยลิงค์ลิสต์ ไม่มี ข้อจำกัดของขนาดของสแตกและหน่วยความจำจะถูกใช้ก็ต่อ
เมื่อมีข้อมูลจริงๆ แล้วเท่านั้น เพราะเป็นการจัดสรรเนื้อที่หน่วย ความจำแบบไดนามิก
ซึ่งทำให้ประหยัดเนื้อที่ในหน่วยความ จำมากกว่า
แต่การเขียนโค้ดสำหรับการแทนที่ข้อมูลสแตก ด้วยอะเรย์ง่ายกว่า
การแทนที่ข้อมูลด้วยลิงค์ลิสต์
[ A ]<----
Top (Top = 0) // ได้มาจาก Top = Top +
การใช้สแตกเพื่อแปลงนิพจน์ Infix เป็น Postfix
ตัวอย่าง
เริ่มต้นสร้างสแตก S ขึ้นทำงานจะได้เป็นสแตกว่าง
ไม่มีสมาชิกโดยตัวชี้สแตก Top ยังไม่มีค่า
[ ] ===> S = {}
<---- Top (Top = -1)
นำค่า 'A' เข้ามาเก็บเป็นตัวแรกโดยใช้คำสั่ง push('A',S); ===> S = { 'A' }
การใช้สแตกเพื่อแปลงนิพจน์ Infix เป็น Postfix
ตัวดำเนินการ
ก็คือ เครื่องหมายทางคณิตศาสตร์ สำหรับการคำนวณต่าง ๆ เรียงตามลำดับการดำเนิน
การก่อนหลัง
(precedence) ได้แก่
ยกกำลัง ^
คูณ หาร * , /
บวก ลบ + , -
ถ้าเครื่องหมายมีลำดับการดำเนินการเดียวกัน
จะเลือกดำเนินงานของเครื่องหมาย
จากซ้ายไปขวา
(ยกเว้น ยกกำลัง) และถ้ามีวงเล็บจะดำเนินงานสิ่งที่อยู่ในวงเล็บก่อน
ข้อเสียของนิพจน์ infix ที่ทำให้คอมไพเลอร์ยุ่งยาก คือ
ลำดับความสำคัญของโอเปอร์เรเตอร์
(Precedence)
ที่ต่างกัน เช่น เครื่องหมายยกกำลัง (^)
มีความสำคัญมากกว่า เครื่องหมายคูณ (*) และ
หาร (/) และเครื่องหมายคูณและหารมี
ความสำคัญมากกว่าเครื่องหมายบวก (+) และลบ (-)
เครื่องหมายใดมีลำดับความสำคัญมากกว่าจะถูกคำนวณก่อน (ถ้าไม่มีวงเล็บกำกับ)เช่น
A
+ B * C
เครื่องจะคำนวณ B
* C ก่อนแล้วนำผลลัพธ์นั้นไปบวกกับค่า
A ซึ่งจะทำงานเหมือน กับ A
+ (B *
C) ส่วนนิพจน์ใดที่มีโอเปอร์เรเตอร์ที่มีลำดับ ความสำคัญเท่ากัน
การคำนวณจะกระทำจากซ้ายไป
ขวา เช่น A – B + C จะทำ
A
– B ก่อน แล้วจึงนำผลลัพธ์นั้นไปบวกกับ ค่า C
ข้อดีของนิพจน์ postfix คือเป็นนิพจน์ที่มีการคำนวณตาม โอเปอร์เรเตอร์ที่มาก่อนหลัง เช่น นิพจน์
ABC*+ หมายถึง
ทำการคูณแล้วจึงทำการบวก ซึ่งคือต้องคำนวณ B*C
ก่อน แล้วจึงนำผลลัพธ์นั้น
ไปบวกกับ A ต่อไป
กฎการแปลงนิพจน์
Infix, Postfix ด้วยมือ
ตัวอย่าง
1.ให้ใส่เครื่องหมายวงเล็บให้กับทุก ๆ
นิพจน์ด้วยการคำนึงถึงลำดับการคำนวณ เช่น
เครื่องหมายคูณ
และหารต้องมาก่อนเครื่องหมายบวกและลบ
2.ทำการเปลี่ยนสัญลักษณ์ Infix ในแต่ละวงเล็บให้มาเป็นสัญลักษณ์แบบ Postfix โดยให้เริ่มจาก
นิพจน์ที่อยู่ในวงเล็บในสุดก่อน
จากนั้นก็ดำเนินการแปลงให้เป็นนิพจน์ Postfix ด้วยการย้ายโอเปอเร
เตอร์ตรงตำแหน่งวงเล็บนั้นไปยังตำแหน่งวงเล็บปิดของคู่นั้นๆ
3.ถอดเครื่องหมายวงเล็บทิ้งให้หมด
การนำสแตกมาใช้ในการแปลงนิพจน์
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 จนกระทั่งสแตกว่าง
