คิว สามารถอธิบายได้ว่าเป็นโครงสร้างข้อมูลเชิงเส้นที่ไม่ใช่แบบดั้งเดิมตามลำดับ FIFO ซึ่งองค์ประกอบข้อมูลจะถูกแทรกจากปลายด้านหนึ่ง (ปลายด้านหลัง) และถูกลบออกจากปลายด้านอื่น (ปลายด้านหน้า) รูปแบบอื่น ๆ ของคิวคือคิวแบบวงกลมคิวที่สิ้นสุดลงสองเท่าและคิวลำดับความสำคัญ
แผนภูมิเปรียบเทียบ
| พื้นฐานสำหรับการเปรียบเทียบ | คิวแบบเชิงเส้น | คิวหนังสือเวียน |
|---|---|---|
| ขั้นพื้นฐาน | จัดระเบียบองค์ประกอบข้อมูลและคำสั่งตามลำดับที่เรียงตามลำดับ | จัดเรียงข้อมูลในรูปแบบวงกลมที่องค์ประกอบสุดท้ายเชื่อมต่อกับองค์ประกอบแรก |
| ลำดับของการเรียกใช้งาน | งานจะถูกดำเนินการตามลำดับที่วางไว้ก่อนหน้า (FIFO) | ลำดับของการดำเนินงานอาจเปลี่ยนแปลง |
| การแทรกและการลบ | องค์ประกอบใหม่จะถูกเพิ่มจากปลายด้านหลังและลบออกจากด้านหน้า | การแทรกและการลบสามารถทำได้ทุกตำแหน่ง |
| ประสิทธิภาพ | ไม่มีประสิทธิภาพ | ทำงานได้ดีกว่าคิวแบบเส้นตรง |
ความหมายของ Linear Queue
คิวแบบเส้นตรง นั้นมีเหตุผลเป็นลำดับ แรกใน รายการที่ได้รับคำสั่งก่อน มันจึงเรียกว่าเชิงเส้นเพราะมันคล้ายกับเส้นตรงที่องค์ประกอบอยู่ในตำแหน่งหนึ่งหลังจากที่อื่น ๆ มันมีคอลเลกชันที่เป็นเนื้อเดียวกันขององค์ประกอบที่องค์ประกอบใหม่จะถูกเพิ่มที่ปลายด้านหนึ่งและลบออกจากปลายอีกด้าน แนวคิดของคิวสามารถเข้าใจได้โดยตัวอย่างของคิวของผู้ชมที่รออยู่ด้านนอกตัวนับตั๋วเพื่อรับตั๋วโรงละคร ในคิวนี้บุคคลเข้าร่วมปลายด้านหลังของคิวเพื่อรับตั๋วและออกตั๋วที่ส่วนหน้าของคิว
มีการดำเนินการหลายอย่างในคิว
- ประการแรกคิวจะเริ่มต้นเป็นศูนย์ (เช่นว่างเปล่า)
- ตรวจสอบว่าคิวว่างเปล่าหรือไม่
- ตรวจสอบว่าคิวเต็มหรือไม่
- การแทรกองค์ประกอบใหม่จากปลายด้านหลัง (Enqueue)
- การลบองค์ประกอบจากส่วนหน้า (Dequeue)
คิวสามารถดำเนินการในสองมารยาท
- แบบคงที่ (ใช้อาร์เรย์)
- แบบไดนามิก (การใช้ตัวชี้)
ข้อ จำกัด ของคิวแบบเส้นตรงคือมันสร้างสถานการณ์สมมติที่ไม่มีองค์ประกอบใหม่สามารถเพิ่มเข้าไปในคิวได้แม้ว่าคิวจะมีช่องว่างก็ตาม สถานการณ์ข้างต้นนี้แสดงให้เห็นในภาพด้านล่าง ที่นี่ด้านหลังชี้ไปที่ดัชนีสุดท้ายในขณะที่กล่องทั้งหมดยังคงว่างเปล่าไม่สามารถเพิ่มองค์ประกอบใหม่ได้
ความหมายของ Circular Queue
คิวแบบวนรอบ เป็นตัวแปรของคิวแบบเส้นตรงซึ่งจะเอาชนะข้อ จำกัด ของคิวแบบเส้นตรงได้อย่างมีประสิทธิภาพ ในคิวแบบวงกลมองค์ประกอบใหม่จะถูกเพิ่มที่ตำแหน่งแรกของคิวหากมีการครอบครองล่าสุดและมีพื้นที่ว่าง เมื่อพูดถึงคิวแบบเส้นตรงการแทรกสามารถทำได้จากปลายด้านหลังและการลบจากปลายด้านหน้าเท่านั้น ในคิวเต็มหลังจากดำเนินการลบแบบต่อเนื่องในคิวเกิดสถานการณ์บางอย่างที่ไม่มีองค์ประกอบใหม่ใด ๆ ที่สามารถเพิ่มได้อีกแม้ว่าจะมีพื้นที่ว่างเนื่องจากสภาพอันเดอร์โฟล์ (หลัง = สูงสุด - 1)
คิวแบบวงกลมเชื่อมต่อปลายทั้งสองด้านผ่านตัวชี้โดยที่องค์ประกอบแรกมาหลังจากองค์ประกอบสุดท้าย นอกจากนี้ยังติดตามด้านหน้าและด้านหลังโดยใช้ตรรกะเพิ่มเติมบางอย่างเพื่อให้สามารถติดตามองค์ประกอบที่จะแทรกและลบ ด้วยวิธีนี้คิวแบบวงกลมจะไม่สร้างเงื่อนไขโอเวอร์โฟลว์จนกว่าคิวจะเต็มตามจริง
เงื่อนไขบางประการตามด้วยคิวเวียน:
- ด้านหน้าจะต้องชี้ไปที่องค์ประกอบแรก
- คิวจะว่างเปล่าถ้า Front = Rear
- เมื่อมีการเพิ่มองค์ประกอบใหม่คิวจะเพิ่มขึ้นตามค่าหนึ่ง (หลัง = หลัง + 1)
- เมื่อองค์ประกอบถูกลบออกจากคิวด้านหน้าจะเพิ่มขึ้นทีละหนึ่ง (Front = Front + 1)
ความแตกต่างที่สำคัญระหว่างคิวเชิงเส้นและคิวแบบวงกลม
- คิวแบบเส้นตรงเป็นรายการที่เรียงลำดับซึ่งองค์ประกอบข้อมูลจะถูกจัดเรียงตามลำดับ ในทางตรงกันข้ามคิวแบบวงกลมจะจัดเก็บข้อมูลในรูปแบบวงกลม
- คิวแบบเส้นตรงตามลำดับ FIFO สำหรับการดำเนินงาน (องค์ประกอบที่เพิ่มในตำแหน่งแรกจะถูกลบในตำแหน่งแรก) ในทางกลับกันในคิวแบบวงกลมลำดับของการดำเนินการที่ดำเนินการกับองค์ประกอบอาจเปลี่ยนแปลงได้
- การแทรกและการลบองค์ประกอบได้รับการแก้ไขในคิวแบบเส้นตรงเช่นการเพิ่มจากส่วนท้ายและการลบจากส่วนหน้า ในทางกลับกันคิววงกลมสามารถแทรกและลบองค์ประกอบออกจากจุดใดก็ได้จนกว่าจะว่าง
- คิวแบบเส้นตรงจะทำให้เปลืองพื้นที่หน่วยความจำในขณะที่คิวแบบวงกลมใช้พื้นที่อย่างมีประสิทธิภาพ
การดำเนินการของคิวแบบเชิงเส้น
อัลกอริทึมที่ระบุด้านล่างแสดงให้เห็นถึงการ เพิ่ม องค์ประกอบในคิว:
คิวต้องการตัวแปรข้อมูลสามตัวซึ่งรวมถึงหนึ่งอาร์เรย์เพื่อเก็บคิวและอื่น ๆ เพื่อเก็บตำแหน่งเริ่มต้นด้านหน้าและด้านหลังนั่นคือ -1
insert (item, queue, n, rear) {if (rear == n) จากนั้นพิมพ์ "queue overflow"; อื่น {หลัง = หลัง + 1; คิว [หลัง] = รายการ; }} อัลกอริทึมที่ระบุด้านล่างแสดงให้เห็นถึงการ ลบ องค์ประกอบในคิว:
delete_circular (รายการ, คิว, ด้านหลัง, ด้านหน้า) {ถ้า (หลัง == ด้านหน้า) จากนั้นพิมพ์ "คิว underflow"; อื่น {front = front + 1; รายการ = คิว [ด้านหน้า]; }} การดำเนินงานของคิวแบบวงกลม
อัลกอริทึมในการตีความการ เพิ่ม องค์ประกอบในคิววงกลม:
insert_circular (รายการ, คิว, ด้านหลัง, ด้านหน้า) {หลัง = (หลัง + 1) mod n; ถ้า (ด้านหน้า == ด้านหลัง) จากนั้นพิมพ์ "คิวเต็ม"; อื่น {คิว [หลัง] = รายการ; }} อัลกอริทึมอธิบายการ ลบ องค์ประกอบในคิววงกลม:
delete_circular (รายการ, คิว, ด้านหลัง, ด้านหน้า) {ถ้า (ด้านหน้า == ด้านหลัง) จากนั้นพิมพ์ ("คิวว่างเปล่า"); อื่น {front = front + 1; รายการ = คิว [ด้านหน้า]; }} ข้อสรุป
คิวแบบเชิงเส้นไม่มีประสิทธิภาพในบางกรณีที่จำเป็นต้องมีองค์ประกอบเพื่อเลื่อนไปยังพื้นที่ว่างเพื่อดำเนินการแทรก นั่นคือเหตุผลที่ทำให้เสียพื้นที่เก็บข้อมูลในขณะที่คิวแบบวงกลมใช้พื้นที่เก็บข้อมูลอย่างเหมาะสมเนื่องจากองค์ประกอบจะถูกเพิ่มในตำแหน่งใด ๆ หากมีพื้นที่ว่าง
