เรากำลังดำเนินการเพื่อคืนค่าแอป Unionpedia บน Google Play Store
ขาออกขาเข้า
🌟เราได้ทำให้การออกแบบของเราง่ายขึ้นเพื่อการนำทางที่ดีขึ้น!
Instagram Facebook X LinkedIn

กองซ้อน

ดัชนี กองซ้อน

กองซ้อน หรือ สแต็ก หมายถึง แบบชนิดข้อมูลนามธรรมที่มีลักษณะการเรียงลำดับข้อมูล ในการเข้า-ออกในลักษณะเข้าก่อนออกทีหลัง FILO (First In Last Out) กล่าวคือข้อมูลที่เข้าใหม่ๆจะได้ออกก่อน คล้ายกองที่ทับถมซึ่งสิ่งที่เข้ามาใหม่จะอยู่ด้านบนๆ จึงเรียกว่า กองซ้อน (stack) กองซ้อนมีการดำเนินการพื้นฐานเพียง 3 อย่าง ได้แก่ push, pop และ top กองซ้อน โดยที่การ push คือการใส่ข้อมูลลงไปในกองซ้อน ซึ่งจะกระทำได้หากกองซ้อนยังว่างอยู่ หากไม่มีที่ว่างในกองซ้อนเหลืออยู่หรือกองซ้อนเต็ม กองซ้อนนั้นจะอยู่ในสภาวะล้นหรือมากเกินเก็บ (overflow) การ pop คือการนำข้อมูลออกจากส่วนบนสุดของกองซ้อน นอกจากนี้ การ pop จะเผยข้อมูลที่ถูกผิดอยู่ก่อนหน้า หรือทำให้กองซ้อนว่างได้ แต่ถ้ากองซ้อนนั้นว่างอยู่แล้ว การ pop จะทำให้อยู่ในสภาวะน้อยเกินเก็บ (underflow) (นั่นคือ ไม่มีข้อมูลให้นำออกแล้ว) การ top กองซ้อน จะดึงข้อมูลที่อยู่บนสุดและส่งค่านั้นให้ผู้ใช้โดยที่ไม่ได้ลบทิ้งไป การ top กองซ้อนอาจทำให้กองซ้อนอยู่ในสภาวะน้อยเกินเก็บได้เช่นกัน หากกองซ้อนว่างอยู่แล้ว กองซ้อนจึงเป็นวิธีการจัดการเข้า-ออกของข้อมูลอีกแบบหนึ่ง เป็นโครงสร้างข้อมูลที่นำมาใช้ในการทำงานของโปรแกรมคอมพิวเตอร์หลายประการ อาทิการสร้าง subroutine การเรียงลำดับนิพจน์ ฯลฯ.

สารบัญ

  1. 7 ความสัมพันธ์: รายการโยงสัญกรณ์โอใหญ่แบบชนิดข้อมูลนามธรรมแถวลำดับแถวคอยแถวคอยสองหน้าโครงสร้างข้อมูล

  2. แบบชนิดข้อมูลนามธรรม

รายการโยง

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

ดู กองซ้อนและรายการโยง

สัญกรณ์โอใหญ่

ตัวอย่างของสัญกรณ์โอใหญ่ โดย ''f''(''x'') ∈ O(''g''(''x'')) ซึ่งหมายความว่ามี ''c'' > 0 (เช่น ''c''.

ดู กองซ้อนและสัญกรณ์โอใหญ่

แบบชนิดข้อมูลนามธรรม

แบบชนิดข้อมูลนามธรรม หมายถึงแบบชนิดข้อมูลซึ่งแสดงถึงระบบการจัดการข้อมูล โดยแสดงถึงบริการและกฎเกณฑ์ในการจัดการข้อมูลนั้น ๆ แต่ไม่ได้กล่าวถึงวิธีการสร้างบริการต่าง.

ดู กองซ้อนและแบบชนิดข้อมูลนามธรรม

แถวลำดับ

ในวิทยาการคอมพิวเตอร์ แถวลำดับ (array) คือโครงสร้างข้อมูลที่เป็นรายการอย่างหนึ่ง ข้อมูล (value) จะถูกเก็บบนหน่วยความจำคอมพิวเตอร์ แบบอยู่ติดกันไปเรื่อย ๆ การเข้าถึงข้อมูลสามารถกระทำได้ผ่านดัชนี (index) หรืออาจเรียกว่า คีย์ โดยดัชนีจะเป็นจำนวนเต็มซึ่งบอกถึงลำดับที่ของข้อมูลในแถวลำดับ นอกจากนี้ ค่าของดัชนียังไปจับคู่กับที่อยู่หน่วยความจำ ผ่านสูตรคณิตศาสตร์ ทำให้สามารถเข้าถึงข้อมูลได้ ตัวอย่างเช่นแถวลำดับที่มีข้อมูล 10 ตัว โดยมีดัชนีตั้งแต่ 0 ถึง 9 สมมุติให้ข้อมูลแต่ละตัวใช้หน่วยความจำ 4 ไบต์ และแถวลำดับนี้มีที่อยู่ในหน่วยความจำคือ 2000 จะได้ว่าที่อยู่หน่วยความจำของข้อมูลตัวที่ i คือ 2000 + 4i แถวลำดับยังสามารถขยายมิติไปเป็นสองมิติหรือมากกว่านั้นได้ เนื่องจากรูปแบบของแถวลำดับสองมิติมีรูปร่างเป็นตาราง คล้ายกับเมตริกซ์ บางทีจึงอาจเรียกแถวลำดับสองมิติว่าเมตริกซ์หรือตาราง (สำหรับตารางโดยส่วนมากแล้วจะหมายความถึงตาราง lookup) เช่นเดียวกับแถวลำดับมิติเดียวที่บางครั้งก็อาจเรียกว่าเวกเตอร์หรือทูเพิล แถวลำดับถือได้ว่าเป็นโครงสร้างข้อมูลที่ถือกำเนิดขึ้นพร้อม ๆ กับการเขียนโปรแกรม และสำคัญมากในการเขียนโปรแกรมเช่นเดียวกัน และแทบจะไม่มีโปรแกรมใดเลยที่ไม่ใช้แถวลำดับ โดยแถวลำดับนี้ยังนำไปอิมพลีเมนต์โครงสร้างข้อมูลอื่นอีกมากมายเช่นรายการหรือสายอักขระ แม้แต่หน่วยเก็บข้อมูลที่มีที่อยู่หน่วยความจำก็อาจจะมองหน่วยเก็บข้อมูลเป็นแถวลำดับขนาดยักษ์ก็ได้.

ดู กองซ้อนและแถวลำดับ

แถวคอย

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

ดู กองซ้อนและแถวคอย

แถวคอยสองหน้า

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

ดู กองซ้อนและแถวคอยสองหน้า

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

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

ดู กองซ้อนและโครงสร้างข้อมูล

ดูเพิ่มเติม

แบบชนิดข้อมูลนามธรรม

หรือที่รู้จักกันในชื่อ Stackสแตกสแต็ก