สแตก

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

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

UNIT StackUA;

INTERFACE CONST Maxsize = 100 {User supplied};

TYPE KeyType = 1..100 {ID};

DataType = RECORD Name : string[20];

Math, Stat, Comp : integer; END;

StdElement = RECORD Key : KeyType;

{User supplied} Data : DataType;

{User supplied} END;

VAR S : ARRAY[1..Maxsize] OF StdElement;

Top : 0..Maxsize;

PROCEDURE Create;

PROCEDURE Push(E : StdElement);

PROCEDURE Pop(VAR E : StdElement);

FUNCTION Empty : boolean;

FUNCTION Full : boolean;

PROCEDURE Clear;

IMPLEMENTATION PROCEDURE Create;

BEGIN Top := 0; END;

PROCEDURE Push(E : StdElement);

BEGIN Top := Top + 1; S[Top] := E; END;

PROCEDURE Pop(VAR E : StdElement);

BEGIN END;

FUNCTION Empty : boolean;

BEGIN IF Top = 0 THEN Empty := true ELSE Empty := false; END;

FUNCTION Full : boolean;

BEGIN IF Top = Maxsize THEN Full := true ELSE Full := false END;

PROCEDURE Clear; BEGIN Top := 0 END; END.

การสร้าง Stack ด้วย Arrays โครงสร้างข้อมูลชนิด Arrays สามารถนำไปประยุกต์ใช้สร้างเป็น Stack ได้ แต่มีข้อแตกต่างกันคือ ข้อมูลแต่ละตัวที่ถูกเก็บใน Array สามารถเข้าถึง (access) ได้โดยตรง แต่ในหลักการของ Stack สมาชิกตัวบนสุดเท่านั้นที่จะสามารถ access ได้ในแต่ละครั้ง ดังนั้นจึงต้องมีตัวแปรสำหรับบ่งชี้สมาชิกตัวบนสุดใน Stack

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

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

ตัวอย่างINFO LINK โหนด P : NODE (P)

หมายถึง โหนดที่ถูกชี้โดยพอยน์เตอร์ P INFO (P) หมายถึง ส่วนที่เก็บข่าวสารหรือสมาชิกของโหนด P LINK (P) หมายถึง ส่วนตำแหน่งหรือที่อยู่ของโหนดถัดจากโหนด P

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

1. trav:=head;

2. while trav <> null do

3. begin print info (trav); trav := link(trav);

6. end; คำสั่งแรกให้พอยน์เตอร์trav ชี้ที่ต้นลิสต์ คำสั่งที่สองตรวจสอบว่าในระหว่างที่พอยน์เตอร์trav ยังไม่มีค่าเป็นnull ให้ทำตามคำสั่งในบรรทัดที่4 และ5 คือให้พิมพ์ข้อมูลในinfo ฟิลด์ของโหนดที่ชี้ด้วยtrav นั้นหลังจากนั้นเลื่อนพอยน์เตอร์trav ชี้โหนดถัดไป คำสั่งในบรรทัดที่2 ที่ถูกทำซ้ำๆจนกว่าเงื่อนไขในคำสั่งไม่เป็นจริงคือ จะหยุดทำงานในบรรทัดที่4 และ5 เมื่อพอยน์เตอร์trav = null คือtrav ชี้ตกลิสต์ไปแล้วการเพิ่มและลบข้อมูลในลิงค์ลิสต์ โอเปอร์เรชันพื้นฐานในลิงค์ลิสต์มี2 อย่างคือการเพิ่มข้อมูลและการลบหรือดึงข้อมูล ไม่ว่าจะเป็นการเพิ่มหรือลบข้อมูลทำได้2 จุดคือกระทำที่ต้นลิสต์ และกระทำที่หลังโหนดที่ชี้ด้วยp ใดๆการเพิ่มข้อมูลในลิงค์ลิสต์ หมายถึง การเพิ่มโหนดใหม่ที่บรรจุข้อมูลที่เพิ่มเข้าในลิงค์ลิสต์ และการลบข้อมูลในลิงค์ลิสต์หมายถึง การลบโหนดที่บรรจุข้อมูลที่ต้องการลบออกจากลิงค์ลิสต์ ดังนั้นจึงขอแสดงขั้นตอนการเพิ่มโหนดและการลบโหนดในลิงค์ลิสต์ จากลิงค์ลิสต์ที่ชี้ด้วยHead และมีNode (New) นี้ต้องการเพิ่มโหนด (New) ที่ต้นลิสต์มีขั้นตอนดังนี้

1. Link (New) := head

2. Head := Newเส้นไข่ปลาแสดงทางที่เกิดขึ้นพร้อมหมายเลขกำกับเพื่อแสดงลำดับของขั้นตอน แสดงผลลัพธ์ของการเพิ่มโหนดที่ต้นลิสต์ให้สังเกตว่าเราไม่สามารถสลับลำดับขั้นตอนเป็น

1. HEAD := NEW;

2. LINK (NEW) := HEAD;ลิสต์ว่างลิสต์ว่างเป็นลิสต์ที่มีสมาชิกเป็นโหนดว่างที่ได้จากโหนดที่ถูกนำออกจากลิสต์อื่นๆและจากลิสต์ว่างนี้เองถ้าผู้ใช้ต้องการเพิ่มโหนดเข้าไปลิสต์หนึ่งลิสต์ใดก็สามารถนำไปใช้ได้การเพิ่มโหนดเข้าลิสต์ว่างหรือการนำโหนดจากลิสต์ว่างนี้ไปใช้ไม่ว่าจะกระทำที่ต้นลิสต์หรือ ในตำแหน่งใดๆในลิสต์ ย่อมได้ผลที่เหมือนกัน (เนื่องจากเป็นโหนดว่าง ) ดังนั้นการเพิ่มโหนดในลิสต์ว่างและการนำโหนดจากลิสต์ที่เกิดขึ้นในหน่วยความจำโหนดแต่ละโหนดไม่จำเป็นต้องอยู่ติดกันการสร้างลิงค์ลิสต์ การสร้างลิงค์ลิสต์ หรือการนำข้อมูลเก็บในโครงสร้างลิงค์ลิสต์ก็คือ การเพิ่มลิสต์ข้อมูลเข้าลิสต์ ณตำแหน่งสุดท้ายตลอดจนข้อมูลหมดเช่น ลิสต์L = ( 5,6,7)เมื่ออยู่ในโครงสร้างลิงค์ลิสต์หน้าตาจะเป็นดังนี้^ 7 6 5 headเพื่อความสะดวกในการสร้างลิงค์ลิสต์ต้องอาศัยพอยน์เตอร์อีกตัวหนึ่งที่คอยชี้โหนดสุดท้ายของลิสต์ตลอดเวลาเพื่อที่เมื่อมีข้อมูลที่จะเก็บในลิงค์ลิสต์ก็เพียงแต่เชื่อมต่อเข้ากับโหนดสุดท้ายของลิสต์ของลิงค์ลิสต์เท่านั้นขั้นตอนเป็นดังนี้โดยมีHEADชี้ต้นลิสต์LAST 5 ^ HEADเมื่อเพิ่มข้อมูล6เข้าไปในลิสต์LAST 5 6 ^ HEADเมื่อเพิ่มข้อมูล7เข้าไปในลิสต์LAST 5 7 ^ 6^ HEAD

คำสั่งแรกของ BEGIN {Main} เนื้อที่หน่วยความจำในสแตกจะถูกใช้สำหรับตัวแปร P, Q, R

2. เมื่อเรียกใช้โพรซีเจอร์ A ณ คำสั่งแรกของ BEGIN {A}

3. เมื่อเรียกใช้โพรซีเจอร์ B ณ คำสั่งแรกของ BEGIN {B}

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

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

6. หลังจากเสร็จสิ้นการประมวลผลของโพรซีเจอร์ B (ตัวแปร X, Y จะถูก Pop ออกจาก สแตก ) ข้อสังเกต ถ้าเราเรียกใช้ตัวแปรแบบไดนามิกและเราไม่ได้ทำการ dispose เมื่อไม่ต้องการใช้แล้ว (เช่นเราออกจากโพรซีเจอร์ B แล้ว ) เนื้อที่ใน heap ก็จะเสียไปไม่สามารถนำมาใช้ได้อีก

7. หลังจากเสร็จสิ้นการประมวลผลของโพรซีเจอร์ A (ตัวแปร S จะถูก pop ออกจากสแตก)

8. หลังจากเสร็จสิ้นการประมวลผลของโปรแกรม Main (ตัวแปร P, Q, R จะถูก pop ออกจากสแตก)

ฟังชันเพื่อคำนวณค่าแฟกตอเรียล (Factorial) ดังนี้

FUNCTION Factorial (N : integer) : integer;

BEGIN IF N = 0 THEN Factorial := 1 ELSE Factorial := N * Factorial(N - 1) END; BEGIN {Main} P := Factorial (3); END;

การตรวจสอบอักขระสมดุล (Balancing Symbol) ผู้ที่มีประสบการณ์ในการเขียนโปรแกรมมาแล้ว จะพบว่าสิ่งที่เรามักจะหลงลืมเมื่อเขียนโปรแกรม และทำให้เกิดข้อผิดพลาดอยู่บ่อย ๆ คือ การหลงลืมอักขระสมดุล เช่น { คู่กับ }, [ คู่กับ ], ( คู่กับ ) เป็นต้น ซึ่งในการตรวจสอบอักขระสมดุลนั้น คอมไพเลอร์นำชนิดข้อมูลแบบสแตกมาประยุกต์ใช้ได้ โดยมีวิธีการดังนี้ ให้อ่านอักขระทีละตัว ถ้า อักขระเป็นอักขระเปิด เช่น {, [, (, เป็นต้น ให้ Push ลงสแตก ถ้า อักขระเป็นอักขระปิด เช่น }, ], ), เป็นต้น ให้ตรวจสอบว่าอักขระบน Top ของสแตกเป็นอักขระเปิดที่คู่กันหรือไม่ ถ้าใช่ ให้ Pop อักขระนั้นออกจากสแตก แต่ถ้าไม่ใช่ แสดงผล error เมื่ออ่านอักขระหมดแล้ว แต่สแตกไม่เป็นสแตกว่างให้แสดงผล error

การคำนวณค่าของนิพจน์เลขคณิต

(Arithmetic Expression ) โดยทั่วๆ ไปทางคณิตศาสตร์ เรามักนิยมเขียนนิพจน์เลขคณิตในลักษณะที่เรียกว่า สัญกรณ์เติมกลาง (infix notation) คือตัวดำเนินการ (operator) จะอยู่ตรงกลางของตัวถูกดำเนินการ (operand) ดังรูป operand operator operand ตัวดำเนินการ ก็คือ เครื่องหมายทางคณิตศาสตร์ สำหรับการคำนวณต่างๆ เรียงตามลำดับการดำเนินการก่อน-หลัง (precedence) ได้แก่ ยกกำลัง ^ คูณ หาร * , / บวก ลบ + , - ถ้าเครื่องหมายมีลำดับการดำเนินการเดียวกัน จะเลือกดำเนินงานของเครื่องหมายจากซ้ายไปขวา และถ้ามีวงเล็บจะดำเนินงานสิ่งที่อยู่ในวงเล็บก่อน ในการคำนวณนิพจน์เลขคณิตด้วยคอมพิวเตอร์ คอมพิวเตอร์จะทำการแปลงนิพจน์ที่เขียนแบบสัญกรณ์เติมกลาง ให้เป็นแบบสัญกรณ์เติมหลัง (postfix notation) ก่อน คือ จะอยู่ในรูปแบบที่ตัวดำเนินการ (operator) อยู่หลัง เช่น A + B - - - - > AB+ A - B - - - - > AB- A * B - - - - > AB* A / B - - - - > AB/ A ^ B - - - - > AB^ ชนิดข้อมูลแบบสแตกได้นำมาใช้ในการเปลี่ยนนิพจน์ในรูปแบบของสัญกรณ์เติมกลาง ให้เป็นสัญกรณ์เติมหลัง และนำมาใช้ในการหาค่าของนิพจน์นั้นๆ ด้วย ดังรายละเอียดในวิธีการ (algorithm) ดังต่อไปนี้ วิธีการเปลี่ยนนิพจน์แบบเติมกลางให้เป็นแบบเติมหลัง อ่านค่าตัวอักขระของนิพจน์ ซึ่งอักขระนี้จะเป็นได้ดังกรณีต่อไปนี้ เป็นตัวถูกดำเนินการ (operand), เป็นวงเล็บเปิด ”(“, เป็นวงเล็บปิด”)”, เป็นตัวดำเนินการ (operator) IF ตัวอักขระเป็น operand THEN ให้แสดงผลลัพธ์ตัวอักขระนั้น ELSE ตัวอักขระอาจจะเป็นวงเล็บหรือ operator IF สแตกว่าง THEN Push ตัวอักขระลงบนสแตก ELSE สแตกไม่ว่าง IF ตัวอักขระเป็น “(“ THEN Push ตัวอักขระลงบนสแตก ELSE ตัวอักขระเป็น “)” หรือ operator IF ตัวอักขระ เป็น “)” THEN PoP สิ่งที่อยู่บนสแตกจนกระทั่งพบ “(“ และ pop ออกมาด้วย ELSE ตัวอักขระเป็น operator (สิ่งที่อยู่บนสแตก “(“ มี priority ต่ำสุด) IF priority (ตัวอักขระ) > priority (สิ่งที่อยู่บนสแตก) THEN Push ตัวอักขระลงบนสแตก ELSE Pop สิ่งที่อยู่บนสแตกออกจนกระทั่ง Priority (ตัวอักขระ) > priority (สิ่งที่อยู่บนสแตก) Push ตัวอักขระลงบนสแตก กลับไปที่ 1 และทำจนกระทั่งหมดข้อมูล Pop สิ่งที่อยู่ในสแตกออกมา

โครงสร้างอาร์เรย์

เป็นแบบหนึ่งของโครงสร้างที่เรียกว่า linear listลักษณะของอาร์เรย์ คือตารางที่เป็นช่อง ๆ แต่ละช่องต้องเก็บข้อมูลแบบเดียวกัน เป็นตัวอักษรล้วนหรือเป็นตัวเลขล้วน ขนาดของแต่ละช่องต้องเท่ากันหมด อาร์เรย์เป็นโครงสร้างที่เกือบกล่าวได้ว่าเป็นที่คุ้นเคยมากที่สุดและเข้าใจง่ายที่สุด ทั้งนี้เนื่องจากโครงสร้างของอาร์เรย์ตรงกับความเป็นจริงตามธรรมชาติของข่าวสารข้อมูลหลายประการ เช่น บัญชีการเงิน คะแนนนักเรียนในชั้น บัญชีพนักงานของบริษัท ข้อมูลที่แบ่งเป็นพวกหรือหมวดหมู่ ฯลฯ นอกจากนี้โปรแกรมที่เขียนคำนวณงานเมตริกซ์ (matrix) หรือพีชคณิตเชิงเส้น ก็ต้องใช้อาร์เรย์เป็นที่เก็บตัวเลข นอกจากนี้อาร์เรย์ยังเป็นโครงสร้างพื้นฐานของโรงสร้างที่สำคัญอื่น ๆ อีก เช่น สแตก,คิว,ต้นไม้ เป็นต้น ลักษณะของอาร์เรย์ การสร้างอาร์เรย์ขึ้นใช้นั้น เราต้องคำนึงถึงสิ่งต่อไปนี้ - ชื่อของอาร์เรย์ - ขนาดของอาร์เรย์แต่ละช่อง และมิติของอาร์เรย์ - ค่าสูงสุด (upper bound)และค่าต่ำสุด (lower bound)ในแต่ละมิติ สำหรับอาร์เรย์ 1 มิตินั้น จะมีลักษณะทั่วไปดังนี้ โครงสร้างของการแทนสแตกด้วยอาร์เรย์ การแทนสแตกด้วยโครงสร้างอาร์เรย์นั้น เนื่องจากอาร์เรย์เป็นโครงสร้างที่ต้องมีการกำหนดจองพื้นที่แน่นอน (static) จึงจำเป็นต้องมีการกำหนดขนาดพื้นที่จัดเก็บข้อมูลสูงสุดให้เหมาะสมเมื่อมีการ นำเอาข้อมูลเข้ามาก็จะนำเข้ามาจัดไว้ในอาร์เรย์แรกสุดจากนั้นจึงเรียงลำดับกัน ไปตามพื้นที่ที่กำหนด

ส่วนประกอบของสแตก

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

1. ตัวชี้สแตก( Stack Pointer ) หรือ SP