วิชาโครงสร้างข้อมูลและอัลกอริทึม: โครงสร้างข้อมูลแบบสแตก

โครงสร้างข้อมูลแบบสแตก

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

โครงสร้างข้อมูลแบบสแตก (Stack)

สแตกเป็นโครงสร้างข้อมูลที่ถูกกล่าวถึงมากโครงสร้างหนึ่ง ซึ่งมักจะใช้เป็นประโยชน์ในการอินเตอร์รัพต์ การกระโดดไปมาระหว่างโปรแกรมย่อย การเขียนโปรแกรมแบบเรียกใช้ตัวเอง (recursive) นอกจากนั้นแล้วโครงสร้างข้อมูลชนิดนี้มักจะใช้ช่วยในการเข้าไปในโครงสร้างแบบพิเศษ เช่น เครือข่าย หรือต้นไม้ โดยจะช่วยในการจำเส้นทาง และงานที่เรานำโครงสร้างแบบสแตกแล้วเราพบเห็นบ่อยๆ คือ การยกเลิกคำสั่ง (Undo) ในไมโครซอฟท์เวิร์ด
สแตกเป็นโครงสร้างแบบเชิงเส้น ที่มีลักษณะที่ว่า การนำข้อมูลเข้าสู่สแตก (insertion) และการนำข้อมูลออกจากสแตก (deletion) สามารถจะทำได้ที่ปลายด้านหนึ่งของลิสท์ที่แทนสแตกเท่านั้น ดังนั้นอันดับของการนำสมาชิกเข้าและออกจากสแตกมีความสำคัญ คือ สมาชิกที่เข้าไปอยู่ในสแตกก่อนจะออกจากสแตกหลังสมาชิกที่เข้าไปใน สแตกทีหลัง นั่นคือ การเข้าทีหลังออกก่อน จึงเรียกลักษณะแบบนี้ว่า LIFO (Last In First Out)

สแตกประกอบด้วยส่วนสำคัญ ๆ 2 ส่วน คือ

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

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

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

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

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

ALGORITHM PUSH

เพื่อใช้ในการแทรกข้อมูล x เข้า Stack โดยที่

TOP แทน ตัวชี้สแตก

N แทน จำนวนช่องของสแตก

X แทน ข้อมูล

ST แทน สแตก

1. [ ตรวจสอบ Overflow ]
IF TOP >= N THEN
PRINT “ STACK OVERFLOW “
EXIT
ENDIF

2. [ เพิ่มค่า Stack Pointer ]
TOP = TOP + 1

3. [ แทรกข้อมูลเข้า Stack ]
ST (TOP) = X

4. [ จบการทำงาน ]
EXIT

การ POP
เป็นการกระทำหรือการทำงานของสแตกที่นำข้อมูลที่เก็บอยู่ในสแตกออกจากสแตกมาใช้งาน โดยการ POP นี้ เมื่อทำการ POP ข้อมูลนั้นออกจากสแตกแล้ว จะต้องมีการจัดการให้ตัวชี้สแตกชี้ไปยังช่องหรือตำแหน่งก่อนหน้าข้อมูลที่ได้ทำการ POP ข้อมูลออกไป
การ POP ข้อมูลนี้จะทำการนำข้อมูลในส่วนบนสุดของสแตกออกไปทำงานตามต้องการ แต่การ POP ข้อมูลนี้จะไม่สามารถ POP ข้อมูลออกจากสแตกที่ว่างเปล่าหรือไม่มีข้อมูลได้ ถ้าเราพยายาม POP ข้อมูลออกจากสแตกที่ว่างเปล่า จะเกิด Error ที่เรียกว่า Stack Underflow

ALGORITHM POP
เพื่อใช้ในการลบข้อมูล x จาก Stack โดยที่
TOP แทน ตัวชี้สแตก
N แทน จำนวนช่องของสแตก
Y แทน ข้อมูล
ST แทน สแตก

1. [ ตรวจสอบ Underflow ]
IF TOP <= 0 THEN
PRINT “ STACK UNDERFLOW “
EXIT
ENDIF

2. [ นำข้อมูลที่ต้องการออกจาก Stack เก็บไว้ที่ Y ]
Y = ST (TOP)

3. [ ลดค่า Stack Pointer ]
TOP = TOP - 1

4. [ จบการทำงาน ]
EXIT

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

การประยุกต์ใช้งานของสแตก
สแตกเป็นโครงสร้างที่มีประโยชน์มาก ถูกนำไปประยุกต์ใช้ในหลายๆ ด้าน เช่น

1. การจัดการหน่วยความจำ
โดยทั่วไปการจัดการหน่วยความจำจะเป็นดังนี้

Reserved By System	Programs And procedures	Dynamic Varible Heap	Local Variable stack	Operating system
Low Memory		Available space		High Memory

ลองมาดูตัวอย่างของการจัดเก็บค่าของตัวแปรในหน่วยความจำในตัวอย่าง

1 ----> main () { // Start main ()

int P, Q, R; // User defined

2 ----> void A (void) { // Start function A

int S; // User defined

3 ----> B() ;

7 ----> } // End function A

3 ----> void B (void) { // Start function B

struct list {

int data;

struct list *link;

} node;

struct list *D ;

int X, Y; //User defined

4 ----> new(D);

new(D);

5 ----> new (D);

6 ----> } // End function B

2 ----> A;

8 ----> } // End main ()

ภาพของค่าของตัวแปรในหน่วยความจำเมื่อกำลังประมวลผลโปรแกรม ณ จุดต่างๆ เป็น ดังนี้

1. เมื่อเริ่มทำงานในส่วน main() เนื้อที่หน่วยความจำในสแตกจะถูกใช้สำหรับตัวแปร P, Q, R

Reserved By System	Programs And procedures				P Q R	Operating system
Low Memory		Top of heap				Top of stack

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

Reserved By System	Programs And procedures				S	P Q R	Operating System
Low Memory		Top of heap				Top of stack

3. เมื่อเรียกใช้ฟังก์ชั่น B จะเข้าไปทำงานในส่วนของฟังก์ชั่น B และเนื้อที่หน่วยความจำในสแตกจะถูกใช้สำหรับตัวแปร X, Y

Reserved By System	Programs And procedures		X Y	S	P Q R	Operating system
Low Memory		Top of heap		Top of stack

4. หลังคำสั่ง new (D)

Reserved

System

Programs

And

procedures

Operating

system

Low Memory

Top of heap

Top of stack

5. หลังคำสั่ง new (D)

Reserved

System

Programs

And

procedures

Operating

system

Low Memory

Top of heap

Top of stack

6. หลังจากเสร็จสิ้นการประมวลผลของฟังก์ชั่น B (ตัวแปร X, Y จะถูก Pop ออกจาก สแตก )

Reserved

System

Programs

And

procedures

Operating

system

Low Memory

Top of heap

Top of stack

ข้อสังเกต ถ้าเราเรียกใช้ตัวแปรแบบไดนามิกและเราไม่ได้ทำการ delete เมื่อไม่ต้องการใช้แล้ว (เช่นเราออกจากฟังก์ชั่น B แล้ว ) เนื้อที่ใน heap ก็จะเสียไปไม่สามารถนำมาใช้ได้อีก

2. การใช้สแตกในกระบวนการเรียกใช้โพรซีเจอร์หรือฟังก์ชัน

สแตกเป็นโครงสร้างข้อมูลที่มีประโยชน์มาก ถูกนำไปใช้ทั้งในซอฟท์แวร์ระบบ (System Software) และในการประยุกต์โดยยูสเซอร์ (user) เช่น ช่วยคอมไพเลอร์ (Compiler) สร้างกฏเกณฑ์ของโปรแกรมมิ่งเกี่ยวกับการเรียกโปรแกรมย่อย (Subprogram call) ที่ว่าโปรแกรมย่อยใดที่ถูกเรียกทำงานที่หลังสุด ต้องทำงานเสร็จก่อน ดังรูป

	.		.	.
	.		.	.
	CALL B		.	.
1000	.		.	.
	.		CALL C	.
	.	4200	.	.

โปรแกรม A โปรแกรม B โปรแกรม C



		4200	TOP
1000	TOP	1000

สแตกที่ใช้เก็บแอดเดรสของโปรแกรม

จากรูปแสดงการเรียกใช้โปรแกรมย่อย B และ C โดยในโปรแกรมหลัก A มีคำสั่งเรียกโปรแกรมย่อย B และในโปรแกรมย่อย B มีคำสั่งเรียกโปรแกรมย่อย C โปรแกรมย่อย C ต้องถูกกระทำเสร็จก่อน ตามมาด้วยโปรแกรมย่อย B และโปรแกรมหลัก A ซึ่งลำดับของการทำงานของคำสั่งแสดงด้วยลูกศร โดยสแตกช่วยเก็บที่อยู่ของคำสั่งถัดจากคำสั่งเรียกใช้โปรแกรมย่อย ซึ่งคำสั่งนี้จะเป็นคำสั่งที่ถูกทำงานต่อหลังจากได้ทำงานตามคำสั่งในโปรแกรมย่อยที่เรียกไป จากรูปสมมติว่าในขณะทำงานคำสั่งถัดจาก CALL B ในโปรแกรมหลัก A อยู่ ณ แอดเดรส 1000 และที่อยู่ของคำสั่งถัดจาก CALL C ในโปรแกรมย่อย B อยู่ ณ แอดเดรส 4200 เมื่อโปรแกรมหลัก A ทำงานมาถึงคำสั่ง CALL B แอดเดรส 1000 จะถูก PUSH ลงสู่สแตก และเช่นกันเมื่อโปรแกรมย่อย B ถูกทำงานมาถึงคำสั่ง CALL C แอดเดรส 4200 จะถูก PUSH ลงสู่สแตก ดังรูป ดังนั้นหลังจากทำงานตามคำสั่งในโปรแกรมย่อย C จนหมดแล้ว แอดเดรสของคำสั่งถัดไปที่จะถูกทำงานจะถูก POP ออกจากสแตก คือคำสั่งที่แอดเดรส 4200 และเมื่อจบโปรแกรมย่อย B คำสั่งที่จะถูกทำงานต่อไปจะถูก POP ออกจากสแตกเช่นเดียวกัน คือคำสั่งที่แอดเดรส 1000

3. การตรวจสอบอักขระสมดุล (Balancing Symbol)
ผู้ที่มีประสบการณ์ในการเขียนโปรแกรมมาแล้ว จะพบว่าสิ่งที่เรามักจะหลงลืมเมื่อเขียนโปรแกรม และทำให้เกิดข้อผิดพลาด
4. การแปลงนิพจน์ infix ให้เป็น postfix
โดยปกติเวลาเขียนโปรแกรมสั่งให้เครื่องคำนวณต้องเขียนนิพจน์ที่ต้องการไปในตัวโปรแกรม ซึ่งนิพจน์เหล่านี้เรียกว่า นิพจน์ 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

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

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

1. ข้อมูลเข้าซึ่งเป็นนิพจน์ infix
2. ข้อมูลออกหรือนิพจน์ postfix
3. สแตกที่ใช้เก็บโอเปอร์เรเตอร์
ข้อมูลเข้าจะถูกอ่านมาทีละอักขระ (character) แล้วดำเนินการต่อไปดังนี้
1. ถ้าข้อมูลเข้า (input character) เป็นโอเปอร์แรนด์ ให้พิมพ์ออกเป็นผลลัพธ์ (postfix string)
2. ถ้าข้อมูลเข้าเป็นโอเปอร์เรเตอร์ ให้ทำดังนี้
2.1 ถ้าสแตกยังว่างอยู่ ให้ PUSH โอเปอร์เรเตอร์ลงสแตก
2.2 ถ้าสแตกยังไม่ว่าง ให้เปรียบเทียบ โอเปอร์เรเตอร์ที่เข้ามากับโอเปอร์เรเตอร์ที่ ท็อปของสแตก
2.2.1 ถ้าโอเปอร์เรเตอร์ที่เข้ามามี precedence น้อยกว่าหรือเท่ากับโอเปอร์เรเตอร์ที่ท็อปของสแตก ให้ POP โอเปอร์เรเตอร์จากสแตกไปเป็นผลลัพธ์ และเปรียบเทียบกับโอเปอร์เรเตอร์ที่ท็อปของสแตกต่อไป หยุดเมื่อโอเปอร์เรเตอร์ที่เป็นข้อมูลเข้ามี precedence มากกว่าโอเปอร์เรเตอร์ที่ ท็อปของสแตก หลังจากนั้นให้ PUSHข้อมูลลงสแตก
2.2.2 ถ้าโอเปอร์เรเตอร์ที่เข้ามามี precedence มากกว่าโอเปอร์เรเตอร์ที่ท็อปของสแตก ให้ PUSH ลงสแตก
3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิดให้ PUSH ลงสแตก
4. ถ้าข้อมูลเข้าเป็นวงเล็บปิดให้ POP ออกจากสแตกจนกว่าจะถึงวงเล็บเปิด และนำผลที่ POP ออกไปเป็นผลลัพธ โดยทิ้งวงเล็บปิดและเปิดทิ้งไป
5. ถ้าข้อมูลหมด ให้ POP Operator ที่ยังคงเหลือในสแตกไปไว้เป็นผลลัพธ์จนสแตกว่าง

ตัวอย่างของการแปลงนิพจน์ Infix เป็น Postfix
นิพจน์ Infix : A – B * C

INPUT	STACK	OUTPUT
A		A
-	-	A
B	-	AB
*	-*	AB
C	-*	ABC
		ABC*-

นิพจน์ Postfix ที่ได้ คือ : ABC*-

นิพจน์ Infix : A * (B + C)

INPUT	STACK	OUTPUT
A		A
*	*	A
(	* (	A
B	* (	AB
+	* ( +	AB
C	* ( +	ABC
)	*	ABC+
		ABC+*

นิพจน์ Postfix ที่ได้ คือ : ABC+*

นิพจน์ Infix : A ^B ^ (C + D)

INPUT	STACK	OUTPUT
A		A
^	^	A
B	^	AB
^	^ ^	AB
(	^ ^ (	AB
C	^ ^ (	ABC
+	^ ^ ( +	ABC
D	^ ^ ( +	ABCD
)	^ ^	ABCD +
		ABCD + ^ ^

นิพจน์ Postfix ที่ได้ คือ : ABCD+^^

นอกจากวิธีการแปลงนิพจน์ Infix เป็น Postfix ตามข้างต้นแล้ว ยังสามารถทำได้ด้วยตนเองโดยไม่อาศัย Stack ก็ได้ ซึ่งมีวิธีการดังนี้
1. เข้าวงเล็บนิพจน์ Infix ให้ครบตามลำดับการคำนวณ
2. ย้าย Operator ทั้งหมดไปแทนที่เครื่องหมายวงเล็บปิดที่สอดคล้องกับ Operator นั้น ตามลำดับ
3. ลบเครื่องหมายวงเล็บเปิดให้หมด จะได้นิพจน์ Postfix

การหาค่าผลลัพธ์จากนิพจน์ Postfix
การหาค่าทางคณิตศาสตร์จากนิพจน์ Postfix มีขั้นตอนใหญ่ ๆ 2 ขั้นตอน คือ
1. ถ้าเป็น Operand ให้ PUSH ลงสู่สแตก
2. ถ้าเป็น Operator ให้ POP ค่า 2 ค่า จากสแตก แล้วดำเนินการโดยใช้ Operator ตัวนั้น ในการนี้ให้ใช้ค่าแรกที่ได้จากสแตกเป็น Operand ตัวที่ 2 จากนั้นก็เก็บค่าผลลัพธ์ในสแตก

ตัวอย่างของการแปลงหาค่านิพจน์ Postfix
นิพจน์ Postfix : 1 6 3 / 4 * + 7 –

INPUT	CALCULATE	STACK
1		1
6		1 6
3		1 6 3
/	6 / 3	1 2
4		1 2 4
*	2 * 4	1 8
+	1 + 8	9
7		9 7
-	9 - 7	2

ผลลัพธ์ที่ได้ คือ : 2

สรุปขั้นตอนในการหาผลลัพธ์ของนิพจน์ Postfix
1. ค้นหาเครื่องหมายดำเนินการทางซ้ายสุด ของนิพจน์
2. เลือกตัวถูกดำเนินการ 2 ตัว ที่อยู่ติดกับเครื่องหมายดำเนินการทางซ้าย
3. ประมวลผลตามเครื่องหมายดำเนินการนั้น
4. แทนที่เครื่องหมายดำเนินการและตัวถูกดำเนินการ ด้วยผลลัพธ์ที่ได้
5. รีเคอร์ซีฟโปรแกรมมิ่ง

สแตกนอกจากจะใช้จัดการกับการเรียกใช้โปรแกรมย่อยแล้ว ในบางภาษายังใช้จัดการกับการรีเคอร์ชั่น (recursion) หรือการเรียกใช้ตัวเอง
ในการเขียนโปรแกรมที่ต้องทำซ้ำซ้อน สามารถทำได้โดยการใช้หลักการทำซ้ำซ้อนด้วย LOOP การเขียนโปรแกรมแบบนี้เรียกว่า โปรแกรมวนซ้ำ (iterative) และแบบรีเคอร์ซีฟ (recursive) คือกระบวนการที่ฟังก์ชั่นหรือโปรแกรมเรียกตัวเองซ้ำๆ จนกว่าจะถึงเงื่อนไขที่กำหนด ซึ่งจะใช้การประมวลผลแบบนี้กับการคำนวณ ที่แต่ละขั้นตอนอยู่ในรูปของผลลัพธ์ที่ได้จากขั้นตอนก่อนหน้า ปัญหาที่ต้องทำซ้ำ ส่วนมากจะเขียนในรูปแบบนี้ได้ เบื้องหลังการโปรแกรมแบบรีเคอร์ซีฟคือ หลักการที่เรียกว่า รีเคอร์ชั่น (recursion) ซึ่งหมายถึงการนิยามปัญหาหรือนิยามสูตรคณิตศาสตร์ของสิ่งหนึ่งโดยใช้ตัวมันเอง ตัวอย่างที่ใช้บ่อยคือ การหาค่าแฟกทอเรียล

ฟังก์ชั่นแฟกทอเรียล
ผลคูณของเลขจำนวนเต็ม 1 ถึง n เรียกว่า n แฟกทอเรียล สามารถแสดงโดย n!

n! = 1 * 2 * 3 …. (n-2) * (n-1) * n

เพื่อความสะดวก กำหนด 0! = 1 ดังนั้น ฟังก์ชั่นจะไม่มีค่าเป็นลบ ซึ่งเราจะได้

0! = 1 1! = 1 2! = 1 * 2 = 2

3! = 1 * 2 * 3 = 6 4! = 1 * 2 * 3 * 4 = 24

5! = 1 * 2 * 3 * 4 * 5 = 120 6! = 1 * 2 * 3 * 4 * 5 = 720 และต่อ ๆ ไป

สังเกต

5! = 5 * 4! = 5 * 24 = 120

และ

6! = 6 * 5! = 6 * 120 = 720

นั่นคือ ทุก ๆ ค่าของ n ที่เป็นบวกจะได้

n! = n * (n – 1)!

ดังนั้นฟังก์ชั่นแฟกทอเรียลจะกำหนดได้ดังนี้

(a) if n = 0 then n! = 1

(b) if n > 0 then n! = n (n – 1)!

สังเกตว่านิยามนี้ n! เป็นรีเคอร์ซีฟ เนื่องจากมีการเรียกใช้ตัวเอง เมื่อใช้ (n – 1)! แต่อย่างไรก็ตาม
ตัวอย่าง จงหาค่า 4!
ในกรณีที่ใช้วิธีการแก้ปัญหาแบบการวนซ้ำ ก็คือ

4! = 4 * 3 * 2 * 1 = 24

ในกรณีที่ใช้วิธีการแก้ปัญหาแบบรีเคอร์ชั่น ก็คือ

1. 4! = 4 * 3!

2. 3! = 3 * 2!

3. 2! = 2 * 1!

4. 1! = 1 * 0!

5. 0! = 1

6. 1! = 1 * 1 = 1

7. 2! = 2 * 1 = 2

8. 3! = 3 * 2 = 6

9. 4! = 4 * 6 = 24

Step 1 การหาค่าของ 4! ทำได้โดยนำ 4 * 3! ซึ่งเราจะยังไม่หาค่าของ 4! จนกว่าจะทราบค่าของ 3!

Step 2 การหาค่าของ 3! ทำได้โดยนำ 3 * 2! ซึ่งเราจะยังไม่หาค่าของ 3! จนกว่าจะทราบค่าของ 2!

Step 3 การหาค่าของ 2! ทำได้โดยนำ 2 * 1! ซึ่งเราจะยังไม่หาค่าของ 2! จนกว่าจะทราบค่าของ 1!

Step 4 การหาค่าของ 1! ทำได้โดยนำ 1 * 0! ซึ่งเราจะยังไม่หาค่าของ 1! จนกว่าจะทราบค่าของ 0!

Step 5 จากนิยาม ค่าของ 0! เท่ากับ 1

Step 6 เป็นการทำกลับโดยนำค่า 0! ซึ่งเท่ากับ 1 ไปแทนในการหาค่า 1! จะได้ค่า 1! = 1 * 1 = 1

Step 7 เป็นการทำกลับโดยนำค่า 1! ซึ่งเท่ากับ 1 ไปแทนในการหาค่า 2! จะได้ค่า 2! = 2 * 1 = 2

Step 8 เป็นการทำกลับโดยนำค่า 2! ซึ่งเท่ากับ 2 ไปแทนในการหาค่า 3! จะได้ค่า 3! = 3 * 2 = 6

Step 9 เป็นการทำกลับโดยนำค่า 3! ซึ่งเท่ากับ 6 ไปแทนในการหาค่า 4! จะได้ค่า 4! = 4 * 6 = 24

ถ้าให้ FACT (n) แทนฟังก์ชันที่ใช้คำนวณหาแฟกทอเรียลของ n จะเขียนได้ว่า

FACT (n) = n * FACT (n – 1)

ถ้าต้องการหา FACT (4) จะต้องผ่านการคำนวณ ดังนี้

FACT (4) = 4 * FACT (3)

FACT (3) = 3 * FACT (2)

FACT (2) = 2 * FACT (1)

FACT (1) = 1 * FACT (0)

รูปข้างล่างแสดงสแตกช่วยในการหา n! เมื่อ n = 4 โดยที่สแตกเก็บค่า n และ FACT(n-1) ไว้ในแต่ละครั้งที่มีการหาค่า FACT (n) ใด ๆ เนื่องจากในแต่ละขั้นยังไม่สามารถคำนวณได้ จนกว่าจะได้ค่า FACT (0) จึงต้อง PUSH ค่า n และ FACT (n – 1) ไว้ในสแตก เมื่อถึงจุดที่หาค่า FACT (0) ซึ่งมีค่าเป็น 1


									1!	1	FACT (0)
						2!	2	FACT (1)	2!	2	FACT (1)
			3!	3	FACT (2)	3!	3	FACT (2)	3!	3	FACT (2)
4!	4	FACT (3)	4!	4	FACT (3)	4!	4	FACT (3)	4!	4	FACT (3)

เมื่อหาค่า FACT (0) ได้แล้ว ก็ให้ POP ข้อมูลที่จะนำไปใช้ออกจากสแตก



2!	2	1
3!	3	FACT (2)	3!	3	2
4!	4	FACT (3)	4!	4	FACT (3)	4!	4	6

วิชาโครงสร้างข้อมูลและอัลกอริทึม

วันพุธที่ 14 กันยายน พ.ศ. 2559

โครงสร้างข้อมูลแบบสแตก

4200

TOP

INPUT

STACK

INPUT

STACK

INPUT

STACK

INPUT

CALCULATE

ไม่มีความคิดเห็น:

แสดงความคิดเห็น