โครงสร้างข้อมูลและอัลกอริทึม - คิว
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 โปรดคลิกที่นี่