สแต็ก(Stack) |
ความรู้พื้นฐานเกี่ยวกับสแตก
สแตกเป็นลิเนียร์ลิสต์ที่มีคุณสมบัติที่ว่าเมื่อทำการเพิ่มข้อมูลหรือ ลบข้อมูลในสแตก กระทำทีปลายข้างเดียวกัน ปลายข้างนั้นเรียกว่า ท๊อปของสแตก (Top Of Stack) ซึ่งคุณสมบัติเรียกว่า ไลโฟลิสต์ (LIFO List) หรือ พูชดาวน์ลิสต์ (Pushdown List) คือสมาชิกที่เข้าลิสต์ที่หลังสุดจะได้ออกจากลิสต์ก่อน การเพิ่มข้อมูลเข้าสแตกจะเรียกว่าพูชชิ่ง (pushing) การนำข้อมูลจากสแตกเรียกว่า ป๊อปปิ้ง (poping) การเพิ่มหรือลบข้อมูลในสแตกทำที่ท๊อปของสแตก ท๊อปของสแตกนี้เองเป็นตัวชี้สมาชิกตัวท้ายสุดของสแต็ก
การเพิ่มข้อมูลในสแตก (pushing stack)
การเพิ่มข้อมูลเข้าสแตก หมายถึงการเพิ่มข้อมูลเข้าในสแตก โดยให้ทับบนข้อมูลสุดท้ายในสแตกจะสามารถเพิ่มเข้าได้เรื่อย ๆ จนกว่าจะเต็มสแตก ความหมายของคำว่า สแตกเต็ม คือท๊อปของสแตกชี้ที่เนื้อที่สุดท้ายของสแตกแล้ว เช่น ถ้า สแตกนั้นจองเนื้อที่ไว้ N เนื้อที่โดยที่สามารถบรรจุสมาชิกในสแตกได้ N ตัว เมื่อสแตกว่างค่าท๊อปเป็นศูนย์ เมื่อสแตกเต็มค่าท๊อปเป็น N ดังนั้นเมื่อท๊อปชี้ที่ N ก็ไม่สามารถ Push ข้อมูลลงสแตกได้อีก
นิยาม push(S,x)
ถ้าให้ S เป็นสแตก และ X เป็นข้อมูล ขบวนการ push (S,X) หมายถึง การ push ข้อมูล X ลงสแตก โดยการ push จะเริ่มจากสแตกว่างโดยให้ค่า TOP เป็นศูนย์ เมื่อมีการ push ข้อมูลเข้าในสแตก ค่า Top จะเปลี่ยนเพิ่มขึ้นทีละหนึ่งทุกครั้งที่ทำการ push
โดยสามารถเขียนขั้นตอนวิธีการ push ได้ดังนี้
Procecdre push(var S: stack; X : itemtype);
Begin
If top > = upperbound then Writeln('Stack Full')
Else
Begin
Top := top +1;
S[top] := X;
End;
End;
การดึงข้อมูลจากสแตก (Popping Stack)
การดึงข้อมูลออกจากสแตก หมายถึงการนำข้อมูลที่อยู่บนสุดในสแตกหรือที่ชี้ด้วยท๊อปออกจากสแตก จะสามารถ pop สแตกได้เรื่อย ๆ จนกว่าสแตกจะว่าง
นิยาม pop(S)
ถ้าให้ S เป็นสแตก ขบวนการ pop(S) คือการนำข้อมูลบนสุดในสแตกออกจากสแตกและให้ค่าเป็นข้อมูลที่นำออกจากสแตก ดังนั้นถ้านำคำสั่ง X= pop(S) ก็คือการนำข้อมูลที่ท๊อปของสแตกมา และใส่ค่าไว้ที่ X หรือการเซตค่า X ให้เท่ากับข้อมูลที่ดึงจากสแตก
โดยเขียนขั้นตอนวิธีการ pop ได้ดังนี้
Function Pop (VarS: stack) : itemtype;
Begin
If empty(s) Then Writeln('Stack Empty')
Else Begin
Pop := S[top];
Top := top -1;
End;
End;
การว่างของสแตก
นิยาม empty(s)
ถ้า S เป็นสแตก ขบวนการ empty(S) จะส่งผลเป็นจริง (true) เมื่อสแตกว่าง และส่งผลเป็นเท็จ (false) เมื่อสแตกไม่ว่าง
การประยุกต์ของสแตก
สแตกเป็นโครงสร้างข้อมูลที่มีประโยชน์มาก ถูกนำไปใช้ทั้งในซอฟท์แวร์ระบบ (System Software) และในการประยุกต์โดยยูสเซอร์ เช่น ช่วยคอมไพเลอร์ (Compiler) สร้างกฏเกณฑ์ของการโปรแกรมมิ่งเกี่ยวกับการเรียกโปรแกรมย่อย กฏเกณฑ์ของการโปรแกรมมิ่งอีกอย่างคือ คำสั่งเงื่อนไขซ้อน (Nested IF) ก็เช่นกัน สแตก ช่วยบอกว่า Else นี้คู่กับ IF ใด ซึ่งมีกฏเกณฑ์ว่า Else แรกจะคู่กับ If หลังสุด และ Else ถัดไป ก็จะคู่กับ IF ที่ถัดขึ้นไป จาก IF หลังสุด
การแปลงนิพจน์ Infix ให้เป็น Postfix
ผู้เขียนโปรแกรมสั่งให้เครื่องคำนวณต้องเขียนนิพจน์ที่ต้องการไปในตัวโปรแกรม ซึ่งนิพจน์เหล่านี้เรียกว่า นิพจน์ Infix คือนิพจน์ที่มีโอเปอร์เรเตอร์ (Operator) อยู่ระหว่างโอเปอร์แรนด์ (Operand) ทั้งสอง เช่น A+B เครื่องหมาย + เป็นโอเปอร์เรเตอร์ระหว่างโอเปอร์แรนด์ A และ B ซึ่งเห็นว่าเป็นนิพจน์ที่มนุษย์คุ้นเคย ข้อเสียของนิพจน์ infix ทีททำให้คอมไพเลอร์ยุ่งยาก คือลำดับความสำคัญของโอเปอร์เรเตอร์ (Precedence) ที่ต่างกัน เช่นเครื่องหมายยกกำลัง (ใช้ ^ ในการเขียนโปรแกรม) มีความสำคัญมากกว่าเครื่องหมายคูณ และหาร และเครื่องหมายคูณและหารมีความสำคัญมากกว่าเครื่องหมายบวกและลบ
Operator คือเครื่องหมายกระทำ + - * / ^
Operand คือตัวแปรต่าง ๆ A,B,C,D,E เช่น A+B*C,(A*B)-C
ลำดับความสำคัญ Operator
- เครื่องหมายยกกำลัง ^
- เครื่องหมายคูณกับหาร *,/
- เครื่องหมายบวกกับลบ +,-
- เครื่องหมายวงเล็บ () กระทำก่อนเช่น A+(B*C)
- เครื่องหมายระดับเดียวกันไม่มีวงเล็บให้ทำจากซ้ายไปขวา เช่น A+B+C
เมื่อการประมวลนิพจน์ infix เป็นไปด้วยความยากที่การคำนวณไม่เป็นไปตามลำดับของเครื่องหมายโอเปอร์เรเตอร์ที่มีก่อนหลัง คอมไพเลอร์จึงแปลงนิพจน์ infix ให้เป็น postfix เสียก่อน
นิพจน์ Postfix ก็คือนิพจน์ที่มีโอเปอเรเตอร์อยู่หลังโอเปอร์แรนด์ทั้งสองของมัน เช่น
AB+ หมายถึง A+B
AB- หมายถึง A-B
AB* หมายถึง A*B
อัลกอริทึมแปลงนิพจน์ Infix ให้เป็นนิพจน์ Postfix
เนื่องจากนิพจน์ infix มีลำดับความสำคัญของเครื่องหมายโอเปอร์เรเตอร์ซึ่งหมายความว่าโอเปอร์เรเตอร์ที่มาก่อนอาจจะไม่ใช่โอเปอร์เรเตอร์ที่ถูกประมวลผลก่อน ดังนั้น สแตกซึ่งมีคุณสมบัติเป็น LIFO List จึงมีส่วนช่วยในการแปลงนิพจน์ infix ให้เป็นนิพจน์ postfix ในการนี้มีสิ่งที่เกี่ยวข้อง 3 อย่างคือหนึ่งข้อมูลเข้ามาซึ่งเป็นนิพจน์ infix สองข้อมูลออกหรือผลลัพธ์คือนิพจน์ Postfix โดยอัลกอริทึมมีดังนี้
- ถ้าข้อมูลเข้า (input character) เป็นโอเปอร์แรนด์ให้พิมพ์ออกเป็นผลลัพธ์ (postfix string)
- ถ้าข้อมูลเข้าเป็นโอเปอร์เรเตอร์ ทำดังนี้
1.1 ถ้าสแตกยังว่างอยู่ในpush โอเปอร์เรเตอร์ลงสแตก
1.2 ถ้าสแตกไม่ว่างให้เปรียบเทียบ โอเปอร์เรเตอร์ที่เข้ามากับโอเปอร์เรเตอร์ที่ท๊อปของสแตก
2.2.1ถ้าโอเปอร์เรเตอร์ที่เข้ามามี precedence น้อยกว่าหรือเท่ากับโอเปอร์เรเตอร์ที่ท๊อปของสแตก ให้ pop สแตกไปเป็นผลลัพธ์และเปรียบเทียบกับโอเปอร์เรเตอร์ที่ท๊อปของสแตกต่อไป หยุดเมื่อโอเปอร์เรเตอร์ทีเป็นข้อมูลเข้ามี precedence มากกว่าโอเปอร์เรเตอร์ ที่ท๊อปของสแตก หลังจากนั้นให้ push ข้อมูลลงสแตก
2.2.2 ถ้าโอเปอร์เรเตอร์เข้ามี precedence มากกว่า โอเปอร์เรเตอร์ที่ท๊อปของสแตก ให้ push ลงสแตก
3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิด ให้ push ลงสแตก
4.ถ้าข้อมูลเข้าเป็นวงเล็บปิดให้ pop สแตกจนกว่าจะถึงวงเล็บเปิดและนำผลที่ pop ออกไปเป็นผลลัพธ์ โดยทิ้งวงเล็บปิดและเปิดไป
5. ถ้าข้อมูล หมด ให้ pop สแตกไปไว้เป็นผลลัพธ์จนสแตกว่าง
การแปลงนิพจน์ Infix เป็น Postfix
1. นิพจน์ A+B*C-D
Infix Stack Postfix
A A
+ + A
B + AB
* +* AB
C +* ABC
- - ABC*+
D - ABC*+D
ABC*+D-
2. นิพจน์ (A+B)*C-D
Infix Stack Postfix
( (
A ( A
+ (+ A
B (+ AB
) ( ) AB+
* * AB+
C * AB+C
- - AB+C*
D - AB+C*D
AB+C*D-
ไม่มีความคิดเห็น:
แสดงความคิดเห็น