กองซ้อน
จากวิกิพีเดีย สารานุกรมเสรี
-
สำหรับความหมายอื่น ดูที่ สแตก (แก้ความกำกวม)
| กองซ้อน | |
|---|---|
| ความสำคัญของลำดับ | FILO (First In Last Out) |
| การซ้ำกันของสมาชิก | อนุญาตให้ซ้ำกันได้ |
| วิธีการเข้าถึง(access) | PUSH/POP |
| เวลาที่ใช้ในการเข้าถึง | O(1) |
| โครงสร้างข้อมูลที่มีรูปแบบนี้ | |
กองซ้อน หรือ สแตก (อังกฤษ: Stack) หมายถึง ประเภทข้อมูลอย่างย่อที่มีลักษณะการเรียงลำดับข้อมูล ในการเข้า-ออกในลักษณะเข้าก่อนออกทีหลัง FILO (First In Last Out) กล่าวคือข้อมูลที่เข้าใหม่ๆจะได้ออกก่อน คล้ายกองที่ทับถมซึ่งสิ่งที่เข้ามาใหม่จะอยู่ด้านบนๆ จึงเรียกว่า กองซ้อน (stack)
กองซ้อนจึงเป็นวิธีการจัดการเข้า-ออกของข้อมูลอีกแบบหนึ่ง เป็นโครงสร้างข้อมูลที่นำมาใช้ในการทำงานของโปรแกรมคอมพิวเตอร์หลายประการ อาทิการสร้าง subroutine การเรียงลำดับนิพจน์ ฯลฯ
เนื้อหา |
[แก้] จุดเด่นของกองซ้อน
กองซ้อนมีจุดเด่นในการจัดการการเข้า-ออกของข้อมูล ใช้เก็บข้อมูลที่ต้องการจัดเรียงเป็นระบบ โดยพิจารณาข้อมูลที่มาใหม่ๆก่อน จึงทำให้สะดวกต่อการจัดการข้อมูลซึ่งต้องการเรียงลำดับใหม่ หรือการย้อนกลับไปจากข้อมูลใหม่ไปข้อมูลเก่า เช่น subroutine,การเรียงลำดับนิพจน์
[แก้] บริการที่มักจะมี
- การเก็บเข้ากองซ้อน (Push)
- การดึงข้อมูลบนสุดของกองซ้อน (Pop)
- การดูข้อมูลบนสุดของกองซ้อน (Top)
- ทำกองซ้อนให้ว่าง ตรวจสอบความว่างของกองซ้อน (Empty)
[แก้] ความเร็วที่ใช้ในการทำงาน
การทำงานของกองซ้อนนั้นไม่ซับซ้อน เนื่องจากไม่ต้องมีการไล่พิจารณาสมาชิกทุกตัว เป็นเพียงแต่การพิจารณาข้อมูลบนสุดของกองซ้อน จึงทำให้ความเร็วในการทำงานของกองซ้อนเป็นค่าคงที่ (O(1))
[แก้] วิธีการสร้างกองซ้อน
การสร้างกองซ้อนอาจใช้แถวลำดับประกอบกับจำนวนเต็ม ที่เก็บดัชนีของข้อมูลบนสุดของกองซ้อน (Stack Pointer หรือ Top of Stack)หรือใช้รายการโยงโดยการเก็บข้อมูลที่ใหม่ๆบนตัวแรกสุดของรายการ
การเก็บข้อมูลใหม่เข้าในกองซ้อนเรียกว่า PUSH ทำได้โดยการเพิ่มค่าดัชนีบนสุดของกองซ้อนไปหนึ่ง (increment)และเก็บข้อมูลใหม่ไว้ในดัชนีนั้น หรือเพิ่มเข้าไปที่ตัวแรกสุดของรายการโยง การนำข้อมูลตัวบนสุดของกองซ้อนออกเรียกว่า POP ทำได้โดยการคืนค่าข้อมูลที่เก็บไว้ในแถวลำดับ ดัชนีบนสุดและลดค่าดัชนีบนสุดลงมาอีกหนึ่ง(decrement) หรือเอาตัวแรกสุดของรายการโยงออก สำหรับ การหาตัวบนสุด(Top)นั้นก็ได้มาจากการคืนค่าข้อมูลในดัชนีบนสุดหรือข้อมูลตัวแรกสุดของรายการโยงนั้นเอง
[แก้] ดูเพิ่ม
|
||||||||||||||||||||
