Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
บทความนี้ไม่มีจาก |
แถวคอย หรือ คิว (อังกฤษ: queue) เป็นแบบชนิดข้อมูลนามธรรมที่มีลักษณะการเรียงลำดับข้อมูล การดำเนินการในแถวคอยจะแบ่งเป็น การเพิ่มข้อมูลไปที่ส่วนหลังสุดของแถวคอย และการดึงข้อมูลออกจากส่วนหน้าสุดของแถวคอย เข้าออกในลักษณะการเข้าก่อนออกก่อน (First In First Out: FIFO) ในโครงสร้างข้อมูลลักษณะเข้าก่อนออกก่อนนี้ ข้อมูลแรกสุดที่ถูกเพิ่มเข้าไปในแถวคอยจะเป็นข้อมูลแรกที่ถูกดึงออก ซึ่งก็เท่ากับว่า ความจำเป็นที่ว่า เมื่อมีข้อมูลหนึ่งถูกเพิ่มเข้ามาแล้ว ข้อมูลที่ถูกเพิ่มก่อนหน้านี้ทั้งหมดจะต้องถูกดึงออกก่อนที่ข้อมูลใหม่จะถูกใช้งาน คล้ายกับการเข้าแถวซื้อของในชีวิตประจำวัน
| แถวคอย | |
|---|---|
 ลักษณะการเข้าก่อนออกก่อนของแถวคอย | |
| ความสำคัญของลำดับ | FIFO (First In First Out) |
| การซ้ำกันของสมาชิก | อนุญาตให้ซ้ำกันได้ |
| เวลาที่ใช้ในการเข้าถึง | ENQUEUE/DEQUEUE |
| โครงสร้างที่นำไปใช้ | แถวคอยสองหน้า, แถวคอยลำดับความสำคัญ |
แถวคอยจัดเป็นวิธีการจัดการเข้า-ออกของข้อมูลอีกแบบหนึ่ง เป็นโครงสร้างข้อมูลที่นำมาใช้ในการทำงานของโปรแกรมคอมพิวเตอร์หลายประการ อาทิแถวคอยในการทำงานของเครือข่าย การออกแบบการทำงานระบบท่อ (pipeline) เป็นต้น
จุดเด่น
แถวคอยสามารถจัดการการเข้า-ออกของข้อมูล ใช้เก็บข้อมูลที่ต้องการจัดเรียงเป็นระบบ โดยพิจารณาข้อมูลตามลำดับ ในทำนองใครถึงก่อนมีสิทธิ์ได้ใช้ก่อน จึงใช้ในการเรียงลำดับในการแบ่งปันทรัพยากรที่มีอยู่จำกัดในการทำงาน เช่น การรอการทำงานของเครื่องพิมพ์ในสำนักงาน เป็นต้น
บริการที่มักจะมี
- เอาข้อมูลใหม่เข้าท้ายแถว (enqueue)
- เอาข้อมูลออกจากหัวแถว (dequeue)
- ดูข้อมูลที่อยู่หัวแถว (peek)
- ทำแถวคอยว่าง และตรวจสอบความว่างของแถว (empty)
ความเร็วที่ใช้ในการทำงาน
การทำงานของแถวคอย ไม่จำเป็นต้องไล่พิจารณาสมาชิกทุกตัว เป็นเพียงแต่การพิจารณาข้อมูลที่เข้าแรกสุดออกจากแถว และเอาข้อมูลใหม่เข้าท้ายแถว การทำงานของแถวคอยจึงมีความเร็วคงที่ (O (1))
วิธีการสร้าง
แถวคอยสามารถสร้างขึ้นด้วยแถวลำดับประกอบกับ ที่เก็บดัชนีของหัวแถวและท้ายแถวสองตัว หรือใช้ (รายการโยงสองชั้นวน)(circular doubly linked list)
แถวคอยแถวลำดับ
สำหรับการใช้แถวลำดับในการทำแถวคอยนั้น (array queue) ตอนเริ่มต้นเราจะให้ดัชนีของหัวแถวและท้ายแถวชี้ที่ศูนย์ เมื่อเข้าแถว (enqueue) ก็จะเก็บข้อมูลตรงดัชนีท้าย พร้อมทั้งเพิ่มค่าดัชนีท้ายแถวขึ้นหนึ่ง (increment) ในทางตรงกันข้ามหากเอาข้อมูลตัวแรกออกจากแถว (dequeue) ก็คืนค่าสมาชิกตัวที่ดัชนีหัวแถวชี้อยู่พร้อมทั้งเพิ่มค่าดัชนีหัวแถวไปอีกหนึ่ง (decrement) หากดัชนีหัวแถวไล่ทับดัชนีท้ายแถวแสดงว่า แถวคอยนั้นว่าง (empty queue) ไม่ควรออกจากแถวอีกเพราะจะทำให้การทำงานรวนได้ (ควรตรวจสอบก่อนออกจากแถว)
เนื่องจากแถวลำดับมีขนาดจำกัดในบางครั้งอาจมีการทำแถวคอยวนรอบ (circular array queue) กล่าวคือบางครั้งแถวคอยอาจมีการเข้าแถวและออกจากแถวสลับกัน ทำให้ดัชนีหัวแถวเลื่อนๆออกไปจนจะตกขอบขวาของแถวลำดับ ทำให้มีเนื้อที่ของแถวลำดับด้านหน้าเหลือไม่ได้ใช้ จึงมีการวนเอาหางแถวมาแทนส่วนหน้าของแถวลำดับ กล่าวคือเมื่อท้ายแถวตกขอบขวาของแถวลำดับ ก็จะมีการเริ่มดัชนีท้ายแถวที่ศูนย์ใหม่และต่อท้ายคิวมาเรื่อยๆ ข้อด้อยของวิธีนี้คือ เมื่อท้ายแถวมาทับหัวแถวอีกครั้งจะตีความไม่ได้ว่าข้อมูลเต็มแถวลำดับหรือว่างกันแน่ จึงอาจใช้ตัวแปรขนาด (size) หรือตัวแปรอื่นๆช่วยในการบอกว่าแถวคอยว่างหรือไม่
แถวคอยรายการโยงสองชั้นวน
สำหรับการใช้(รายการโยงสองชั้นวน)(circular doubly linked list) ในการทำนั้น โดยหัวแถวจะอยู่ที่ปมสุดท้ายนี้ (กล่าวคือเป็นปมก่อนที่จะชี้ปมหัว เพราะว่าเป็นรายการวน) ส่วนท้ายแถวอยู่ที่ปมแรก เมื่อเข้าแถวก็เพิ่มปมใหม่หลังปมหัว เมื่อจะเอาข้อมูลแรกออกจากแถวก็จะเอาข้อมูลก่อนปมหัวออก ก็คือข้อมูลที่เข้าแรกๆสุด เมื่อใดที่รายการว่าง ก็คือตอนที่ปมหัวชี้มาที่ตัวเองนั่นเอง
แถวคอยด้วยกอง
สำหรับ (Implement Queue using Stacks) เป็นการสร้างแถวคอย โดยการต้องสร้างกองขึ้นมาก่อนสองกอง จากนั้นค่อยพุช (push) และป้อบ (pop) ข้อมูลออก ก็จะได้ลำดับข้อมูลที่เหมือนกับแถวคอยเดิม
ดูเพิ่ม
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
bthkhwamniimmikarxangxingcakaehlngthimaidkrunachwyprbprungbthkhwamni odyephimkarxangxingaehlngthimathinaechuxthux enuxkhwamthiimmiaehlngthimaxacthukkhdkhanhruxlbxxk eriynruwacanasaraemaebbnixxkidxyangiraelaemuxir aethwkhxy hrux khiw xngkvs queue epnaebbchnidkhxmulnamthrrmthimilksnakareriyngladbkhxmul kardaeninkarinaethwkhxycaaebngepn karephimkhxmulipthiswnhlngsudkhxngaethwkhxy aelakardungkhxmulxxkcakswnhnasudkhxngaethwkhxy ekhaxxkinlksnakarekhakxnxxkkxn First In First Out FIFO inokhrngsrangkhxmullksnaekhakxnxxkkxnni khxmulaerksudthithukephimekhaipinaethwkhxycaepnkhxmulaerkthithukdungxxk sungkethakbwa khwamcaepnthiwa emuxmikhxmulhnungthukephimekhamaaelw khxmulthithukephimkxnhnanithnghmdcatxngthukdungxxkkxnthikhxmulihmcathukichngan khlaykbkarekhaaethwsuxkhxnginchiwitpracawnaethwkhxylksnakarekhakxnxxkkxnkhxngaethwkhxykhwamsakhykhxngladbFIFO First In First Out karsaknkhxngsmachikxnuyatihsaknidewlathiichinkarekhathungENQUEUE DEQUEUEokhrngsrangthinaipichaethwkhxysxnghna aethwkhxyladbkhwamsakhy aethwkhxycdepnwithikarcdkarekha xxkkhxngkhxmulxikaebbhnung epnokhrngsrangkhxmulthinamaichinkarthangankhxngopraekrmkhxmphiwetxrhlayprakar xathiaethwkhxyinkarthangankhxngekhruxkhay karxxkaebbkarthanganrabbthx pipeline epntncudednaethwkhxysamarthcdkarkarekha xxkkhxngkhxmul ichekbkhxmulthitxngkarcderiyngepnrabb odyphicarnakhxmultamladb inthanxngikhrthungkxnmisiththiidichkxn cungichinkareriyngladbinkaraebngpnthrphyakrthimixyucakdinkarthangan echn karrxkarthangankhxngekhruxngphimphinsankngan epntnbrikarthimkcamiexakhxmulihmekhathayaethw enqueue exakhxmulxxkcakhwaethw dequeue dukhxmulthixyuhwaethw peek thaaethwkhxywang aelatrwcsxbkhwamwangkhxngaethw empty khwamerwthiichinkarthangankarthangankhxngaethwkhxy imcaepntxngilphicarnasmachikthuktw epnephiyngaetkarphicarnakhxmulthiekhaaerksudxxkcakaethw aelaexakhxmulihmekhathayaethw karthangankhxngaethwkhxycungmikhwamerwkhngthi O 1 withikarsrangaethwkhxysamarthsrangkhundwyaethwladbprakxbkb thiekbdchnikhxnghwaethwaelathayaethwsxngtw hruxich raykaroyngsxngchnwn circular doubly linked list aethwkhxyaethwladb sahrbkarichaethwladbinkarthaaethwkhxynn array queue txnerimtneracaihdchnikhxnghwaethwaelathayaethwchithisuny emuxekhaaethw enqueue kcaekbkhxmultrngdchnithay phrxmthngephimkhadchnithayaethwkhunhnung increment inthangtrngknkhamhakexakhxmultwaerkxxkcakaethw dequeue kkhunkhasmachiktwthidchnihwaethwchixyuphrxmthngephimkhadchnihwaethwipxikhnung decrement hakdchnihwaethwilthbdchnithayaethwaesdngwa aethwkhxynnwang empty queue imkhwrxxkcakaethwxikephraacathaihkarthanganrwnid khwrtrwcsxbkxnxxkcakaethw enuxngcakaethwladbmikhnadcakdinbangkhrngxacmikarthaaethwkhxywnrxb circular array queue klawkhuxbangkhrngaethwkhxyxacmikarekhaaethwaelaxxkcakaethwslbkn thaihdchnihwaethweluxnxxkipcncatkkhxbkhwakhxngaethwladb thaihmienuxthikhxngaethwladbdanhnaehluximidich cungmikarwnexahangaethwmaaethnswnhnakhxngaethwladb klawkhuxemuxthayaethwtkkhxbkhwakhxngaethwladb kcamikarerimdchnithayaethwthisunyihmaelatxthaykhiwmaeruxy khxdxykhxngwithinikhux emuxthayaethwmathbhwaethwxikkhrngcatikhwamimidwakhxmuletmaethwladbhruxwangknaen cungxacichtwaeprkhnad size hruxtwaeprxunchwyinkarbxkwaaethwkhxywanghruxim aethwkhxyraykaroyngsxngchnwn sahrbkarichraykaroyngsxngchnwn circular doubly linked list inkarthann odyhwaethwcaxyuthipmsudthayni klawkhuxepnpmkxnthicachipmhw ephraawaepnraykarwn swnthayaethwxyuthipmaerk emuxekhaaethwkephimpmihmhlngpmhw emuxcaexakhxmulaerkxxkcakaethwkcaexakhxmulkxnpmhwxxk kkhuxkhxmulthiekhaaerksud emuxidthiraykarwang kkhuxtxnthipmhwchimathitwexngnnexng aethwkhxydwykxng sahrb Implement Queue using Stacks epnkarsrangaethwkhxy odykartxngsrangkxngkhunmakxnsxngkxng caknnkhxyphuch push aelapxb pop khxmulxxk kcaidladbkhxmulthiehmuxnkbaethwkhxyedimduephimaethwkhxysxnghna aethwkhxyladbkhwamsakhy