แนะนำ, 2024

ตัวเลือกของบรรณาธิการ

ความแตกต่างระหว่าง Linear Queue และ Circular Queue

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

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

แผนภูมิเปรียบเทียบ

พื้นฐานสำหรับการเปรียบเทียบคิวแบบเชิงเส้นคิวหนังสือเวียน
ขั้นพื้นฐานจัดระเบียบองค์ประกอบข้อมูลและคำสั่งตามลำดับที่เรียงตามลำดับจัดเรียงข้อมูลในรูปแบบวงกลมที่องค์ประกอบสุดท้ายเชื่อมต่อกับองค์ประกอบแรก
ลำดับของการเรียกใช้งาน
งานจะถูกดำเนินการตามลำดับที่วางไว้ก่อนหน้า (FIFO)ลำดับของการดำเนินงานอาจเปลี่ยนแปลง
การแทรกและการลบ
องค์ประกอบใหม่จะถูกเพิ่มจากปลายด้านหลังและลบออกจากด้านหน้าการแทรกและการลบสามารถทำได้ทุกตำแหน่ง
ประสิทธิภาพ
ไม่มีประสิทธิภาพ
ทำงานได้ดีกว่าคิวแบบเส้นตรง

ความหมายของ Linear Queue

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

มีการดำเนินการหลายอย่างในคิว

  • ประการแรกคิวจะเริ่มต้นเป็นศูนย์ (เช่นว่างเปล่า)
  • ตรวจสอบว่าคิวว่างเปล่าหรือไม่
  • ตรวจสอบว่าคิวเต็มหรือไม่
  • การแทรกองค์ประกอบใหม่จากปลายด้านหลัง (Enqueue)
  • การลบองค์ประกอบจากส่วนหน้า (Dequeue)

คิวสามารถดำเนินการในสองมารยาท

  • แบบคงที่ (ใช้อาร์เรย์)
  • แบบไดนามิก (การใช้ตัวชี้)

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

ความหมายของ Circular Queue

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

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

เงื่อนไขบางประการตามด้วยคิวเวียน:

  • ด้านหน้าจะต้องชี้ไปที่องค์ประกอบแรก
  • คิวจะว่างเปล่าถ้า Front = Rear
  • เมื่อมีการเพิ่มองค์ประกอบใหม่คิวจะเพิ่มขึ้นตามค่าหนึ่ง (หลัง = หลัง + 1)
  • เมื่อองค์ประกอบถูกลบออกจากคิวด้านหน้าจะเพิ่มขึ้นทีละหนึ่ง (Front = Front + 1)

ความแตกต่างที่สำคัญระหว่างคิวเชิงเส้นและคิวแบบวงกลม

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

การดำเนินการของคิวแบบเชิงเส้น

อัลกอริทึมที่ระบุด้านล่างแสดงให้เห็นถึงการ เพิ่ม องค์ประกอบในคิว:
คิวต้องการตัวแปรข้อมูลสามตัวซึ่งรวมถึงหนึ่งอาร์เรย์เพื่อเก็บคิวและอื่น ๆ เพื่อเก็บตำแหน่งเริ่มต้นด้านหน้าและด้านหลังนั่นคือ -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; รายการ = คิว [ด้านหน้า]; }} 

ข้อสรุป

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

Top