DTS06-04/08/2009

สรุปบทเรียน

สแตก(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 ) เป็นข้อมูลที่จะเก็บลงไปในสแตก ซึ่งจะต้องเป็นข้อมูลชนิดเดียวกัน เช่น ข้อมูลชนิดจำนวนเต็ม เป็นต้น นอกจากนี้ยังต้องมีตัวกำหนดค่าสูงสุดของสแตก ( Max Stack ) ซึ่งจะเป็นตัวบอกว่าสแตกนี้สามารถเก็บ จำนวนข้อมูลได้มากที่สุดเท่าไร เปรียบเทียบส่วนประกอบของสแตกได้กับการให้ สแตกเป็นกระป๋องเก็บลูกเทนนิส ส่วน Stack Elements หรือสมาชิกของสแตก คือ ลูกเทนนิส ส่วนตัวชี้สแตกเป็นตัวบอกว่าขณะนี้มีลูกเทนนิสอยู่ในกระป๋องกี่ลูก ส่วน Max Stack เป็นตัวบอกว่า กระป๋องนี้เก็บลูกเทนนิสได้มากที่สุดเท่าไร

การจัดการ กับสแตก
ในการทำงานของสแตก ประกอบด้วย 2 กระบวนการ คือ การเพิ่มข้อมูลลงบนสแตก (pushing stack) และ การดึงข้อมูลออกจากสแตก (poping stack)

1. การเพิ่มข้อมูลในสแตก (pushing stack) เป็นการนำข้อมูลเข้าสู่สแตก ซึ่งการกระทำเช่นนี้ เราเรียกว่า push ซึ่งโดยปกติก่อนที่จะนำข้อมูลเก็บลงในสแตกจะต้องมีการตรวจสอบพื้นที่ในสแตกก่อน ว่ามีที่เหลือว่างให้เก็บข้อมูลได้อีกหรือไม่

ในการเพิ่มข้อมูลในสแตก (pushing) สามารถทำได้โดยให้ทับบนข้อมูลสุดท้ายในสแตก และจะสามารถเพิ่มเข้าได้เรื่อย ๆ จนกว่าสแตกจะเต็ม ความหมายของคำว่า สแตกเต็ม คือท๊อปของ สแตกชี้ที่บนสุดของสแตก เช่น ถ้า สแตกนั้นจองเนื้อที่ไว้ N เนื้อที่ หมายถึงสามารถบรรจุสมาชิกในสแตกได้ N ตัว หากเป็นสแตกว่าง ค่าของท๊อปจะเป็นศูนย์ แต่หากสแตกเต็ม ค่าท๊อปจะเป็น N นั้นแสดงว่าเมื่อท๊อปชี้ที่ N หรือค่าของท๊อป เท่ากับ N ก็จะไม่สามารถ push ข้อมูลลง สแตกได้


นิยาม Push (S,x)

ถ้าให้ S เป็นสแตก และ x เป็นข้อมูลที่ต้องการใส่ในสแตก หรือดึงออกสแตก กระบวนการ push (S, x ) หมายถึง การ push ข้อมูล x ลงสแตก โดยการ push จะเริ่มจากสแตกว่างโดยให้ค่า ท๊อปมีค่าเป็นศูนย์ เมื่อมีการ push ข้อมูลเข้าในสแตก ค่า ของท๊อปจะเปลี่ยนเพิ่มขึ้นทีละหนึ่งทุกครั้งที่ทำการ 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) หากตัวชี้สแตกมีค่าเท่ากับค่าสูงสุดของสแตกแล้ว แสดงว่าไม่มีที่ว่างให้ข้อเก็บข้อมูล อีก


2. สแตกว่าง (Empty Stack)

นิยาม empty(S) ถ้า S เป็นสแตก ขบวนการ empty(S) จะส่งผลเป็นจริง (true) เมื่อสแตกว่าง และส่งผลเป็นเท็จ (false) เมื่อสแตกไม่ว่างหรือสแตกเต็ม

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

DTS05-28/07/2009

เรื่อง Linked List
Linked List
เป็นการจัดเก็บชุดข้อมูลมีพอยเตอร์เป็นตัวเชื่อมโยงต่อเนื่องกันไป
ตามลำดับซึ่งในลิงค์ลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่า
โหนด (Node) ในหนึ่งโหนดจะประกอบด้วย1.ส่วนของข้อมูลที่ต้อง
การจัดเก็บ เรียกว่าส่วน (Data)2.ส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนด
ถัดไป (Link) หรือชี้ไปยังโหนดอื่นๆที่อยู่ในลิสต์

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

โครงสร้างข้อมูลแบบลิงค์ลิสต์ประกอบด้วย 2 ส่วน
1.Head Structure แบ่งเป็น 3ส่วน
-count เป็นการนับจำนวนข้อมูลที่มีอยู่ในลิสต์นั้น
-pos พอยเตอร์ที่ชี้ไปยังโหนดที่เข้าถึง
-head พอยเตอร์ที่ชี้ไปยังโหนดแรกของลิสต์
2.Data Node Structure จะประกอบด้วย ข้อมูลและพอยเตอร์
ที่ชี้ไปโหนดถัดไป

การเพิ่มข้อมูลลงไปในลิงค์ลิสต์นั้น จากที่ Head Structure
ในส่วนของ count จะมีค่าเป็น 0 นั้นหมายถึงในลิสต์นั้นยังไม่มี
ข้อมูลใดเลย ส่วน head จะมีเครื่องหมายกากบาท นั้นหมายถึง
ในลิสต์นั้นไม่มีการเชื่อมโยงไปยังข้อมูลแรก แต่ถ้าต้องการเพิ่ม
ข้อมูลลงไปในลิสต์ Data Node ในส่วนของข้อมูล (Data)จะมี
ค่าเก็บอยู่ แล้ว count ก็จะเปลี่ยนค่าจาก 0 เป็น 1 คือ การบ่งบอก
ถึงจำนวนข้อมูลที่มีอยู่ในลิสต์นั้น แล้ว head ก็จะชี้ไปยัง
ข้อมูล (Data) ตัวแรกของลิสต์ ส่วนพอยเตอร์ที่ชี้ไปโหนดถัดไป
จะเป็นเครื่องหมายกากบาทแทน

การลบข้อมูลในลิงค์ลิสต์ ถ้าต้องการลบข้อมูลตัวใดในลิสต์
สามารถลบได้เลย แต่ต้องเปลี่ยน head เพื่อชี้ไปยังข้อมูลตัวแรก
ของลิสต์กรณีที่ลบข้อมูลตัวแรกออก แล้ว link คือ เมื่อลบข้อมูล
ตัวใดออกควรชี้ link ถัดไปให้ถูกต้องด้วย