Stack
โครงสร้างของ Stack
สแตกเป็นโครงสร้างข้อมูลแบบลิเนียร์ลิสต์(linear list) ที่สามารถนำข้อมูลเข้าหรือออกได้ทางเดียวคือส่วนบนของสแตกหรือ หรือเรียกว่า ท๊อปของสแตก (Top Of Stack) ซึ่งคุณสมบัติดังกล่าวเรียกว่า ไลโฟลิสต์ (LIFO list: Last-In-First-Out list) หรือ พูชดาวน์ลิสต์ (Pushdown List) คือสมาชิกที่เข้าลิสต์ที่หลังสุดจะได้ออกจากลิสต์ก่อน หรือ เข้าหลังออกก่อน การเพิ่มข้อมูลเข้าสแตกจะเรียกว่าพูชชิ่ง (pushing) การนำข้อมูลจากสแตกเรียกว่า ป๊อปปิ้ง (poping) การเพิ่มหรือลบข้อมูลในสแตกทำที่ท๊อปของสแตก ท๊อปของสแตกนี้เองเป็นตัวชี้สมาชิกตัวท้ายสุดของสแตก การทำงานของสแตกจะประกอบด้วยกระบวนการ 3 กระบวนการที่สำคัญคือ
Push คือ การนำข้อมูลใส่ลงไปในสแตก โดยการเพิ่มข้อมูลลงในสแตก จะต้องทำการตรวจสอบว่าสแตก เต็มหรือไม่ ถ้าไม่เต็มก็สามารถเพิ่มข้อมูลลงไปในสแตกได้ แล้วปรับตัวชี้ตำแหน่งให้ไปชี้ที่ตำแหน่งข้อมูลใหม่ ถ้าสแตกเต็ม (Stack Overflow) ก็จะไม่สามารถเพิ่มข้อมูลเข้าไปในสแตกได้อีก
Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตก โดยการนำข้อมูลออกจากสแตก ถ้าสแตกมีสมาชิก เพียง 1ตัว แล้วนำสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง (Stack Empty)คือ ไม่มีสมาชิก อยู่ในสแตกเลย แต่ถ้าไม่มีสมาชิกในสแตก แล้วทำการ pop สแตก จะทำให้ เกิดความผิดพลาดที่เรียกว่า Stack Underflowเพราะฉะนั้นก่อนนำข้อมูลออกจากสแตกจะต้องตรวจสอบ ก่อนว่าสแตกว่างหรือเปล่า จึงจะนำข้อมูลออกจากสแตกได้และ ปรับตัวชี้ตำแหน่งให้ไปชี้ตำแหน่งของข้อมูลที่ต่อจากข้อมูลที่ถูกนำ ออกไป
Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตกการแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์ ประกอบไปด้วย2 ส่วน คือ1. Head Node จะประกอบไปด้วย 2ส่วนคือ top pointer และจำนวนสมาชิกในสแตก
2. Data Node จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ ที่ชี้ไปยังข้อมูลตัวถัดไป2. การแทนที่ข้อมูลของสแตกแบบอะเรย์การดำเนินการเกี่ยวกับสแตก
ส่วนประกอบของสแตก
การนำสแตกไปใช้งานนั้นไม่ว่าจะเป็นโครงสร้างสแตกแบบแถวลำดับ(array)หรือ แบบลิงค์ลิสต์ (link list) เราจะมีตัวแปรตัวหนึ่งที่ใช้เป็นตัวชี้สแตก(stack pointer ) เพื่อเป็นตัวชี้ข้อมูลที่อยู่บนสุดของสแตก ซึ่งจะทำให้สามารถจัดการข้อมูล ที่จะเก็บในสแตกได้ง่าย ดังนั้นโครงสร้างข้อมูลแบบสแตกจะแบ่งออกเป็น 2 ส่วนที่สำคัญ คือ
1. ตัวชี้สแตก ( Stack Pointer ) ซึ่งมีหน้าที่ชี้ไปยังข้อมูลที่อยู่บนสุดของ สแตก ( Top stack )
2. สมาชิกของสแตก ( Stack Element ) เป็นข้อมูลที่จะเก็บลงไปในสแตก ซึ่งจะต้องเป็นข้อมูลชนิดเดียวกัน เช่น ข้อมูลชนิดจำนวนเต็ม เป็นต้น
ประโยชน์ของ Stack
ประโยชน์ของสแตก ใช้ในการจดจำการกระโดดไปมาระหว่างโปรแกรมย่อย ใช้ในการเขียนโปรแกรมแบบรีเคอร์ซีฟ (Recursive) ใช้ในการจดจำเส้นทางในการเดินทางของโครงสร้างข่ายงาน (Network) หรือ โครงสร้างของต้นไม้ (Tree) ลักษณะสำคัญของสแตก โครงสร้างข้อมูลเป็นแบบเชิงเส้น (Linear structure) มีโครงสร้างที่ไม่ตายตัว (dynamic structure) นำข้อมูลเข้าและดึงข้อมูลออกได้ (push and pop) นำข้อมูลเข้าและดึงข้อมูลออกแบบลำดับ (lifo mechanism) มีการจัดการนำเข้าและดึงข้อมูลในตำแหน่งบนสุด (push and pop at top)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น