เรื่อง Linked List

เนื้อหา
- โครงสร้างข้อมูลแบบลิงค์ลิสต
- กระบวนงานและฟังกชั่นที่ใช้ดำเนินงานพื้นฐาน
- การสร้างลิงค์ลิสต
- ลิงค์ลิสต์แบบซับซ้อน

จุดประสงค์การเรียนรู้
1. เพื่อให้นักศึกษาทราบโครงสร้างข้อมูลแบบลิงค์ลิสต
2. เพื่อให้ทราบกระบวนการทำงานและฟังกชั่นที่ ใช้ดำเนินงานพื้นฐานของลิงค์ลิสต
3. เพื่อให้นักศึกษาทราบวิธีการสร้างลิงค์ลิสต
4. เพื่อให้นักศึกษาทราบการทางานของลิงค์ลิสต แบบซับซ้อน

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

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

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

โครงสร้างข้อมูลแบบลิงค์ลิสตโครงสร้างข้อมูลแบบลิงค์ลิสตจะแบ่งเป็น 2 ส่วน คือ

1. Head Structure จะประกอบไปด้วย 3 ส่วน ได้แก่ จำนวนโหนดในลิสต (Count)พอยเตอร์ที่ชี้ไปยัง โหนดที่เข้าถึง(Pos) และพอยเตอร์ที่ชี้ไปยังโหนดข้อูมลแรกของลิสต (Head)

2. Data Node Structure จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป

กระบวนงานและฟังกชั่นทใช้ดำเนินงานพื้นฐาน

1. กระบวนงาน Create Listหน้าที่ สร้างลิสตว่างผลลัพธ์ ลิสตว่าง

Algorithm CreateList

Pre Nothing

Post Head node allocated or error returned

Return Head node pointer or null if memory overflow

1. if (memory available)

1 allocate (Pnew)

2 pNew->head = null pointer

3 pNew->count = 0
2. else

1 pNew = null poiter

3. return pNew

End CreateList

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

กระบวนงานและฟังกชั่นทใช้ดำเนินงานพื้นฐาน
1. กระบวนงาน Create List
หน้าที่ สร้างลิสตว่าง
ผลลัพธ์ ลิสตว่าง Algorithm CreateList
Pre Nothing
Post Head node allocated or error returned
Return Head node pointer or null if memory overflow
1. if (memory available)
1 allocate (Pnew)
2 pNew->head = null pointer
3 pNew->count = 0
2. else
1 pNew = null poiter
3. return pNew
End CreateList

2.กระบวนงาน Insert Nodeหน้าที่เพิ่มข้อมูลลงไปในลิสตบริเวณตำแหน่งที่ต้องการข้อมูลนำเข้าลิสต ข้อมูล และตำแหน่งผลลัพธ์ ลิสตที่มีการเปลี่ยนแปลง

Algorithm insertNode
val pPre ,
val dataIn )

Pre pList is a pointer to a valid list head structurep
Pre is a pointer todata’s logical predecessordataIn contains data to be inserted
Post data have been insert in sequence
Return true if successful, false if memory overflow
Allocate (pNew)
If (memory overflow)
1 return false
pNew->data = dataIn
3. If (pPre null)
1 pNew->link = pList->head
2 pList->head = pNew
5. else
1 pNew->link = pPre->link
2 pPre->link = pNew
6. pList->count = pList->count +1
7. Return true
End insertNode

3. กระบวนงาน Delete Node หน้าที่ลบสมาชิกในลิสตบริเวณตำแหน่งที่ต้องการข้อมูลนำเข้าข้อมูลและตำแหน่งผลลัพธ์ ลิสตที่มีการเปลี่ยนแปลง

Algorithm deleteNode
val pPre ,
val pLoc ,
ref dataOut )

Pre pList is a pointer to a valid list head structure
pPre is a pointer to predecessor node
pLoc is a pointer to node to be deleteddataOut is address to pass deleted data to

calling module
Post data have been delete and return to caller

1. dataOut = pLoc->data
2. if (pPre null)
1 pList->head = pLoc->link
3. Else1 pPre->link = pLoc->link
4. pList->count = pList->count - 1
5. Release (pLoc)
6. ReturnEnd deleteNode
4. กระบวนงาน Search listหน้าที่ค้นหาข้อมูลในลิสตที่ต้องการข้อมูลนำเข้าลิสตผลลัพธ์ ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่พบข้อมูล

Algorithm searchList (
val pList val pPre ,
ref pLoc ,
val target )

Pre pList is a pointer to a valid list head structure
pPre is a pointer to receive predecessor
pLoc is a pointer to receive current node
target is the key being sought
Post pLoc points to first node with equal or greater key or null if target >
key of last node

pPre points to largest node smaller than key or null if target<>

Return true if found, false if not found
pPre = null
pLoc = pList->head
loop (pLoc not null AND target > pLoc->data.key)

1 pPre = pLoc
2 pLoc = pLoc->link
If (pLoc null)
1 found = false
else
1 if (target equal pLoc->data.key)
1 found = true
2 else
1 found = false
Return found
Return searchList

5.กระบวนงาน Traverse หน้าที่ ท่องไปในลิสตเพื่อเข้าถึงและประมวลผลข้อมูลนำเข้าลิสตผลลัพธ์ ขึ้นกับการประมวลผล เช่น เปลี่ยนแปลงค่าใน node , รวมฟิลด์ในลิสต , คำนวณค่าเฉลยของฟิลด์ เป็นต้น

Algorithm traverse
ref dataPtr)
Pre pList is a pointer to a valid list head structurefromWhere is 0 to start at the first elementdataPtr is address of a pointer to dataPost address placed in dataPtr and return true or if end of list, returnfalseReturn true if next element located, false if end of list

เรื่อง Queue

เนื้อหา
- โครงสร้างข้อมูลแบบคิว
- การทำงานของคิว
- การแทนที่ข้อมูลของคิว
- การประยุกต์ใช้คิว

จุดประสงค์การเรียนรู้
1. เพี่อให้นักศึกษาทราบโครงสร้างข้อมูลแบบคิว และการทำงาน
2. เพื่อให้ทราบวิธีการแทนที่ข้อมูลแบบคิว
3. เพื่อให้นักศึกษาทราบวิธีการประยุกต์ใช้สแตก

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

การนำสมาชิกออกจากคิว เรียกว่า Dequeue ซึ่งมีรูปแบบคือdequeue (queue, element)
หมายถึง การนำออกจากส่วนหน้า ของคิวและให้ ข้อมูลนั้นกับ element

การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดงจะ เรียกว่า Queue Frontแต่จะไม่ทำการเอาข้อมูลออกจากคิว การนำข้อมูลที่อยู่ตอนท้ายของคิวมาแสดงจะ เรียกว่าQueue Rear แต่จะไม่ทำการเพิ่มข้อมูลเข้าไปในคิว


การแทนที่ข้อมูลของคิวการแทนที่ข้อมูลของคิวสามารถทาได 2 วิธี คือ
1. การแทนที่ข้อมูลของคิวแบบลิงค์ลิสค์
2. การแทนที่ข้อมูลของคิวแบบอะเรย์

การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต

การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต จะประกอบไปด้วย 2 ส่วน คือ
1. Head Node จะประกอบไปด้วย 3 ส่วนคือ พอยเตอร์จำนวน 2 ตัว คือ Front และ rear กับจำนวนสมาชิกในคิว
2. Data Node จะประกอบไปด้วย ข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป

การดำเนินการเกี่ยวกับคิวการดำเนินการเกี่ยวกับคิว ได้แก่
1. Create Queue
2. Enqueue
3. Dequeue
4. Queue Front
5. Queue Rear
6. Empty Queue
7. Full Queue
8. Queue Count
9. Destroy Queue
Algorithm CreateQueue
Pre Nothing
Post Head has been allocated and initialized
Return Head’s address if successful, null if overflow
1. if (memory available)

allocate (newPrt)
2 newPtr->front = null pointer
3 newPtr->rear = null pointer
4 newPtr->count = 0
5 return newPtr
2. Else1 return null pointer
End CreateQueue

Algorithm EnQueue
Queue has been create
Post Item data have been inserted
Return Boolean; True: if successful, False ifoverflow
1. if (queue full)
1 return false

1 allocate(newPtr)
2 newPtr->data = item
3 newPtr->next = null pointer
4 if (queue->count zero)
1 queue->front = newPtr
5 else1 queue->rear->next = newPtr
6 queue->rear = newPtr
7 queue->count = queue->count+1
8 return true
End EnQueue

Algorithm DeQueue
Queue has been create
Data at front of queue returned to userthrough item and front element deleted and recycled
Return Boolean; True: if successful, False ifunderflow
1. if (queue->count is 0)
1 return false

1 item = queue->front->data
2 deleteLoc = queue->front
3 if (queue->count 1)
1 queue->rear = null pointer
4 queue->front = queue->front->next
5 queue->count = queue->count-1
6 recycle(deleteLoc)
7 return true
End Dequeue

4.Queue Front เป็นการนำข้อมูลที่อยู่ส่วนต้นของคิวมา
Algorithm QueueFront
Queue is a pointer to an initialized queue
Post Data pass back to caller
Return Boolean; True: successful, False ifunderflow

5. Queue Rear เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง
Algorithm QueueRearPre
Queue is a pointer to an initialized queue
Post Data pass back to caller
Return Boolean; True: successful, False if underflow

6. Empty Queue เป็นการตรวจสอบว่าคิวว่างหรือไม่
Algorithm EmptyQueue
Queue is a pointer to a queuehead node
Return Boolean; True: if empty, False if queuehas data
1. Return (queue->count equal 0)
End EmptyQueue

7. Full Queue เป็นการตรวจสอบว่าคิวเต็มหรือไม่
Algorithm FullQueue
Pre Queue is a pointer to a queue head node
Return Boolean; True: if full, False if room for anothernode
1. allocate (tempPtr)
2. if (allocation successful)
1 release (tempPtr)
2 return false
3. else
1 return true
End FullQueue

8. Queue Count เป็นการนับจำนวนสมาชิกที่อยู่ในคิว
Algorithm QueueCount
Queue is a pointer to the queuehead node
Return Queue count
1. Return queue->count
End QueueCount

9. Destroy Queue เป็นการลบข้อมูลทั้งหมดที่อยู่ในคิว Algorithm DestroyQueue
Queue is valid queue
All data have been deleted and recycled
Return null pointer
1. pWalker = queue->front
2. Loop(pWalker not null)
1 deletePtr = pWalker
2 pWalker = pWalker->next
3 recycle (deletePtr)
4 recycle (queue)
5 return null pointer1.
End DestroyCount

การแทนที่ข้อมูลของคิวแบบอะเรย์

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

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

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

แบบฝึกหัด
1. อธิบายหลักการทำงานของ Queue
2. การแทนที่ของข้อมูลในคิวมีกี่ประเภทอะไร้บาง อธิบายพร้อมยกตวอย่างประกอบ
3. การประยกตใช คว ในชวตประจาวนทเกดขน

เรื่อง Stack

เนื้อหา
- โครงสร้างข้อมูลแบบสแตก
- การดำเนินงานพื้นฐานของสแตก

- การแทนที่ข้อมูลของสแตก
- การประยุกต์ใช้สแตก

จุดประสงค์การเรียนรู้

1. เพื่อให้นักศึกษาทราบโครงสร้างข้อมูลแบบสแตกและการทำงาน
2. เพื่อให้นักศึกษาทราบการดำเนินงานพื้นฐานของสแตก
3. เพื่อให้นักศึกษาทราบการแทนที่ของข้อมูลแบบสแตก

4. เพื่อให้นักศึกษาทราบวิธีการประยุกต์ใช้สแตก

สแตก(Stack)เป็นโครงสร้างข้อมูลที่ ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่าการเพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ปลายข้างเดียวกัน ซึ่งเรียกว่า Topของสแตก (Top Of Stack)และ ลักษณะที่สำคัญของสแตก คือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมา จากสแตกเป็นลำดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO (Last In First Out)การดำเนินงานพื้นฐานของสแตกการทำงานต่าง ๆของสแตกจะกระทาที่ปลายข้างหนึ่งของสแตกเท่านั้นดั้งนั้นจะต้องมีตัวชี้ตำแหน่งข้อมูลบนสุดของสแตกด้วยการทำงานของสแตกจะประกอบด้วยกระบวนการ 3กระบวนการที่สำคัญ คือ

1.Push คือ การนำข้อมูลใส่ลงไปในสแตกเช่น สแตก s ต้องการใส่ข้อมูล iในสแตกจะได้ push(s,i)คือ ใส่ข้อมูล i ลงไปที่ท็อปของสแตก sในการเพิ่มข้อมูลลงในสแตก จะต้องทำการ ตรวจสอบว่าสแตก เต็มหรือไม่ ถ้าไม้เต็มก็ สามารถเพิ่มข้อมูลลงไปในสแตกได้แล้วปรับตัวชี้ตำแหน่งให้ไปชี้ที่ตำแหน่งข้อมูลใหม่ ถ้าสแตกเต็ม (Stack Overflow)ก็จะไม่สามารถเพิ่มข้อมูลเขาไปในสแตกได้อีก

2.Pop คือการนำข้อมูลออกจากส่วนบนสุดของสแตกเช่น ต้องการนำข้อมูลออกจากสแตกsไปไว้ที่ตัวแปร iจะได้ i = pop (s)การนำข้อมูลออกจากสแตกถ้าสแตกมีสมาชิกเพียง 1ตัวแล้วนำสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง(Stack Empty) คือ ไม่มีสมาชิกอยู่ในสแตกเลยแต่ถ้าไม่มีสมาชิกในสแตกแล้วทำการ popสแตกจะทำให้เกิดความผิดพลาดที่เรียกว่าStack Underflow เพราะฉะนั้นก่อนนำข้อมูลออกจากสแตกจะต้องตรวจสอบก่อนว่าสแตกว่างหรือเปล่าจึงจะนำข้อมูลออกจากสแตกได้ และ ปรับตัวชี้ตำแหน่งให้ไปชี้ตำแหน่งของข้อมูลที่ต่อจากข้อมูลที่ถูกนำออกไป 3.Stack Top ป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตกแต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตกตัวอย่าง
การแทนที่ข้อมูลของสแตก
การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ
1. การแทนที้ข้อมูลของสแตกแบบลิงค์ลิสต
2. การแทนที่ข้อมูลของสแตกแบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสตจะประกอบไปด้วย 2 ส่วน คือ
1. Head Node จะประกอบไปด้วย 2ส่วนคือ top pointer และจำนวนสมาชิกในสแตก
2. Data Node จะประกอบไปด้วยข้อมูล (Data)และพอยเตอร์ ที่ชี้ไปยังข้อมูล การดำเนินการเกี่ยวกับสแตกการดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack
2. Push Stack
3. Pop Stack
4. Stack Top
5. Empty Stack
6. Full Stack
7. Stack Count
8. Destroy Stack

1. Create Stack จัดสรรหน่วยความจำให้แก่ Head Nodeและส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา

Algorithm CreateStack
Nothing
Post Head node allocated or error returned
Return Pointer to head node or null pointer if no
memory
1. if (memory available)
1 allocate (StackPrt)
2 StackPtr->count=0
3 StackPtr->top=null pointer
2. else
1 StackPtr=null pointer
3. return StackPtr
End
CreateStack

2.Push Stackการเพิ่มข้อมูลลงไปในสแตก

Algorithm PushStack
Pre Stack is a pointer to the stack head structure
Data contains data to pushed into stack
Post Data have been pushed in stack
Return True if successful; False if memory overflow
1. if (stack full)
1 success = false
2. else
1 allocate (newPtr)
2 newPtr->data =data
3 newPtr->next =stack->top
4 stack->top =newPtr
5 stack->count =stack->count+1
6 succes = true
3. return success

3.Pop stack การยำข้อมูลบนสุดออกจากสแตก
Algorithm PopStack
Pre Stack is a pointer to the stack head structure
DataOut is a reference variable to receive the data
Post Data have been returned to calling algorithm
Return True if successful; False if underflow
1. if (stack empty)
1 success = false
2. else
1 dltPtr->data =stack->top
2 dataOut =stack->top->data
3 stack->top =stack->top
4 stack->count =stack->count-1
5 recycle (dltPtr)
6 succes = true
3. return successEnd PopStack

4. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตกโดยไม่มีการลบข้อมูลออกจากสแตก
Algorithm StackTop
Pre Stack is a pointer to the stack head structure
DataOut is a reference variable to receive the data
Post Data have been returned to calling algorithm
Return True if data returned; False if underflow
1. if (stack empty)
1 success = false
2. else
1 dataOut = stack->top->data
2 succes = true
3. return successEnd StackTop

5.Empty Stack เป็นการตรวจสอบการวางของสแตกเพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลออกจากสแตกที่เรียกว่า Stack Underflow
Algorithm EmptyStack
Pre Stack is a pointer to the stack head structure
Post Returns stack status
Return Boolean, true: stack empty, false: stack contains data
1. if (stack not empty)
1 result = false
2. else
1 result = true
3. return result
End EmptyStack

6. Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
Algorithm FullStack
Pre Stack is a pointer to the stack head structure
Post Returns stack status
Return Boolean, true: stack full, false: memory available
1. if (memory available)
1 result = false
2. else
1 result = true
3. return result
End FullStack

7. Stack Count เป็นการนับจำนวนสมาชิกในสแตก
Algorithm StackCount
Pre Stack is a pointer to the stack head structure
Post Returns stack count
Return integer count of number of elements in stack
1. Return (stack->count)
End StackCount

8.Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ใน สแตก

Algorithm DestroyStack
Pre Stack is a pointer to the stack head structure
Post Stack empty and all nodes recycled
Return null pointer
1. if (stack not empty)
1 loop (stack->top not null)
1 temp = stack->top
2 stack->top = stack->top->link
3 recycle (temp)
Recycle (stack)
Return null pointer
End DestroyStack

Stack Definition for Array Implementation
stackAry dataType>
stackMax
End Stack

การดำเนินการเกี่ยวกับสแตกการดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack
2. Push Stack
3. Pop Stack
4. Stack Top
5. Empty Stack
6. Full Stack
7. Stack Count
8. Destroy Stack

1. Create Stack
Algorithm CreateStack
stackElem contains size of stack
Head node and array allocated or error returned
Return Pointer to head node or null pointer if no memory
1. if (memory not available)
1 StackPtr = null
1 allocate (StackPtr)
2 StackPtr->count = 0
3 StackPtr->top = -1
4 StackPtr->stackMax=stackElem
5 if (memory not available)
1 recycle (StackPtr)
2 StackPtr = null
6 else1 allocate (StackPtr->stackAry)
3. return StackPtr
End CreateStack

2. Push Stack
Algorithm PushStack
Pre Stack is a pointer to the stack head structureData contains data to be pushed into stack
Post Data have been pushed in stack
Return True if successful ; False if memory overflow
1. if (stack->count is at maximum)
1 success = false

1 stack->count = stack->count + 1
2 stack->top = stack->top + 1
3 stack->stackAry[stack->top] = data
4 success = true
3. Return success
End PushStack

3. Pop Stack
Algorithm PushStack
Pre Stack is a pointer to the stack head structureDataOut contains a reference variable to receive the data
Post Data have been returned to calling algorithm
Return True if successful ; False if underflow
1. if (stack empty)
1 success = false
2. else
1 dataOut = stack->stackAry[stack->top]
2 stack->top = stack->top - 1
3 stack->count = stack->count - 1
4 success = true
3. Return success
End PopStack

4. Stack Top
Algorithm StackTop
Stack is a pointer to the stack headstructure
Data have been returned to calling algorithm
Return True if data returned ; False if underflow
1. if (stack->count zero)
1 success = false
1 dataOut = stack->stackAry[stack->top].data
2 success = true
3. return success
End StackTop

5. Empty Stack
Algorithm EmptyStack
Pre Stack is a pointer to the stack headstructure
Post Return stack status
Return Boolean; True: stack empty , False: stackcontain data
1. if (stack->count > 0)
1 result = false
2 else
1 result = true
3. return result
End EmptyStack

6. Full Stack
Algorithm Full
StackStack is a pointer to the stack
head structure
Post Return stack status
Return Boolean; True: stack full , False:
memory available
1. if (stack->count < result =" false" result =" true">

7. Stack Count
Algorithm StackCount
Pre Stack is a pointer to the stack headstructure
Post Return stack count
Return Integer count of number of elements in stack
1. return (stack->count)
End StackCount

8. Destroy Stack
Algorithm DestroyStack
Pre Stack is a pointer to the stack head structure
Post Head structure and array recycled
Return null pointer
1.if (stack no empty)
1 recycle (stack->stackAry)
2 recycle (stack)
2.return null pointer
End DestroyStack

การประยุกต์ใช้สแตก
การประยุกต์ใช้สแตก จะใช้ในงานด้าน ปฏิบัตการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสารอันดับแรกสุดไว้ใช้ หลังสุด เช่น การทำงานของโปรแกรมแปลภาษานำไปใช้ในเรื่องของการโปรแกรมที่เรียกใช้โปรแกรมย่อย การคำนวณนิพจน์ทาง คณิตศาสตร์ และรีเคอร์ชั่น (Recursion)

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

แสดงโปรแกรมหลักที่มีการเรียกใช้โปรแกรมย่อย การคำนวณนิพจน์ทางคณิตศาสตร์ในการเขียนนิพจน์ทางคณิตศาสตร์เพื่อการคำนวณจะต้องคำนึงถึงลำดับความสำคัญของเครื่องหมายสำหรับการคำนวณด้วยโดยทั่วไปนิพจน์ทางคณิตศาสตร์สามารถเขียนได้ 3 รูปแบบ คือ
1. นิพจน์ Infix นิพจน์รูปแบบนี้ operatorจะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ 2 ตัว
2. นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และ 2 ก่อน แล้วตามด้วย operator 3. นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operatorก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2

ตัวอย่างนิพจน์คณิตศาสตร์ในรูปแบบต่าง ๆ
นิพจน์ Postfix นิพจน์ Prefix
AB+C- - +ABC
ABC*+DE/- - +A*BC/DE
AB*C+DE/- - +*ABC/DE

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

ค่าลำดับความสำคัญของตัวดำเนินการ
ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์
1. อ่านอักขระในนิพจน์ Infix เข้ามาที่ละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
- ถามความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถามความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัว ดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์ Postfix
4.ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตกแต่มีผลให้ตัวดำเนินการอื่น ๆ ถูก popออกจากสแตก นำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ popวงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5.เมื่อทำการอ่านตัวอักษรในนิพจน์ Infix หมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุก ตัวในสแตกนำมาเรียงต่อในนิพจน์
ตัวอย่าง
การแปลงนิพจน์ Infix เป็นนิพจน์ Postfix นิพจน์ A-B/C+D*Eตัวที่อ่านเข้ามา ผลลัพธ์ในสแตก นิพจน์ Postfix
A ว่าง A
- - A
B - AB
/ -/ AB
C -/ ABC
+ + ABC/-
D + ABC/-D
* +* ABC/-D
E +* ABC/-DE
ABC/-DE*+
นิพจน์ A*(B+C-D)/E ในการคำนวณค่า Postfix ที่แปลงมาแล้ว ตัวแปลภาษาจะทำการคำนวณโดยใช้โครงสร้างสแตกช่วยอีกเช่นกัน ขั้นตอนในการคำนวณ
1. อ่านตัวอักษรในนิพจน์ Postfix จากซ้ายไปขวาทีละ ตัวอักษร
2. ถ้าเป็นตัวถูกดำเนินการ ให้ทำการ push ตัวถูกดำเนินการ นั้นลงในสแตก แล้วกลับไปอ่านอักษรตัวใหม่เข้ามา
3. ถ้าเป็นตัวดำเนินการ ให้ทำการ pop ค่าจากสแตก 2 ค่า โดยตัวแรกเป็นตัวถูกดำเนินการตัวที่ 2 และตัวที่ 1ตามลำดับ
4. ทำการคำนวณ ตัวถูกดำเนินการตัวที่ 1ด้วยตัวถูกดำเนินการตัวที่ 2โดยใช้ตัวดำเนินการในข้อ 3
5. ทำการ push ผลลัพธท์ได้จากการคำนวณในข้อ 4 ลงสแตก
6. ถ้าตัวอักษรในนิพจน์ Postfix ยังอ่านไม่หมดให้กลับไปทำข้อ 1 ใหม่

Algorithm PostfixEvaluate
Pre a valid expression
Post postfix value computed
Return value of expression
1. exprSize= length of string
2. Stack = createStack
3. Index = 1
4. Loop (index<=exprSize) 1 if (expr[index] is operand 1 pushStack(stack,exp[index]) 1 popStack(stack, operand2) 2 popStack(stack, operand1) 3 operator = expr[index] 4 value = calculate (operand1, operator,
5 pushStack(stack,value)
3 index= index+1
5. popStack(stack,result)
6. destroyStack(stack)
7. return (result)
End PostfixEvaluate

ตัวอย่าง
ขั้นตอนการคำนวณจากนิพจน์ Postfix ABC+D-*E/



แบบฝึกหัด
1. อธิบายหลักการทำงานของ Stack
2. การแทนที่ของข้อมูลในสแตกมีกี่ประเภท อะไรบ้าง อธิบายพร้อมยกตัวอย่างประกอบ
3. การประยุกต์ใช้ สแตก Postfix ของ AB+CD*-E/ ใหอธิบายตามขั้นตอนการทำงาน
4. 15*A-F+D/J-(5*T)