โครงสร้างข้อมูลและอัลกอริทึม - คิว

Queue เป็นโครงสร้างข้อมูลนามธรรมคล้ายกับ Stacks ซึ่งแตกต่างจากสแต็กคือคิวจะเปิดที่ปลายทั้งสองด้าน ปลายด้านหนึ่งใช้เพื่อแทรกข้อมูล (จัดคิว) เสมอและอีกด้านหนึ่งใช้เพื่อลบข้อมูล (dequeue) คิวเป็นไปตามระเบียบวิธีเข้าก่อน - ออกก่อนกล่าวคือรายการข้อมูลที่เก็บไว้ก่อนจะถูกเข้าถึงก่อน

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

การแทนคิว

ตอนนี้เราเข้าใจแล้วว่าในคิวเราเข้าถึงปลายทั้งสองด้านด้วยเหตุผลที่แตกต่างกัน แผนภาพด้านล่างนี้พยายามอธิบายการแสดงคิวเป็นโครงสร้างข้อมูล -

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

การทำงานขั้นพื้นฐาน

การดำเนินการคิวอาจเกี่ยวข้องกับการกำหนดค่าเริ่มต้นหรือการกำหนดคิวใช้ประโยชน์จากนั้นจึงลบออกจากหน่วยความจำทั้งหมด ที่นี่เราจะพยายามทำความเข้าใจการทำงานพื้นฐานที่เกี่ยวข้องกับคิว -

  • enqueue() - เพิ่ม (จัดเก็บ) รายการในคิว

  • dequeue() - ลบ (เข้าถึง) รายการออกจากคิว

ต้องใช้ฟังก์ชันเพิ่มเติมอีกเล็กน้อยเพื่อให้การทำงานของคิวดังกล่าวข้างต้นมีประสิทธิภาพ เหล่านี้คือ -

  • peek() - รับองค์ประกอบที่ด้านหน้าของคิวโดยไม่ต้องลบออก

  • isfull() - ตรวจสอบว่าคิวเต็มหรือไม่

  • isempty() - ตรวจสอบว่าคิวว่างหรือไม่

ในคิวเราจะจัดคิว (หรือเข้าถึง) ข้อมูลเสมอโดยชี้ด้วย front ตัวชี้และในขณะที่จัดคิว (หรือจัดเก็บ) ข้อมูลในคิวเราใช้ความช่วยเหลือ rear ตัวชี้

ก่อนอื่นเรามาเรียนรู้เกี่ยวกับฟังก์ชันสนับสนุนของคิว -

แอบมอง ()

ฟังก์ชันนี้ช่วยในการดูข้อมูลที่ไฟล์ frontของคิว อัลกอริทึมของฟังก์ชัน peek () มีดังนี้ -

Algorithm

begin procedure peek
   return queue[front]
end procedure

การใช้ฟังก์ชัน peek () ในโปรแกรมภาษาซี -

Example

int peek() {
   return queue[front];
}

เต็ม()

ในขณะที่เราใช้อาร์เรย์มิติเดียวเพื่อใช้งานคิวเราเพียงแค่ตรวจสอบว่าตัวชี้ด้านหลังไปถึงที่ MAXSIZE เพื่อตรวจสอบว่าคิวเต็มแล้ว ในกรณีที่เรารักษาคิวไว้ในรายการที่เชื่อมโยงแบบวงกลมอัลกอริทึมจะแตกต่างกัน อัลกอริทึมของฟังก์ชัน isfull () -

Algorithm

begin procedure isfull

   if rear equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

การใช้ฟังก์ชัน isfull () ในโปรแกรมภาษาซี -

Example

bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

มันว่างเปล่า()

อัลกอริทึมของฟังก์ชัน isempty () -

Algorithm

begin procedure isempty

   if front is less than MIN  OR front is greater than rear
      return true
   else
      return false
   endif
   
end procedure

ถ้าค่าของ front มีค่าน้อยกว่า MIN หรือ 0 จะบอกว่าคิวยังไม่ได้เริ่มต้นดังนั้นจึงว่างเปล่า

นี่คือรหัสโปรแกรม C -

Example

bool isempty() {
   if(front < 0 || front > rear) 
      return true;
   else
      return false;
}

จัดคิวการดำเนินการ

คิวรักษาตัวชี้ข้อมูลสองตัว front และ rear. ดังนั้นการดำเนินการจึงค่อนข้างยากที่จะใช้งานได้ยากกว่าการใช้งานแบบสแต็ก

ควรใช้ขั้นตอนต่อไปนี้เพื่อจัดคิว (แทรก) ข้อมูลลงในคิว -

  • Step 1 - ตรวจสอบว่าคิวเต็มหรือไม่

  • Step 2 - หากคิวเต็มทำให้เกิดข้อผิดพลาดล้นและออก

  • Step 3 - หากคิวไม่เต็มให้เพิ่มขึ้น rear ตัวชี้เพื่อชี้พื้นที่ว่างถัดไป

  • Step 4 - เพิ่มองค์ประกอบข้อมูลไปยังตำแหน่งคิวที่ด้านหลังชี้ไป

  • Step 5 - คืนความสำเร็จ

บางครั้งเรายังตรวจสอบด้วยว่าคิวเริ่มต้นแล้วหรือไม่เพื่อจัดการกับสถานการณ์ที่ไม่คาดฝัน

อัลกอริทึมสำหรับการดำเนินการจัดคิว

procedure enqueue(data)      
   
   if queue is full
      return overflow
   endif
   
   rear ← rear + 1
   queue[rear] ← data
   return true
   
end procedure

การใช้งาน enqueue () ในการเขียนโปรแกรมภาษาซี -

Example

int enqueue(int data)      
   if(isfull())
      return 0;
   
   rear = rear + 1;
   queue[rear] = data;
   
   return 1;
end procedure

การยกเลิกคิว

การเข้าถึงข้อมูลจากคิวเป็นกระบวนการสองงาน - เข้าถึงข้อมูลที่ frontจะชี้และลบข้อมูลหลังจากเข้าถึง ดำเนินการตามขั้นตอนต่อไปนี้dequeue การทำงาน -

  • Step 1 - ตรวจสอบว่าคิวว่างหรือไม่

  • Step 2 - หากคิวว่างให้สร้างข้อผิดพลาดที่น้อยเกินไปและออก

  • Step 3 - หากคิวไม่ว่างให้เข้าถึงข้อมูลที่ front กำลังชี้

  • Step 4 - เพิ่มขึ้น front ตัวชี้เพื่อชี้ไปยังองค์ประกอบข้อมูลที่มีอยู่ถัดไป

  • Step 5 - คืนความสำเร็จ

อัลกอริทึมสำหรับการดำเนินการยกเลิกคิว

procedure dequeue
   
   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front + 1
   return true

end procedure

การใช้งาน dequeue () ในการเขียนโปรแกรมภาษาซี -

Example

int dequeue() {
   if(isempty())
      return 0;

   int data = queue[front];
   front = front + 1;

   return data;
}

สำหรับโปรแกรมคิวที่สมบูรณ์แบบในการเขียนโปรแกรมภาษา C โปรดคลิกที่นี่