ตัวอย่างโดยละเอียดพร้อมรูปภาพและข้อความเพื่อใช้คิวใน JavaScript

คำแนะนำที่เกี่ยวข้อง: บทช่วยสอน JavaScript

1. โครงสร้างข้อมูลคิว

• คิวเป็นโครงสร้างข้อมูลประเภท "เข้าก่อนออกก่อน" (FIFO) รายการแรกที่เข้าคิว (อินพุต) คือรายการแรกที่แยกออกจากคิว (เอาต์พุต)
• คิวมี 2 พอยน์เตอร์: หัวและส่วนท้าย รายการที่อยู่ในคิวที่เก่าแก่ที่สุดในคิวจะอยู่ที่ส่วนหัว และรายการที่อยู่ในคิวใหม่ล่าสุดจะอยู่ที่ส่วนท้าย
• คิวก็เหมือนการรอคิวในรถไฟใต้ดิน ผู้โดยสารใกล้ประตูจะอยู่หัวคิว และผู้โดยสารที่เพิ่งเข้าคิวจะอยู่ด้านหลังคิว

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

2. การดำเนินการบนคิว

คิวรองรับการดำเนินการหลัก 2 ประการ: เข้าคิวและถอนคิว นอกจากนี้ คุณอาจพบว่ามีประโยชน์ในการดำเนินการดูและความยาวในคิว

• การดำเนินการเข้าคิว <br/>การดำเนินการเข้าคิวคือการแทรกรายการที่จุดสิ้นสุดของคิว และรายการที่แทรกจะกลายเป็นจุดสิ้นสุดของคิว

การดำเนินการจัดคิวในรูปด้านบนจะแทรกรายการที่ 8 ไปที่จุดสิ้นสุด และ 8 จะกลายเป็นจุดสิ้นสุดของคิว

Queue.enqueue(8);

• การดำเนินการ Dequeue <br/> การดำเนินการ Dequeue คือการแตกรายการที่จุดเริ่มต้นของคิวและรายการถัดไปในคิวจะกลายเป็นรายการหลัก

ในภาพด้านบน การดำเนินการถอนคิวจะส่งคืนและลบรายการที่ 7 ออกจากคิว หลังจากถอนคิวแล้ว รายการที่ 2 จะกลายเป็นรายการหลักใหม่

Queue.dequeue(); // => 7

• การดำเนินการตรวจสอบ <br/> การดำเนินการตรวจสอบจะอ่านจุดเริ่มต้นของคิวโดยไม่ต้องเปลี่ยนคิว

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

Queue.peek(); // => 7

• ความยาวคิว การดำเนินการตามความยาวจะคำนวณจำนวนรายการในคิว

คิวในภาพมี 4 รายการ คือ 4, 6, 2 และ 7 ส่งผลให้คิวยาวเป็น 4

Queue.length; // => 4

• Queue Operation Time Complexity สิ่งสำคัญสำหรับการดำเนินการคิวทั้งหมด (enqueue, dequeue, view และ length) คือการดำเนินการทั้งหมดเหล่านี้จะต้องดำเนินการในเวลาที่กำหนด O(1)

เวลาคงที่ O(1) หมายความว่าไม่ว่าคิวจะมีขนาดเท่าใดก็ตาม (สามารถมีได้ 10 หรือ 1 ล้านรายการ): การดำเนินการเข้าคิว, ดีคิว, การดู และความยาวจะต้องดำเนินการพร้อมกันทั้งหมด

3. การใช้คิวใน JavaScript

มาดูการใช้งานที่เป็นไปได้ของโครงสร้างข้อมูลคิวในขณะที่ยังคงรักษาข้อกำหนดที่ว่าการดำเนินการทั้งหมดจะต้องดำเนินการในเวลาคงที่ O(1)

คิวคลาส {
  ตัวสร้าง () {
    นี่.รายการ = {};
    นี้.headIndex = 0;
    นี่.tailIndex = 0;
  -

  เข้าคิว (รายการ) {
    this.items[this.tailIndex] = รายการ;
    this.tailIndex++;
  -

  ยกเลิกคิว() {
    รายการ const = this.items [this.headIndex];
    ลบ this.items[this.headIndex];
    นี้.headIndex++;
    คืนสินค้า;
  -

  แอบมอง() {
    กลับ this.items[this.headIndex];
  -

  รับความยาว () {
    กลับ this.tailIndex - this.headIndex;
  -
-

คิว const = คิวใหม่ ();

คิว.เข้าคิว(7);
คิว.เข้าคิว(2);
คิว.เข้าคิว(6);
คิว.เข้าคิว(4);

Queue.dequeue(); // => 7

Queue.peek(); // => 2

Queue.length; // => 3

const Queue = new Queue() คือวิธีสร้างอินสแตนซ์ของคิว

เรียกใช้เมธอด Queu.enqueue(7) เพื่อใส่รายการที่ 7 ลงในคิว

Queue.dequeue() ลบรายการส่วนหัวออกจากคิว ในขณะที่ Queu.peek() เป็นเพียงการดูจากจุดเริ่มต้น

สุดท้าย Queu.length จะแสดงจำนวนรายการที่เหลืออยู่ในคิว

เกี่ยวกับการนำไปใช้งาน: ภายในคลาส Queue วัตถุธรรมดา this.items จะเก็บรายการไว้ในคิวด้วยดัชนีตัวเลข ดัชนีของรายการส่วนหัวถูกติดตามโดย this.headIndex และดัชนีของรายการส่วนท้ายถูกติดตามโดย this.tailIndex

• ความซับซ้อนของวิธีคิว

วิธีการคิว(), dequeue(), peek() และความยาว() ของคลาสคิวใช้เฉพาะ:

การเข้าถึงแอตทริบิวต์ (เช่น this.items[this.headIndex]),

หรือดำเนินการทางคณิตศาสตร์ (เช่น this.headIndex++)

ดังนั้นความซับซ้อนของเวลาของวิธีการเหล่านี้จึงเป็นค่าคงที่เวลา O(1)

4. สรุป

โครงสร้างข้อมูลคิวเป็นแบบ "เข้าก่อนออกก่อน" (FIFO): รายการแรกสุดที่จะจัดคิวคือรายการแรกสุดที่จะจัดคิว

คิวมีการดำเนินการหลัก 2 ประการ: เข้าคิวและถอนคิว นอกจากนี้ คิวสามารถมีการดำเนินการเสริม เช่น มุมมองและความยาว

การดำเนินการคิวทั้งหมดจะต้องดำเนินการ O(1) ในเวลาคงที่

คำแนะนำที่เกี่ยวข้อง: บทช่วยสอนการเรียนรู้ JavaScript

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