คิวคืออะไร?
หาง เป็นโครงสร้างข้อมูลที่ใช้ในการจัดเก็บและเรียกใช้องค์ประกอบตามลำดับที่กำหนดไว้ล่วงหน้า เป็นโครงสร้างข้อมูลเชิงเส้นที่มีลักษณะคล้ายสแตกและยึดติดกับ FIFO (เข้าก่อนออกก่อน) กฎ. อาจเปรียบได้กับรายการรอหรือแถวที่ให้บริการคนแรกที่มาถึงก่อน ส่วนประกอบที่มีอยู่หลุดจากด้านหน้าของ คิว และองค์ประกอบใหม่จะถูกเพิ่มที่ด้านหลัง
การใช้คิวใน Golang
การดำเนินการของก คิว ใน Go นั้นง่ายและมีประสิทธิภาพและสามารถนำไปใช้ได้โดยใช้สี่วิธีต่อไปนี้
1: ชิ้น
ใน Go, ก ชิ้น เป็นอาร์เรย์แบบไดนามิกที่สามารถเปลี่ยนแปลงขนาดได้ ในการดำเนินการ คิว โดยใช้ก ชิ้น เราสามารถเพิ่มองค์ประกอบที่ด้านหลังของ ชิ้น โดยใช้ฟังก์ชันต่อท้ายในตัวและลบองค์ประกอบออกจากด้านหน้าของ ชิ้น โดยใช้การหั่น
วิธีการนี้ง่ายต่อการสร้างและให้ประสิทธิภาพที่ดีสำหรับการต่อท้ายและการแบ่งส่วนด้วยส่วนย่อยในตัวของ Go อย่างไรก็ตาม วิธีการแบ่งส่วน ซึ่งรวมถึงการคัดลอกองค์ประกอบไปยังอาร์เรย์พื้นฐานใหม่อาจไม่มีประสิทธิภาพหาก คิว ขยายและจำเป็นต้องดำเนินการ dequeuing ซ้ำ
รหัสต่อไปนี้กำหนด คิว การใช้งานโดยใช้สไลซ์ใน Go
แพคเกจหลัก
นำเข้า 'เอฟเอ็มที'
ฟังก์ชั่นหลัก ( ) {
คิว := ทำ ( [ ] อินเตอร์เฟซ { } , 0 )
คิว = ผนวก ( คิว , 'ภาษาอังกฤษ' )
คิว = ผนวก ( คิว , 'ภาษาอูรดู' )
คิว = ผนวก ( คิว , 'คณิตศาสตร์' )
ถ้า เท่านั้น ( คิว ) > 0 {
รายการ := คิว [ 0 ]
คิว = คิว [ 1 : ]
เอฟเอ็มที พิมพ์ ( รายการ )
}
ถ้า เท่านั้น ( คิว ) == 0 {
เอฟเอ็มที พิมพ์ ( 'คิวว่าง' )
} อื่น {
เอฟเอ็มที พิมพ์ ( คิว )
}
}
รหัส Go ด้านบนใช้ชิ้นส่วนเพื่อสร้างตรงไปตรงมา คิว โครงสร้างข้อมูล. เดอะ ผนวก() ฟังก์ชันใช้เพื่อจัดคิวองค์ประกอบใน คิว ชิ้น และการดำเนินการชิ้นที่ลบองค์ประกอบเริ่มต้นจะถูกใช้เพื่อแยกออก กับ fmt.Println() , องค์ประกอบที่ถูกระงับจะถูกพิมพ์ออกมา จากนั้นรหัสจะใช้ เท่านั้น() ฟังก์ชันเพื่อตรวจสอบว่าคิวว่างหรือไม่ และถ้าว่าง จะเขียนว่า “ คิว ว่างเปล่า” โดยใช้ฟังก์ชัน fmt.Println()
เอาต์พุต
2: รายการที่เชื่อมโยง
โหนดที่มีค่าและตัวชี้ไปยังโหนดต่อไปนี้ในรายการประกอบกันเป็นรายการที่เชื่อมโยง ด้วยพอยน์เตอร์สองตัว ตัวหนึ่งชี้ไปด้านหน้า (ส่วนหัว) ของรายการ และอีกตัวชี้ไปด้านหลัง (หาง) เราสามารถใช้ คิว โดยใช้รายการที่เชื่อมโยง การลบรายการออกจากคิว (การต่อคิว) เกี่ยวข้องกับการลบโหนดที่อยู่ด้านหน้าของรายการ ในขณะที่การเพิ่มรายการในคิว (การเข้าคิว) เกี่ยวข้องกับการเพิ่มโหนดใหม่ที่ด้านหลังของรายการ
วิธีนี้ช่วยให้สามารถจัดคิวและจัดคิวได้อย่างมีประสิทธิภาพ เนื่องจากจำเป็นต้องเปลี่ยนเฉพาะพอยน์เตอร์ส่วนหัวและส่วนท้ายเท่านั้น ซึ่งตรงข้ามกับโซลูชันแบบแบ่งส่วนซึ่งองค์ประกอบต่างๆ จะต้องถูกคัดลอก
ใช้รายการที่เชื่อมโยงเพื่อใช้งาน คิว โดยใช้รหัสที่ให้ไว้ด้านล่าง:
แพคเกจหลักนำเข้า 'เอฟเอ็มที'
พิมพ์โหนด โครงสร้าง {
อินเทอร์เฟซค่า { }
ต่อไป * โหนด
}
พิมพ์คิว โครงสร้าง {
ศีรษะ * โหนด
หาง * โหนด
}
ฟังก์ชั่นหลัก ( ) {
คิว := & คิว { ศีรษะ : ไม่มีเลย , หาง : ไม่มีเลย }
โหนดใหม่ := & โหนด { ค่า : 'ภาษาอังกฤษ' , ต่อไป : ไม่มีเลย }
คิว. หาง = โหนดใหม่
คิว. ศีรษะ = โหนดใหม่
โหนดใหม่ = & โหนด { ค่า : 'ภาษาอูรดู' , ต่อไป : ไม่มีเลย }
คิว. หาง . ต่อไป = โหนดใหม่
คิว. หาง = โหนดใหม่
โหนดใหม่ = & โหนด { ค่า : 'คณิตศาสตร์' , ต่อไป : ไม่มีเลย }
คิว. หาง . ต่อไป = โหนดใหม่
คิว. หาง = โหนดใหม่
ถ้า คิว. ศีรษะ != ไม่มีเลย {
รายการ := คิว. ศีรษะ . ค่า
คิว. ศีรษะ = คิว. ศีรษะ . ต่อไป
เอฟเอ็มที พิมพ์ ( รายการ )
}
ถ้า คิว. ศีรษะ == ไม่มีเลย {
เอฟเอ็มที พิมพ์ ( 'คิวว่าง' )
}
}
โครงสร้างโหนดแสดงถึงแต่ละรายการในคิวและมีสองฟิลด์: ฟิลด์ค่าสำหรับเก็บค่าของรายการ และฟิลด์ถัดไปสำหรับชี้ไปยังรายการถัดไปในคิว โครงสร้างคิวใช้คุณสมบัติส่วนหัวและส่วนท้ายเพื่อติดตามส่วนหน้าและส่วนหลังของคิวตามลำดับ เดอะ หางของ รายการแรกระบุโดยคุณสมบัติส่วนหัว ในขณะที่รายการสุดท้ายระบุโดยคุณสมบัติส่วนท้าย
พารามิเตอร์ส่วนหัวและส่วนท้ายถูกตั้งค่าเริ่มต้นเป็น ไม่มีเลย เมื่อใหม่ คิว ถูกสร้างขึ้นในฟังก์ชั่น main() ตัวชี้ส่วนหัวและส่วนท้ายได้รับการอัปเดตเพื่อเพิ่มสามโหนดให้กับ คิว ด้วยค่า “ภาษาอังกฤษ”, “ภาษาอูรดู”, และ “คณิตศาสตร์”. เดอะ 'ภาษาอังกฤษ' รายการแล้ว “ค้างคิว” (ลบออก) จากด้านหน้าของ คิว โดยแสดงค่าและเลื่อนตัวชี้ส่วนหัวไปยังโหนดต่อไปนี้ใน คิว . หลังจาก dequeuing ถ้า head เป็น null หมายความว่าคิวว่างเปล่า และข้อความ “ คิว ว่างเปล่า” ถูกพิมพ์
เอาต์พุต
3: โครงสร้าง
ใน Go คุณสามารถสร้างโครงสร้างข้อมูลแบบกำหนดเองที่เรียกว่า โครงสร้าง เพื่อเป็นตัวแทนของก คิว . นี้ โครงสร้าง สามารถมีฟิลด์เพื่อจัดเก็บ คิว องค์ประกอบและวิธีการเพิ่มและลบรายการ ตรวจสอบว่าคิวว่างหรือไม่ และรับขนาดคิวปัจจุบัน
วิธีการสร้างนี้ คิว in Go นำเสนอการใช้งานที่สะดวกและครอบคลุมด้วยวิธีการใช้งานง่ายที่สามารถขยายและปรับแต่งได้ด้วยคุณสมบัติเพิ่มเติม เป็นวิธีการที่ยืดหยุ่นซึ่งช่วยให้สามารถเปลี่ยนแปลงการดำเนินการหรือเพิ่มความสามารถใหม่ได้ทุกเมื่อที่ต้องการ
การสร้างแบบกำหนดเอง โครงสร้าง ด้วยวิธีการที่เกี่ยวข้องกับการเขียนโค้ดเพิ่มเติมเมื่อเทียบกับอีกสองวิธี ซึ่งอาจเพิ่มความซับซ้อน อย่างไรก็ตาม มันยังให้ความยืดหยุ่นและการควบคุมการใช้งานของ คิว .
ตัวอย่างต่อไปนี้แสดงการสร้างโครงสร้างข้อมูลเพื่อเป็นตัวแทนของ คิว ในไป
แพคเกจหลักนำเข้า 'เอฟเอ็มที'
พิมพ์คิว โครงสร้าง {
รายการ [ ] อินเตอร์เฟซ { }
}
ฟังก์ชั่น ( ถาม * คิว ) เข้าคิว ( อินเทอร์เฟซรายการ { } ) {
ถาม รายการ = ผนวก ( ถาม รายการ , รายการ )
}
ฟังก์ชั่น ( ถาม * คิว ) คิว ( ) อินเตอร์เฟซ { } {
ถ้า เท่านั้น ( ถาม รายการ ) == 0 {
กลับ ไม่มีเลย
}
รายการ := ถาม รายการ [ 0 ]
ถาม รายการ = ถาม รายการ [ 1 : ]
กลับ รายการ
}
ฟังก์ชั่น ( ถาม * คิว ) มันว่างเปล่า ( ) บูล {
กลับ เท่านั้น ( ถาม รายการ ) == 0
}
ฟังก์ชั่น ( ถาม * คิว ) ขนาด ( ) นานาชาติ {
กลับ เท่านั้น ( ถาม รายการ )
}
ฟังก์ชั่นหลัก ( ) {
คิว := & คิว { รายการ : ทำ ( [ ] อินเตอร์เฟซ { } , 0 ) }
คิว. เข้าคิว ( 'ภาษาอังกฤษ' )
คิว. เข้าคิว ( 'ภาษาอูรดู' )
คิว. เข้าคิว ( 'คณิตศาสตร์' )
รายการ := คิว. คิว ( )
เอฟเอ็มที พิมพ์ ( รายการ )
ถ้า คิว. มันว่างเปล่า ( ) {
เอฟเอ็มที พิมพ์ ( 'คิวว่าง' )
}
ขนาด := คิว. ขนาด ( )
เอฟเอ็มที พิมพ์ ( 'ขนาดของคิว:' , ขนาด )
}
ในโค้ดข้างต้น ไอเท็มจะถูกผนวกเข้ากับส่วนของไอเท็มผ่านทาง เข้าคิว() วิธีการซึ่งย้ายไปยังจุดสิ้นสุดของ คิว . กำลังติดตาม เข้าก่อนออกก่อน (FIFO) หลักการ, เดคิว() วิธีการนำรายการออกจากด้านหน้าของ คิว และส่งคืน มีการตรวจสอบความยาวของชิ้นส่วนของรายการเป็นส่วนหนึ่งของ มันว่างเปล่า() วิธีการตรวจสอบเพื่อดูว่า คิว มันว่างเปล่า. โดยการส่งคืนความยาวของชิ้นรายการ, the ขนาด() วิธีการส่งกลับปัจจุบัน หางของ ขนาด.
ฟังก์ชัน main() ใช้ โครงสร้างคิว เพื่อสร้างใหม่ คิว , เพิ่มองค์ประกอบเข้าไป, ลบรายการจากมัน, กำหนดว่า คิว ว่างเปล่าและคำนวณขนาดของมัน
เอาต์พุต
4: ช่อง
ใน Go สามารถใช้ประเภทแชนเนลในตัวเพื่อใช้งาน คิว โครงสร้างข้อมูล. สามารถสร้างแชนเนลด้วยขนาดบัฟเฟอร์เพื่อจำกัดจำนวนองค์ประกอบที่สามารถเข้าคิวในเวลาใดก็ได้ ในการเพิ่มองค์ประกอบให้กับ คิว สามารถส่งไปยังช่องโดยใช้ <- ตัวดำเนินการ ในขณะที่ต้องการลบองค์ประกอบออกจากคิว สามารถรับได้จากช่องสัญญาณโดยใช้ตัวดำเนินการเดียวกัน
วิธีการนี้มีประโยชน์มากในสถานการณ์ที่การเข้าถึงพร้อมกัน คิว จำเป็นเนื่องจากช่องสัญญาณมีความปลอดภัยโดยเนื้อแท้สำหรับการใช้งานพร้อมกัน
สิ่งสำคัญคือต้องจำไว้ว่าช่อง Go ถูกพิมพ์ ซึ่งหมายความว่าคุณสามารถส่งค่าประเภทเฉพาะผ่านช่องสัญญาณได้เท่านั้น และคุณสามารถรับค่าประเภทเดียวกันจากช่องสัญญาณได้เท่านั้น
นี่คือภาพประกอบของวิธีการใช้แชนเนลเพื่อสร้าง คิว โครงสร้างข้อมูลใน Go
แพคเกจหลักนำเข้า (
'เอฟเอ็มที'
'เวลา'
)
พิมพ์คิว โครงสร้าง {
รายการ chaninterface { }
}
funcNewQueue ( ) * คิว {
ถาม := & คิว {
รายการ : ทำ ( อินเตอร์เฟซจัน { } ) ,
}
ไป q รายการกระบวนการ ( )
กลับ ถาม
}
ฟังก์ชั่น ( ถาม * คิว ) รายการกระบวนการ ( ) {
สำหรับ รายการ := ช่วง q รายการ {
ถ้า รายการ == 'ภาษาอังกฤษ' {
เอฟเอ็มที พิมพ์ ( 'ค้างคิว:' , รายการ )
}
}
}
ฟังก์ชั่น ( ถาม * คิว ) เข้าคิว ( อินเทอร์เฟซรายการ { } ) {
ถาม รายการ <- รายการ
}
ฟังก์ชั่นหลัก ( ) {
คิว := คิวใหม่ ( )
คิว. เข้าคิว ( 'ภาษาอังกฤษ' )
คิว. เข้าคิว ( 'ภาษาอูรดู' )
คิว. เข้าคิว ( 'คณิตศาสตร์' )
เวลา . นอน ( 2 * เวลา . ที่สอง )
}
รหัสด้านบนสร้างไฟล์ โครงสร้างคิว ด้วยฟิลด์เดียว รายการ ซึ่งเป็นช่องทางของ อินเตอร์เฟซ{} พิมพ์. เดอะ คิวใหม่() ฟังก์ชันสร้างอินสแตนซ์ใหม่ของ คิว และเริ่มต้นของมัน “รายการ” ฟิลด์ด้วยแชนเนลที่ไม่มีบัฟเฟอร์ใหม่ นอกจากนี้ยังเริ่ม goroutine ใหม่เพื่อประมวลผลรายการที่เพิ่มไปยังคิวโดยใช้ รายการกระบวนการ () การทำงาน. เดอะ รายการกระบวนการ () ฟังก์ชั่นตรวจสอบว่ารายการที่ได้รับเท่ากับ 'ภาษาอังกฤษ' และพิมพ์ข้อความไปยังคอนโซลสำหรับรายการนั้นเท่านั้น เดอะ เข้าคิว() ฟังก์ชันใช้เพื่อเพิ่มรายการใหม่ลงในคิว
เอาต์พุต
บทสรุป
คิวเป็นโครงสร้างข้อมูลที่จำเป็นใน Go ซึ่งใช้เพื่อจัดเก็บและดึงข้อมูลองค์ประกอบตามลำดับที่กำหนด การดำเนินการของก คิว ใน Go นั้นปลอดภัยสำหรับเธรด ทำให้เป็นตัวเลือกที่เหมาะสมที่สุดสำหรับการดำเนินการพร้อมกันในโปรแกรม สามารถนำไปใช้งานได้โดยใช้สไลซ์ รายการที่เชื่อมโยง โครงสร้าง และแชนเนล รายละเอียดทั้งหมดมีอยู่แล้วในหลักเกณฑ์ที่ให้ไว้ข้างต้น