โครงสร้างข้อมูลกราฟ

กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนี่งของกราฟโดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูป และการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด

กราฟเป็นโครงสร้างข้อมูลประเภทหนึ่งที่แสดงความสัมพันธ์ระหว่าง vertex และ edge กราฟจะประกอบด้วยกลุ่มของ vertex ซึ่งแสดงในกราฟด้วยสัญลักษณ์รูปวงกลม และ กลุ่มของ edge (เส้นเชื่อมระหว่าง vertex) ใช้แสดงถึงความสัมพันธ์ระหว่าง vertex หากมี vertex ตั้งแต่ 2 vertex ขึ้นไปมีความสัมพันธ์กัน ใช้สัญลักษณ์เส้นตรงซึ่งอาจมีหัวลูกศร หรือไม่มีก็ได้

กราฟสามารถเขียนแทนด้วยสัญลักษณ์ ดังนี้

G = ( V , E )

G คือ กราฟ

V คือ กลุ่มของ vertex

E คือ กลุ่มของ edge

ศัพท์ที่เกี่ยวข้อง

1.เวอร์เทก (Vertex) หมายถึง โหนด

2.เอดจ (Edge) หมายถึง เส้นเชื่อมของโหนด

3.ดีกรี (Degree) หมายถึง จำนวนเส้นเข้าและออก ของโหนดแต่ละโหนด

4.แอดจาเซนท์โหนด (Adjacent Node) หมายถึง โหนดที่มีการเชื่อมโยงกัน

ตัวอย่างของกราฟในชีวิตประจำวัน เช่น กราฟของการเดินทางระหว่างเมือง ซึ่ง vertex คือ กลุ่มของเมืองต่างๆ และ edge คือ เส้นทางเดินระหว่างเมือง หรือ ในเครือข่ายคอมพิวเตอร์ (Computer Network) vertex ก็คือ กลุ่มของเครื่องคอมพิวเตอร์ หรือโหนดต่างๆ และ edge ก็คือ เส้นทางการติดต่อสื่อสารระหว่างโหนดต่างๆ เป็นต้น

ประเภทของกราฟ

แบ่งเป็น 3 ประเภทโดยแบ่งตามประเภทของ edge ได้ดังนี้

1. Direct Graph (กราฟแสดงทิศทาง) เป็นกราฟที่แสดงเส้นเชื่อมระหว่าง vertex โดแสดงทิศทางของการเชื่อมต่อด้วย

2. Undirected Graph กราฟที่แสดงเส้นเชื่อมต่อระหว่าง vertex แต่ไม่แสดงทิศทางของการเชื่อมต่อ

3. Cyclic Graph กราฟที่มีเส้นเชื่อมต่อระหว่าง vertex ที่ทำให้ vertex มีลักษณะเป็นวงจรปิด (Cycle) เส้นเชื่อมต่อระหว่าง vertex อาจจะแสดงทิศทางหรือไม่แสดงทิศทางการเชื่อมต่อก็ได้

เส้นทาง (Path)

เส้นทางคือการเดินทางจาก vertex หนึ่งไปยังอีก vertex หนึ่งที่ต้องการ โดยผ่าน edge ที่เชื่อมระหว่าง vertex

ความยาวของเส้นทาง (The length of path) คือ จำนวนของ edge ในเส้นทางเดินนั้น ว่ามีจำนวนเท่าไหร่ ในการเดินทางจาก vertex หนึ่ง ไปยังอีก vertex หนึ่ง ถ้าหากเส้นทางประกอบด้วย vertex จำนวน N ความยาวของเส้นทางจะเท่ากับ N-1

ตัวอย่างเส้นทางการเดินทาง จาก vertex A ไป vertex D จะมีเส้นทางดังนี้

ตัวอย่างเส้นทางการเดินทาง จาก vertex A ไป vertex D จะมีเส้นทางดังนี้

การแทนที่กราฟด้วยเมตริกซ์

โครงสร้างข้อมูลประเภทกราฟสามารถใช้เมตริกซ์มาแสดงแทนได้ โดยกราฟที่ประกอบด้วย vertex จำนวน N vertex สามารถแทนที่ด้วยเมตริกซ์ขนาด N x N โดยค่าในเมตริกซ์จะประกอบด้วย ค่า 0 และ 1

ค่า 0 จะใช้แทนไม่มี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง และ

ค่า 1 จะใช้แทนมี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง

ตัวอย่างจากรูปกราฟแบบ Direct Graph

สามารถแทนที่กราฟด้วยเมตริกซ์ดังนี้

ตัวอย่าง หากเป็นกราฟแบบ Undirected Graph

การคำนวณเส้นทางระหว่าง vertex โดยใช้ Adjacency Matrix

จากการแทนที่กราฟด้วยเมตริกซ์ เราสามารถนำเมตริกซ์ที่ได้มาคำนวณหาจำนวนเส้นทางระหว่าง vertex ต้นทางและปลายทางที่มีจำนวน edge ต่างๆ ได้

ตัวอย่างจากรูป สามารถคำนวณจำนวนเส้นทางระหว่าง vertex ที่มี edge จำนวน 3 เส้นได้ดังนี้

ตัวอย่างจากรูป สามารถคำนวณจำนวนเส้นทางระหว่าง vertex ที่มี edge จำนวน 4 เส้นได้ดังนี้

โครงสร้างข้อมูลกราฟ

กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนี่งของกราฟโดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูป และการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด

กราฟเป็นโครงสร้างข้อมูลประเภทหนึ่งที่แสดงความสัมพันธ์ระหว่าง vertex และ edge กราฟจะประกอบด้วยกลุ่มของ vertex ซึ่งแสดงในกราฟด้วยสัญลักษณ์รูปวงกลม และ กลุ่มของ edge (เส้นเชื่อมระหว่าง vertex) ใช้แสดงถึงความสัมพันธ์ระหว่าง vertex หากมี vertex ตั้งแต่ 2 vertex ขึ้นไปมีความสัมพันธ์กัน ใช้สัญลักษณ์เส้นตรงซึ่งอาจมีหัวลูกศร หรือไม่มีก็ได้

กราฟสามารถเขียนแทนด้วยสัญลักษณ์ ดังนี้

G = ( V , E )

G คือ กราฟ

V คือ กลุ่มของ vertex

E คือ กลุ่มของ edge

ศัพท์ที่เกี่ยวข้อง

1.เวอร์เทก (Vertex) หมายถึง โหนด

2.เอดจ (Edge) หมายถึง เส้นเชื่อมของโหนด

3.ดีกรี (Degree) หมายถึง จำนวนเส้นเข้าและออก ของโหนดแต่ละโหนด

4.แอดจาเซนท์โหนด (Adjacent Node) หมายถึง โหนดที่มีการเชื่อมโยงกัน

ตัวอย่างของกราฟในชีวิตประจำวัน เช่น กราฟของการเดินทางระหว่างเมือง ซึ่ง vertex คือ กลุ่มของเมืองต่างๆ และ edge คือ เส้นทางเดินระหว่างเมือง หรือ ในเครือข่ายคอมพิวเตอร์ (Computer Network) vertex ก็คือ กลุ่มของเครื่องคอมพิวเตอร์ หรือโหนดต่างๆ และ edge ก็คือ เส้นทางการติดต่อสื่อสารระหว่างโหนดต่างๆ เป็นต้น

ประเภทของกราฟ

แบ่งเป็น 3 ประเภทโดยแบ่งตามประเภทของ edge ได้ดังนี้

1. Direct Graph (กราฟแสดงทิศทาง) เป็นกราฟที่แสดงเส้นเชื่อมระหว่าง vertex โดแสดงทิศทางของการเชื่อมต่อด้วย

2. Undirected Graph กราฟที่แสดงเส้นเชื่อมต่อระหว่าง vertex แต่ไม่แสดงทิศทางของการเชื่อมต่อ

3. Cyclic Graph กราฟที่มีเส้นเชื่อมต่อระหว่าง vertex ที่ทำให้ vertex มีลักษณะเป็นวงจรปิด (Cycle) เส้นเชื่อมต่อระหว่าง vertex อาจจะแสดงทิศทางหรือไม่แสดงทิศทางการเชื่อมต่อก็ได้

เส้นทาง (Path)

เส้นทางคือการเดินทางจาก vertex หนึ่งไปยังอีก vertex หนึ่งที่ต้องการ โดยผ่าน edge ที่เชื่อมระหว่าง vertex

ความยาวของเส้นทาง (The length of path) คือ จำนวนของ edge ในเส้นทางเดินนั้น ว่ามีจำนวนเท่าไหร่ ในการเดินทางจาก vertex หนึ่ง ไปยังอีก vertex หนึ่ง ถ้าหากเส้นทางประกอบด้วย vertex จำนวน N ความยาวของเส้นทางจะเท่ากับ N-1

ตัวอย่างเส้นทางการเดินทาง จาก vertex A ไป vertex D จะมีเส้นทางดังนี้

ตัวอย่างเส้นทางการเดินทาง จาก vertex A ไป vertex D จะมีเส้นทางดังนี้

การแทนที่กราฟด้วยเมตริกซ์

โครงสร้างข้อมูลประเภทกราฟสามารถใช้เมตริกซ์มาแสดงแทนได้ โดยกราฟที่ประกอบด้วย vertex จำนวน N vertex สามารถแทนที่ด้วยเมตริกซ์ขนาด N x N โดยค่าในเมตริกซ์จะประกอบด้วย ค่า 0 และ 1

ค่า 0 จะใช้แทนไม่มี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง และ

ค่า 1 จะใช้แทนมี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง

ตัวอย่างจากรูปกราฟแบบ Direct Graph

สามารถแทนที่กราฟด้วยเมตริกซ์ดังนี้

ตัวอย่าง หากเป็นกราฟแบบ Undirected Graph

การคำนวณเส้นทางระหว่าง vertex โดยใช้ Adjacency Matrix

จากการแทนที่กราฟด้วยเมตริกซ์ เราสามารถนำเมตริกซ์ที่ได้มาคำนวณหาจำนวนเส้นทางระหว่าง vertex ต้นทางและปลายทางที่มีจำนวน edge ต่างๆ ได้

ตัวอย่างจากรูป สามารถคำนวณจำนวนเส้นทางระหว่าง vertex ที่มี edge จำนวน 3 เส้นได้ดังนี้

ตัวอย่างจากรูป สามารถคำนวณจำนวนเส้นทางระหว่าง vertex ที่มี edge จำนวน 4 เส้นได้ดังนี้

ทรี (Tree)
หรือโครงสร้างข้อมูลแบบต้นไม้ ประกอบด้วยโหนด (node) ซึ่งเป็นส่วนที่เก็บข้อมูล ในทรีหนึ่งทรีจะประกอบไปด้วยรูทโหนด (root node) เพียงหนึ่งโหนด แล้วรูทโหนดสามารถแตกโหนดออกเป็นโหนดย่อยๆ ได้อีกหลายโหนดเรียกว่าโหนดลูก (Child node) เมื่อมีโหนดลูกแล้ว โหนดลูกก็ยังสามารถแสดงเป็นโหนดพ่อแม่ (Parent Node) โดยการแตกโหนดออกเป็นโหนดย่อยๆได้อีก


จุดเด่นของทรี
เป็นโครงสร้างที่เน้นข้อมูลที่เปรียบเทียบกันได้ (comparable) เช่นต้นไม้ค้นหา หรือมีลำดับความสำคัญเป็นขั้นตอน เช่นฮีป มักใช้ในการจัดการค้นหาอย่างรวดเร็วเป็น O (log n) หรือการจัดลำดับความสำคัญ เช่นการจัดนิพจน์ซึ่งเรียงลำดับการทำงานโดยต้นไม้นิพจน์

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

คิว (Queues)

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

ลักษณะของคิว จะมีปลายสองข้าง ซึ่งข้างหนึ่งจะเป็นช่องทางสำหรับข้อมูลเข้าที่เรียกว่า REAR และอีกข้างหนึ่งซึ่งจะเป็นช่องทางสำหรับข้อมูลออก เรียกว่า FRONT

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

การกระทำกับคิว
  • การเพิ่มข้อมูลเข้าไปในคิว
    การจะเพิ่มข้อมูลเข้าไปในคิว จะกระทำที่ตำแหน่ง REAR หรือท้ายคิว และก่อนที่จะเพิ่มข้อมูลจะต้องตรวจสอบก่อนว่าคิวเต็มหรือไม่ โดยการเปรียบเทียบค่า REAR ว่า เท่ากับค่า MAX QUEUE หรือไม่ หากว่าค่า REAR = MAX QUEUE แสดงว่าคิวเต็มไม่สามารถเพิ่มข้อมูลได้ แต่หากไม่เท่า แสดงว่าคิวยังมีที่ว่างสามารถเพิ่มข้อมูลได้ เมื่อเพิ่มข้อมูลเข้าไปแล้ว ค่า REAR ก็จะเป็นค่าตำแหน่งท้ายคิวใหม่

  • การนำข้อมูลออกจากคิว
    การ นำข้อมูลออกจากคิวจะกระทำที่ตำแหน่ง FRONT หรือส่วนที่เป็นหัวของคิว โดยก่อนที่จะนำข้อมูลออกจากคิวจะต้องมีการตรวจสอบก่อนว่ามีข้อมูลอยู่ในคิว หรือไม่ หากไม่มีข้อมูลในคิวหรือว่าคิวว่าง ก็จะไม่สามารถนำข้อมูลออกจากคิวได้

คิวแบบวงกลม (Circular Queue)
คิวแบบวงกลมจะมีลักษณะเหมือนคิวธรรมดา คือ มีตัวชี้ FRONT และ REAR ที่แสดงตำแหน่งหัวคิวและท้ายคิวตามลำดับ โดย FRONT และ REAR จะมีการเลื่อนลำดับทุกครั้งเมื่อมีการนำข้อมูลเข้าและออกจากคิว แต่จะแตกต่างจากคิวธรรมดาก็คือ คิวธรรมดาเมื่อ REAR ชี้ที่ตำแหน่งสุดท้ายของคิว จะทำให้เพิ่มข้อมูลเข้าในคิวอีกเมื่อไม่ได้ เนื่องจาก ค่า REAR=MAX QUEUE ซึ่งแสดงว่าคิวนั้นเต็ม ไม่สามารถเพิ่มข้อมูลเข้าไปได้อีก ทั้งๆ ที่ยังมีเนื้อที่ของคิวเหลืออยู่ก็ตาม ทำให้การใช้เนื้อที่ของคิวไม่มีประสิทธิภาพ

จากรูป แสดงคิวที่ค่า REAR ชี้ที่ตำแหน่งสุดท้ายของคิว ทำให้ไม่สามารถนำข้อมูลเข้าได้อีก

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

แสดงคิวแบบวงกลมที่ REAR สามารถวนกลับมาชี้ที่ตำแหน่งแรกสุดของคิว

คิวแบบวงกลมจากที่กล่าวมาสามารถเพิ่มข้อมูลได้อีก จนกว่าคิวจะเต็มซึ่งแสดงดังรูป

อัลกอริทึมการแปลงนิพจน์ Infix เป็น นิพจน์ Postfix (ต่อจาก สแตค )


 เราสามารถแปลงนิพจน์ Infix ให้เป็น Postfix ได้โดยอาศัยสแตคที่มีคุณสมบัติการเข้าหลังออกก่อนหรือ LIFO โดยมีอัลกอริทึมในการแปลงนิพจน์ ดังนี้

1. ถ้าข้อมูลเข้า (input) เป็นตัวถูกดำเนินการ (operand) ให้นำออกไปเป็นผลลัพธ์ (output)

2. ถ้าข้อมูลเข้าเป็นตัวดำเนินการ (operator) ให้ดำเนินการดังนี้
2.1 ถ้าสแตคว่าง ให้ push operator ลงในสแตค
2.2 ถ้าสแตคไม่ว่าง ให้เปรียบเทียบ operator ที่เข้ามากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตค
2.2.1 ถ้า operator ที่เข้ามามีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตคให้ push ลงสแตค
2.2.2 ถ้า operator ที่เข้ามามีความสำคัญน้อยกว่าหรือเท่ากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตค ให้ pop สแตคออกไปเป็นผลลัพธ์ แล้วทำการเปรียบเทียบ operator ที่เข้ามากับ operator ที่ตำแหน่ง TOP ต่อไป จะหยุดจนกว่า operator ที่เข้ามาจะมีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตค แล้วจึง push operator ที่เข้ามานั้นลงสแตค

3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิด ให้ push ลงสแตค

4. ถ้าข้อมูลเข้าเป็นวงเล็บปิด ให้ pop ข้อมูลออกจากสแตคไปเป็นผลลัพธ์จนกว่าจะถึงวงเล็บ เปิด จากนั้นทิ้งวงเล็บเปิดและปิดทิ้งไป

5. ถ้าข้อมูลเข้าหมด ให้ pop ข้อมูลออกจากสแตคไปเป็นผลลัพธ์จนกว่าสแตคจะว่าง


Operand
คือตัวแปรต่าง ๆ A,B,C,D,E เช่น A+B*C,(A*B)-C

ลำดับความสำคัญ Operator
  1. เครื่องหมายยกกำลัง ^
  2. เครื่องหมายคูณกับหาร *,/
  3. เครื่องหมายบวกกับลบ +,-
  4. เครื่องหมายวงเล็บ () กระทำก่อนเช่น A+(B*C)
  5. เครื่องหมายระดับเดียวกันไม่มีวงเล็บให้ทำจากซ้ายไปขวา เช่น A+B+C
เมื่อการประมวลนิพจน์ infix เป็นไปด้วยความยากที่การคำนวณไม่เป็นไปตามลำดับของเครื่องหมายโอเปอร์เรเตอร์ที่มีก่อนหลัง คอมไพเลอร์จึงแปลงนิพจน์ infix ให้เป็น postfix เสียก่อน

นิพจน์ Postfix ก็คือนิพจน์ที่มีโอเปอเรเตอร์อยู่หลังโอเปอร์แรนด์ทั้งสองของมัน เช่น

AB+ หมายถึง A+B

AB- หมายถึง A-B

AB* หมายถึง A*B


ตัวอย่างการแปลงนิพจน์ Infix เป็นนิพจน์ Postfix
นิพจน์ A + B * C

นิพจน์ (A * B) + (C / D)

นิพจน์ A / B + (C – D)

นิพจน์ (A + B) * ( C ^ D – E ) * F

สแตค (Stack)
สแตคเป็นโครงสร้างข้อมูลที่มีลักษณะแบบลำดับ (sequential) คือการกระทำกับข้อมูลจะกระทำที่ปลายข้างเดียวกันที่ส่วนปลายสุดของสแตค การกระทำกับข้อมูลของสแตคประกอบไปด้วยการนำเข้าข้อมูลเข้า (PUSH) ที่ส่วนบนสุดของสแตค และการนำข้อมูลออก (POP) ที่ส่วนบนสุดของสแตคเช่นกัน ในการจะ Push ข้อมูลเข้าก็ต้องตรวจสอบด้วยว่าข้อมูลในสแตคเต็มหรือไม่ หากสแตคเต็มก็จะไม่สามารถ Push หรือนำข้อมูลเข้าได้ เช่นเดียวกับการ Pop ข้อมูลออกก็ต้องตรวจสอบด้วยว่ามีข้อมูลอยู่ในสแตคหรือไม่ หากไม่มีข้อมูลอยู่ในสแตคหรือสแตคว่าง (empty stack) ก็ไม่สามารถ pop ได้
การนำข้อมูลเข้า-ออก จากสแตค (push , pop) จะมีลักษณะแบบเข้าหลัง ออกก่อน (LIFO : Last In , First Out) คือ ข้อมูลที่เข้าไปในสแตคลำดับหลังสุด จะถูกนำข้อมูลออกจากสแตคเป็นลำดับแรก ยกตัวอย่างการทำงานแบบ LIFO เช่น การวางจานซ้อนกัน
รูปแสดงลักษณะของสแตค ที่ประกอบด้วยข้อมูล A , B , C , D และ E มี TOP ที่ชี้ที่สมาชิกตัวบนสุดของสแตค



Operation ของสแตค
  • การเพิ่มข้อมูลลงในสแตค (pushing stack)
  • การดึงข้อมูลออกจากสแตค (popping stack)
การเพิ่มข้อมูลลงในสแตค
การเพิ่มข้อมูลลงในสแตค คือ การนำเข้ามูลเข้าสู่สแตคโดยทับข้อมูลที่อยู่บนสุดของสแตค ข้อมูลจะสามารถนำเข้าได้เรื่อยๆ จนกว่าสแตคจะเต็ม สมมติว่าสแตคจองเนื้อที่ไว้ N ตัว ถ้าหากค่า TOP เป็น 0 แสดงว่าสแตคว่าง หากค่า TOP = N แสดงว่าสแตคเต็มไม่สามารถเพิ่มข้อมูลลงในสแตคได้อีก
จากรูปแสดง การ Push ข้อมูล ABC ลงในสแตคที่มีการจองเนื้อที่ไว้ N ตัว โดยมี TOP ชี้ข้อมูลตัวที่เข้ามาล่าสุด โดยค่าของ TOP จะเพิ่มขึ้นทุกครั้งเมื่อมีข้อมูลเข้ามาในสแตค

การดึงข้อมูลออกจากสแตค
ก่อนที่จะดึงข้อมูลออกจากสแตคต้องตรวจสอบก่อนว่าสแตคมีข้อมูลอยู่หรือไม่ หรือว่าเป็นสแตคว่าง (Empty Stack)


การใช้ สแตค เพื่อแปลรูปนิพจน์ทางคณิตศาสตร์
รูปแบบนิพจน์ทางคณิตศาสตร์
• นิพจน์ Infix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่ระหว่างตัวดำเนินการ (Operands) เช่น A+B-C
• นิพจน์ Prefix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หน้าตัวดำเนินการ (Operands) เช่น +-AB
• นิพจน์ Postfix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หลังตัวดำเนินการ (Operands) เช่น AC*+

การประยุกต์ของสแตก
สแตกเป็นโครงสร้างข้อมูลที่มีประโยชน์มาก ถูกนำไปใช้ทั้งในซอฟท์แวร์ระบบ (System Software) และในการประยุกต์โดยยูสเซอร์ เช่น ช่วยคอมไพเลอร์ (Compiler) สร้างกฏเกณฑ์ของการโปรแกรมมิ่งเกี่ยวกับการเรียกโปรแกรมย่อย กฏเกณฑ์ของการโปรแกรมมิ่งอีกอย่างคือ คำสั่งเงื่อนไขซ้อน (Nested IF) ก็เช่นกัน สแตก ช่วยบอกว่า Else นี้คู่กับ IF ใด ซึ่งมีกฏเกณฑ์ว่า Else แรกจะคู่กับ If หลังสุด และ Else ถัดไป ก็จะคู่กับ IF ที่ถัดขึ้นไป จาก IF หลังสุด



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

Linked list
ลิงค์ ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ ซึ่งอาจอยู่ในลักษณะแบบเชิงเส้นตรง (linear) หรือ ไม่เป็นเส้นตรง (nonlinear) ก็ได้ ซึ่งในลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่าโหนด (node) ในหนึ่งโหนดจะประกอบด้วยส่วนของข้อมูลที่ต้องการจัดเก็บ เรียกว่าส่วน Info และส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป (Link) หรือชี้ไปยังโหนดอื่นๆที่อยู่ในลิสต์ หากไม่มีโหนดที่อยู่ถัดไป ส่วนที่เป็นพอยน์เตอร์หรือ Link จะเก็บค่า NULL หรือ NILL ใช้สัญลักษณ์ ^
โหนด (Node)

โครง สร้างแบบ Linked list แบ่งได้หลายแบบตามวิธีการชี้ไปยังโหนดต่างๆ เช่น Singly Linked list , Doubly Linked list , Multi-Linked list


Singly Linked list จะประกอบด้วยโหนดที่มีพอยน์เตอร์ชี้ไปในทิศทางเดียว คือชี้ไปยังโหนดถัดไป

จาก รูปหากทราบถึงโหนดแรกของ Linked list จะสามารถเข้าถึงข้อมูลทั้งหมดใน Linked list ได้ เนื่องจากแต่ละโหนดจะมีพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป ดังนั้น Linked list ต้องมี external พอยน์เตอร์ที่ชี้ไปยังโหนดแรกของ Linked list จากรูปใช้พอยน์เตอร์ H (Head)


 Linked list ประกอบไปด้วย node ซึ่งมีข้อมูลของแต่ละ node อยู่ประกอบไปด้วย ข้อมูลและตัวที่บ่งชี้ถึงโหนดต่อไป หากเป็นโหนดสุดท้ายจะมีค่าเป็น null ในภาษา java เราสามารถอ้างถึง reference ได้โดย object จึงสามารถที่จะสร้าง linked list ได้เช่นกันเหมือนกับภาษา C หรืออื่นๆเปรียบเสมือนกับ element เป็นตัวเก็บข้อมูล และ next ทำหน้าที่ในการชี้ถึงโหนดอื่น ๆ ต่อไป

การสร้าง Linked List


 วิธี สร้าง Linked list คือการนำข้อมูลที่จะจัดเก็บเข้า Linked list เพิ่มตรงโหนดตำแหน่งสุดท้ายของลิสต์ ฉะนั้นจึงต้องมี External พอยน์เตอร์ที่คอยชี้โหนดสุดท้ายของลิสต์ ในที่นี้ใช้ L (Last)
 ตัวอย่างการสร้าง Linked list จากลิสต์ L = 21 , 5 , 14
เริ่มจากการให้ H ชี้ทิ่โหนดตำแหน่งแรก และ L ชี้ทิ่โหนดตำแหน่งสุดท้าย
เพิ่มข้อมูล 5 เข้าไปใน list , L ชี้ไปยังโหนดที่เก็บข้อมูล 5
เพิ่มข้อมูล 14 เข้าไปใน list , L ชี้ไปยังโหนดที่เก็บข้อมูล 14



 การเพิ่มและลบข้อมูลใน Linked list


การเพิ่มข้อมูลที่ต้น list

จากรูป จะเพิ่ม NODE(tmp) ลงใน linked list โดยมีขั้นตอนคือ

tmp = new ListNode();
tmp.element = 12;
tmp.next = current.next;

การเพิ่มข้อมูลโดยแทรกลงในลิสต์

การเพิ่มข้อมูลจะทำการแทรกโหนด NEW หลังโหนด P
ตัวอย่าง ทำการเพิ่มข้อมูลโหนด 16 ระหว่างโหนด 21 และ 5

จากรูปมีขั้นตอนดังนี้
tmp = new ListNode();
tmp.element = 16;
tmp.next = current.next;
current.next = tmp;


การลบข้อมูลใน Linked list
การลบข้อมูลที่ต้น list

เนื่อง จากขั้นตอนของการลบข้อมูลที่ header นั้นจะมีปัญหาที่ยุ่งยากกว่าเมื่อ design ด้วย oop(java) เราสามารถที่จะแก้ปัญหานี้ได้โดยการใส่ header node ที่ว่าง ๆ ไว้ข้างหน้าของ linked list เพื่อที่จะทำหน้าที่เป็นชี้ว่าเป็นหัวโหนดโดยที่ไม่ต้องมี pointer คอยชี้ที่ header และเมื่อเราต้องการที่จะเปลี่ยนแปลงข้อมูลใด ๆ บนหัวสามารถที่จะทำได้โดยการแทรก node เข้าไปดังตัวอย่างของการแทรกข้อมูลข้างล่าง


การแทรกข้อมูลลงในโหนดที่ต้องการ

จากรูปมีขั้นตอนดังนี้
tmp.next = tmp.next.next;

Pointer คือสัญลักษณ์ที่ใช้แทนตำแหน่งของหน่วยความจำตัวแปร pointer ทุกชนิดจะใช้ หน่วยความจำ 2 ไบต์ เท่ากันหมด เพราะว่าเอาไว้เก็บตำแหน่งใดๆ ในหน่วยความจำเท่านั้น ซึ่งหน่วยความจำที่เตรียมไว้ให้ตัวแปรต่างๆ มีตำแหน่งตั้งแต่ 0 ถึง 65535 ฉะนั้น 2 ไบต์(16 บิต) จึงเพียงพอในการเก็บค่าดังกล่าว
การดำเนินงาน
Relational =, <>
Dynamic allocation new, dispose
ชนิดของข้อมูลแบบพอยเตอร์
ค่าของข้อมูล เป็น nil คือไม่มีค่า หรือ มีค่าเป็น address ของตัวแปร โครงสร้างของข้อมูล ไม่มีความสัมพันธ์กัน
pointer มีประโยชน์หลายอย่างดังนี้
1. ช่วยประหยัดหน่วยความจำ ไม่ต้องประกาศตัวแปรหลายๆ ครั้งเพื่อ ส่งค่าไปมา โดยเฉพาะการส่งค่าไปมาระหว่างฟังก์ชัน ถ้าเราใช้ pointer มาช่วยในการส่งค่าแบบอ้างอิง ทำให้ใน function ที่รับค่า ไม่จำเป็นต้องประกาศตัวแปรแบบเดียวกันซ้ำอีก จะเห็นได้ชัดเจนในตัวแปรแบบ array
2. ช่วยประหยัดเวลา เพราะการส่งค่าไปมาแล้วเปลี่ยนแปลงค่าที่ส่งหากันระหว่างฟังก์ชันจะทำให้เสียเวลามากกว่า แต่ถ้าเราใช้ตัวแปร pointer เลย ก็จะทำให้เข้าถึงหน่วยความจำในตำแหน่งเดียวกันเลย ทำให้ไม่ต้อง copy ค่าดังกล่าวอีก
3. ช่วยลดข้อจำกัดของ array ที่ว่า
- array ต้องจองเผื่อไว้ แต่ถ้าเราใช้ link-list (เป็นวิธีการทาง pointer ชนิดหนึ่ง) ในการจองหน่วยความจำ เราไม่ต้องจองหน่วยความจำเผื่อไว้เลย
- array ต้องจองหน่วยความจำที่เป็นที่ว่างติดกัน แต่ link-list จองที่ว่างที่ไม่ติดกันได้
- array มีขนาดที่จำกัด ตามที่ว่างที่ติดกันที่เหลืออยู่ในหน่วยความจำภายใน 1 เซ็กเม้น(65536 ไบต์) แต่ link-list จะจองหน่วยความจำได้ไม่จำกัดขึ้นอยู่กับขนาดของหน่วยความจำเลย

ชนิดข้อมูลแบบสตริงค์
ชนิดข้อมูลแบบสตริงค์ ไม่ได้เป็นชนิดข้อมูลมาตรฐานของปาสคาล แต่มีที่ใช้บ่อยมากในการเขียนโปรแกรม ตัวแปรภาษาจึงได้เพิ่มชนิดข้อมูลนี้ขึ้นเป็นชนิดข้อมูลมาตรฐานอีกตัวหนึ่ง ในความเป็นจริงแล้ว ชนิดข้อมูลแบบสตริงค์ก็คือ packed array of char ซึ่งค่าของข้อมูลคือ char และมีโครงสร้างเหมือนอะเรย์ โดยมีการดำเนินงาน ดังนี้
Relational =, <>, <, >, <=, >=, in
Textfile I/O read, readln, write, writeln
Procedure/Functions มีมากมายขึ้นอยู่กับ compiler ที่ใช้
-------------------------------------------------------------------------------------------------