สแตก(stack)
สแตกเป็นโครงสร้างข้อมูลแบบลิเนียร์ลิสต์(linear list) ที่สามารถนำข้อมูลเข้าหรือออกได้ทางเดียวคือส่วนบนของสแตกหรือ หรือเรียกว่า ท๊อปของสแตก (Top Of Stack) ซึ่งคุณสมบัติดังกล่าวเรียกว่า ไลโฟลิสต์ (LIFO list: Last-In-First-Out list) หรือ พูชดาวน์ลิสต์ (Pushdown List) คือสมาชิกที่เข้าลิสต์ที่หลังสุดจะได้ออกจากลิสต์ก่อน หรือ เข้าหลังออกก่อน การเพิ่มข้อมูลเข้าสแตกจะเรียกว่าพูชชิ่ง (pushing) การนำข้อมูลจากสแตกเรียกว่า ป๊อปปิ้ง (poping) การเพิ่มหรือลบข้อมูลในสแตกทำที่ท๊อปของสแตก ท๊อปของสแตกนี้เองเป็นตัวชี้สมาชิกตัวท้ายสุดของสแตก
ส่วนประกอบของสแตก
การนำสแตกไปใช้งานนั้นไม่ว่าจะเป็นโครงสร้างสแตกแบบแถวลำดับ(array)หรือ แบบลิงค์ลิสต์ (link list) เราจะมีตัวแปรตัวหนึ่งที่ใช้เป็นตัวชี้สแตก(stack pointer ) เพื่อเป็นตัวชี้ข้อมูลที่อยู่บนสุดของสแตก ซึ่งจะทำให้สามารถจัดการข้อมูล ที่จะเก็บในสแตกได้ง่าย ดังนั้นโครงสร้างข้อมูลแบบสแตกจะแบ่งออกเป็น 2 ส่วนที่สำคัญ คือตัวชี้สแตก ( Stack Pointer ) ซึ่งมีหน้าที่ชี้ไปยังข้อมูลที่อยู่บนสุดของ สแตก ( Top stack )สมาชิกของสแตก ( Stack Element ) เป็นข้อมูลที่จะเก็บลงไปในสแตก ซึ่งจะต้องเป็นข้อมูลชนิดเดียวกัน เช่น ข้อมูลชนิดจำนวนเต็ม เป็นต้น
การจัดการ กับสแตก
ในการทำงานของสแตก ประกอบด้วย 2 กระบวนการ คือ การเพิ่มข้อมูลลงบนสแตก (pushing stack) และ การดึงข้อมูลออกจากสแตก (poping stack)
1. การเพิ่มข้อมูลในสแตก (pushing stack) เป็นการนำข้อมูลเข้าสู่สแตก ซึ่งการกระทำเช่นนี้ เราเรียกว่า push ซึ่งโดยปกติก่อนที่จะนำข้อมูลเก็บลงในสแตกจะต้องมีการตรวจสอบพื้นที่ในสแตกก่อน ว่ามีที่เหลือว่างให้เก็บข้อมูลได้อีกหรือไม่
2. การดึงข้อมูลจากสแตก (Popping Stack) หมายถึงการเอาข้อมูลที่อยู่บนสุดในสแตก หรือที่ชี้ด้วย ท๊อปออกจากสแตก เรียกว่าการ pop ในการpop นั้นเราจะสามารถ pop ข้อมูลจากสแตกได้เรื่อย ๆ จนกว่า ข้อมูลจะหมดสแตก หรือ เป็นสแตกว่าง โดยก่อนที่จะนำข้อมูลออกจากสแตก จะต้องมีการตรวจสอบว่าใน สแตกมีข้อมูลเก็บ อยู่หรือไม่
นิยาม pop(S)
ถ้าให้ S เป็นสแตก การ pop(S) คือการนำข้อมูลบนสุดในสแตกออกจากสแตกและให้ค่าเป็นข้อมูลที่นำออกจากสแตก ดังนั้น คำสั่ง x = pop(S) ก็คือการนำข้อมูลที่ท๊อปของสแตกออกมา และใส่ค่าไว้ที่ x หรือการเซตค่า x ให้เท่ากับข้อมูลที่ดึงจากสแตก
ปัญหาที่เกิดขึ้นกับสแตก
คือขอผิดพลาดที่เกิดขึ้นซึ่งมีผลมาจากการจัดการสแตกมีดังนี้
สแตกเต็ม (Full Stack)
สแตกว่าง (Empty Stack)
สแตกเต็ม (Full Stack)
การ push สแตกทุกครั้งจะมีการตรวจสอบที่ว่างในสแตกว่ามีที่ว่างเหลือหรือไม่ ถ้าไม่มีที่ว่างเหลืออยู่ เราก็จะไม่สามารถทำการ push สแตกได้ ในกรณีเช่นนี้เราเรียกว่าเกิดสถานะล้นเต็ม (Stack Overflow) โดย การตรวจสอบว่าสแตกเต็มหรือไม่ เราจะใช้ตัวชี้สแตก (Stack pointer) มาเปรียบเทียบกับค่าสูงสุดของ สแตก (Max stack) หากตัวชี้สแตกมีค่าเท่ากับค่าสูงสุดของสแตกแล้ว แสดงว่าไม่มีที่ว่างให้ข้อเก็บข้อมูล อีก
สแตกว่าง (Empty Stack)
นิยาม empty(S) ถ้า S เป็นสแตก ขบวนการ empty(S) จะส่งผลเป็นจริง (true) เมื่อสแตกว่าง และส่งผลเป็นเท็จ (false) เมื่อสแตกไม่ว่างหรือสแตกเต็ม
การ pop สแตกทุกครั้งจะมีการตรวจสอบข้อมูลในสแตกว่ามีข้อมูลในสแตกหรือไม่ ถ้าไม่มีข้อมูลในสแตก เหลืออยู่ เราก็ไม่สามารถทำการ pop สแตกได้ ในกรณีเช่นนี้เรียกว่าเกิดสถานะ สแตกจม (Stack Underflow) โดยการตรวจสอบว่าสแตกว่างหรือไม่ เราจะตรวจสอบตัวชี้สแตกว่าเท่ากับ 0 หรือ null หรือไม่ ถ้าเท่ากับ 0 แสดงว่า สแตกว่าง จึงไม่สามารถดึงข้อมูลออกจากสแตกได้
สมัครสมาชิก:
ส่งความคิดเห็น (Atom)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น