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

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

โครงสร้างสแตกข้อมูลที่รู้จักและนำมาใช้งานชนิดหนึ่งก็คือ สแตก (Stack) มีลักษณะเป็นรายการในแนวเชิงเส้น(Linear List) รูปแบบหนึ่ง และมีข้อกำหนดให้ชุดปฏิบัติการ สามารถเพิ่มและลบรายการเพียงด้านเดียว ซึ่งเป็นด้านบนสุดของสแตก (Top of Stack)

เรียกว่าตัวชี้สแตก (Stack Pointer) มีรูปแบบเป็น (Top)(S)โดยสแตกมีการกำหนดเป็นรูปแบบดังนี้

S = [s1 ,S2, … ,ST]

ด้านบนสุดของสแตกจะอยู่ที่ Top (S) =ST และมีจำนวนสมาชิกในสแตกเท่ากับ T

ดังในรูปที่ 4.1

ST

…

S2

S1

รูปที่ 4.1 ตัวอย่างลักษณะสแตกที่มีสมาชิกเท่ากับ T มีตัวชี้สแตก Top

ปัญหาที่ 1  เนื่องจากคอมพิวเตอร์ทำงานในรูปแบบของเลขฐาน 2 แต่ในส่วนของผู้ใช้งานจะเป็นเลขฐาน 10 จึงต้องแปลงค่าจากเลขฐาน 10 ไปเป็นเลขฐาน 2 เช่น เปลี่ยนจาก 26 เป็น 11010

ปัญหาที่ 2  คอมไพเลอร์ (Compiler) จะต้องคำนวณนิพจน์ (Expression) ทางคณิตศาสตร์ที่มีเครี่องหมายวงเล็บเปิดและปิดเข้ามาเกี่ยวข้อง

ปัญหาที่ 3  โปรแกรมเกมเล่นไพ่ (Card Game) จะมีที่วางกองไพ่และการแจกไพ่ได้เฉพาะใบที่อยู่บนสุด

ปัญหาที่ 4  รูปแบบปัญหาการทำงานบางอย่าง  เช่น  การทำงานของ  Switching Box ของเครือข่าย หรือรูปแบบการสลับตู้รถไฟบนราง  ดังในรูปที่ 4.3

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

การปฏิบัติการของสแตก

จากลักษณะดังที่กล่างมาของสแตก  จะต้องมีการปฏิบัติการเข้ามาช่วยการทำงานของสแตกให้มีความถูกต้อง

1.    CreateStack( ) ใช้สร้างสแตกใหม่ขึ้นมาใช้งานและกำหนดค่าเริ่มต้นต่าง ๆ

2.    Push(value,  stack)  ใช้เพิ่มค่าใหม่เก็บลงในสแตกที่ใช้งานอยู่  มีอัลกอริทึมการทำงานเป็นดังในตารางที่ 4.1

ตารางที่ 4.1  อัลกอริทึมการเพิ่มค่าใหม่เก็บลงในสแตก

1.  ตรวจสอบสแตกว่าจะมีสมาชิกอยู่เต็มหรือไม่  โดยเปรียบเทียบค่า Top กับขนาดอาร์เรย์

2.  ถ้าสแตกไม่เต็ม

2.1  เพิ่มค่าให้กับ Top โดยการบวก 1

2.2  ทำการนำค่าที่ได้มาเก็บลงในสแตกในตำแหน่ง Top ไม่เช่นนั้นแจ้งกลับมาว่าสแตกเต็ม

3.  Pop(stack)  ใช้ดึงค่าออกจากสแตกที่ใช้งานอยู่และส่งค่า value กลับมาให้ มีอัลกอริทึมการ   ทำงานเป็นดังในตารางที่ 4.2

ตารางที่ 4.2  อัลกอริทึมดึงค่าออกจากสแตก

1.    ตรวจสอบว่าสแตกว่างหรือไม่ โดยเปรียบเทียบค่า Top กับขนาดอาร์เรย์

2.    ถ้าสแตกไม่ว่าง

2.1  ทำการดึงค่าในตำแหน่ง  Top ออกมาให้

2.2  ลดค่าของ Top โดยการลบ 1 ไม่เช่นนั้นแจ้งกลับมาว่าสแตกว่าง

3.  isEmpty(stack)  ใช้ตรวจสอบว่าสแตกที่ใช้งานอยู่ว่างหรือไม่  ถ้าไม่มีค่าเก็บไว้เลยจะส่งค่าจริงกลับให้

เมื่อนำสแตกมาใช้งานตามลำดับดังในรูป (a) ถึง (g) มีการทำงานโดยใช้ชุดปฏิบัติการ Push และ Pop ดังนี้

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

(b)   นำค่า  A  เข้ามาเก็บเป็นตัวแรกโดยใช้  Push(A) สแตก S = [A] ตัวชี้สแตก Top = A

(c)    นำค่า  B เก็บต่อโดยใช้ Push(B) สแตก S = [A,B] ตัวชี้สแตก Top = B

(d)นำค่า C เก็บต่อโดยใช้ Push(C) สแตก S = [A,B,C]ตัวชี้สแตก Top =C

(d)   ต้องการดึงค่าออกมาโดยใช้ Pop( ) สแตก S = [A,B] ตัวชี้สแตกTop = B

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

S = [A,B,D,E] ตัวชี้สแตก Top = E

(g) ดึงค่าออกมา 3 ค่าโดยใช้ Pop( )  3  ครั้งและเก็บค่า F โดยใช้ Push(F) สแตก S = [A,F] ตัวชี้สแตก Top = F

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

ตัวอย่างการใช้สแตก

จากปัญหาในตอนต้นกล่าวถึงปัญหาการเปลี่ยนเลขฐาน  10  เป็นเลขฐาน  2   เนื่องจากการคำนวณเป็นการหารเลขฐาน  10  เศษที่เหลือจะได้เป็นเลขฐาน  2  เมื่อนำมาแสดงผลจะเป็นตัวเลขจากซ้ายไปขวา  แต่เลขฐาน  2  เป็นตัวเลขจากขวาไปซ้ายจึงเกิดการสลับด้านกัน  จึงนำสแตกมาช่วยแก้ปัญหานี้  ดังในตารางที่ 4.3 คือ โปรแกรม Stack.c

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

การใช้สแตกแก้ปัญหาการแปลงนิพจน์คณิตศาสตร์

คอมไพเลอร์จะแปลงคำสั่งจากภาษาระดับสูง  (High-level  Language)  ไปเป็นภาษาเครื่อง(Machine Language) ส่วนหนึ่งที่ต้องแปลงคือนิพจน์คณิตศาสตร์ เช่น X = A * B + C ซึ่งมีลักษณะที่เรียกว่า  Infix  Notation  มีเครื่องหมายคำนวณอยู่ระหว่างโอเปอแร้น (Operand) โดยแปลงไปเป็นนิพจน์แบบPostfix  Notation มีเครื่องหมายคำนวณนำหน้าโอเปอแร้น แต่เนื่องจากนิพจน์แบบ Infix มีการนำเครื่องหมายวงเล็บเข้ามาใช้ทำให้ทิศทางการคำนวณเปลี่ยนไป   ดังในตารางที่ 4.4 เป็นตัวอย่างของการคำนวณแบบเดียวกัน

ตารางที่ 4.4  ลักษณะนิพจน์แบบ Infix, Postfix, และ Prefix Notation

Infix	Postfix	Prefix
A+(B*C)

(A+B)*C

A+B-C

(A+B)*(C-D)

(A+B)*C-(D-E) ) $ (F+G)ABC*+

AB+C*

AB+C-

AB+CD-*

AB+C*DE—FG+$+A*BC

*+ABC

-+ABC

*+AB-CD

$-*+ABC-DE+FG

การแปลงนิพจน์แบบ Infix เป็นแบบ  Postfix

เมื่อพิจารณาการแปลงนิพจน์แบบ Infix เป็นแบบ Postfix เป็นขั้นตอนการแปลงโดยเริ่มต้นจากสแกนนิพจน์Infix ทีละตัว  หากพบวงเล็บก็จะทำส่วนที่อยู่ในวงเล็บให้เสร็จก่อนเป็นนิพจน์ย่อย (Subexpression) ซึ่งจะได้เป็นอัลกอริทึมดังในตารางที่ 4.5

ตารางที่ 4.5  อัลกอริทึมการแปลงนิพจน์แบบ Infix เป็นแบบ Postfix

สร้างสแตกที่ว่างเปล่ายังไม่มีการเก็บค่า ถ้าค่าในนิพจน์ Infix ยังไม่หมด หรือเกิดข้อผิดพลาด ให้ทำดังนี้ a.       รับค่า  (Token) ตัวถัดไปในนิพจน์  Infix (ประกอบด้วย ค่าคงที่ ตัวแปร เครื่องหมายคำนวณ วงเล็บเปิดและปิด b.       ค่าที่รับเข้ามา ถ้าเป็น b.1  โอเปอแร้น (ค่าคงที่,ตัวแปร)                                  นำไปแสดงทางจอภาพ b.2  วงเล็บเปิด                                                               ให้นำใส่ลงในสแตก (Push) b.3  วงเล็บปิด                                                                 ดึงค่าออกจากสแตก (Pop) และนำไปแสดงทาง                      จอภาพ  ทำจนกว่าจะพบวงเล็บเปิด b.4  เครื่องหมายคำนวณ                                                 ถ้าสแตกว่าง  หรือค่าที่รับมามี Precedence สูงกว่าค่าบนสแตกให้นำใส่ลงในสแตก (Push) ถ้าหากค่าที่รับมามี Precedence น้อยกว่าค่าบนสแตกให้ดึงค่าออกจากสแตก (Pop) 3.  เมื่อทำจนค่าในนิพจน์ Infix หมด ให้ดึงค่าออกจากสแตก (Pop) แสดงทางจอภาพตามลำดับ จนกว่าสแตกว่าง

จากอัลกอริทึมดังกล่าวเมื่อนำมาใช้กับตัวอย่างนิพจน์ 7*8-(2+3) จะได้เป็นลำดับขั้นตอนดังในรูปที่ 4.4 หรือเขียนเป็นแบบตารางได้ดังในตารางที่ 4.6

ตารางที่ 4.6 การแปลงนิพจน์ 7*8-(2+3) เป็นนิพจน์ Postfix

นิพจน์ Infix	สแตก	นิพจน์ Postfix
7*8-(2+3)

*8-(2+3)

8-(2+3)

-(2+3)

(2+3)

2+3)

+3)

3)

) 

*

–

– (

–         ( +

-7

7 8

7 8 *

7 8 *2

7 8 *2 3

/ 8 *2 3 +

7 8 * 2 3 + –

การหาค่าคำตอบจากการคำนวณนิพจน์ Postfix

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

ตารางที่ 4.7  อัลกอริทึมการหาค่าคำตอบจากนิพจน์ Postfix

1.     สร้างสแตกที่ว่างเปล่ายังไม่มีการเก็บค่า

2.     ทำงานต่อไปนี้ซ้ำจนกว่าถึงจุดสิ้นสุดของนิพจน์

a.          รับค่า (Token) ตัวถัดไปในนิพจน์ RPN (ประกอยด้วย  ค่าคงที่  ตัวแปร  เครื่องหมายคำนวณ)

b.         ค่าที่รับเข้ามา  ถ้าเป็นโอเปอแร้น ให้นำใส่ลงในสแตก (Push) แต่ถ้าเป็นเครื่องหมายคำนวณให้ทำดังนี้

b.1  ดึงค่าออกจากสแตก (Pop) สองค่า ถ้าไม่ครบให้แจ้งเกิดข้อผิดพลาด

b.2  นำเครื่องหมายคำนวณทำการประมวลผลกับค่าทั้งสอง

b.3  นำผลลัพธ์ที่ได้ใส่กลับลงในสแตก (Push)

3.  เมื่อถึงจุดสิ้นสุดของนิพจน์ ค่าที่เป็นคำตอบจะอยู่บนสแตก ซึ่งมีเพียงค่าเดียวเท่านั้น

จากอัลกอริทึมดังกล่างเมื่อนำมาใช้กับตัวอย่างนิพจน์ 2 4 *9 5 + -จะเป็นตามลำดับขั้นตอนดังในรูปที่ 4.5 หรือเขียนเป็ฯแบบตารางได้ดังในตารางที่ 4.8

ตารางที่ 4.8 การหาค่าคำตอบจากนิพจน์

นิพจน์ Postfix	ค่าที่ได้	สแตก
2 4 * 9 5 + –

4 + 9 5 + –

* 9 5 + –

9 5 + –

5 + –

+ –

– 

2 * 4 = 8

9 + 5 = 14

8 – 14 = -62

2 4

8

8 9

8 9 5

8 14

-6

-6

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

1.โครงสร้างข้อมูลแบบสแตกจะแบ่งออกเป็น กี่ส่วน

ก.1 ส่วน คือ ตัวชี้สแตก ( Stack Pointer )

ข.2 ส่วน คือ ตัวชี้สแตก ( Stack Pointer )และสมาชิกของสแตก ( Stack Element )

ค.3ส่วน คือ ตัวชี้สแตก ,ตัวรับค่า ,ตัวเก็บค่า

ง.4ส่วน คือ ตัวชี้สแตก ,ตัวรับค่า ,ตัวเก็บค่า และตัว output

2 “ CreateStack( ) “ มีความจำเป็นเป็นอย่างไรสำหรับสแต็ก

ก. ใช้สร้างแสต็กขึ้นมาใช้งานใหม่           ข.เพิ่มค่าใหม่ของแสต็ก

ค.ใช้ทับค่าเดิมเข้าไปแทนที่               ง.ใช้สำหรับการตรวจสอบสแต็ก

3.ปัญหาของสแตกมีกี่ข้อ

ก.1ข้อ ข.2ข้อ

ค.3ข้อ ง.4ข้อ 

4. โครงสร้างสแตกข้อมูลที่รู้จักและนำมาใช้งานชนิดหนึ่ง และมีข้อกำหนดให้ชุดปฏิบัติการ สามารถเพิ่มและ ลบข้อมูลได้กี่ด้าน และจะต้องลบข้อมูล ด้านใด

ก. 3 ด้าน คือ ด้าน ขวา

ข. 4 ด่าน คือด้าน ล่าง

ค. ด้านเดียว คือด้าน บน

ง. 2 ด้าน คือด้าน ซ้าย

5.สแตก (Stack) มีลักษณะเป็นอย่างไร?

ก. เป็นเชิงเส้น

ข. เป็นเชิงเดี่ยว

ค. เป็นสี่เหลี่ยม

ง. เป็นวงกลม

6. การทำงานของสแตกเมื่อมีค่าใดส่งเข้ามาเป็นตัวสุดท้ายจะอยู่ที่ตำแหน่งใด

ก.ล่างสุด

ข.บนสุด

ค.ตรงกลาง

ง.ด้างข้าง

7.Push(value, stack) คืออะไร

ก.ใช้เพิ่มค่าใหม่เก็บลงในสแตกที่ใช้งานอยู่

ข.ใช้สร้างสแตกใหม่

ค.ใช้เลดค่าในสแตกที่ใช้งานอยู่

ง. ถูกทุกข้อ

8.คำสั่ง CreateStack( ) และ Push(value, stack) ใช้ทำอะไร

ก.CreateStack( ) ใช้สร้างสแตกใหม่ขึ้นมาใช้งานและกำหนดค่าเริ่มต้นต่าง ๆ , Push(value, stack)ใช้เพิ่มค่าใหม่เก็บลงในสแตกที่ใช้งานอยู่

ข.CreateStack( ) ใช้เพิ่มค่าใหม่เก็บลงในสแตกที่ใช้งานอยู่ , Push(value, stack) ใช้สร้างสแตกใหม่ขึ้นมาใช้งานและกำหนดค่าเริ่มต้นต่าง ๆ

ค.CreateStack( ) ใช้สร้างสแตกใหม่ขึ้นมาใช้งานและกำหนดค่าเริ่มต้นต่าง ๆ , Push(value, stack)ใช้แก้ไขค่าที่มีอยู่เก็บลงในสแตก

ง.ผิดทุกข้อ

9. จงแปลง 26 จากฐาน 10ไปเป็นฐาน 2 เท่ากับเท่าไร

ก. 11100 ค. 10100

ข. 01010 ง. 11010

10ด้านบนสุดของสแตก เรียกว่า?

ก.Stack

ข.Linear List

ค.Stack Pointer

ง.Top of Stack