คิว
ภาพ แสดงคิวแบบFIFO (เข้าก่อนออกก่อน)
ความซับซ้อนของเวลาในรูปแบบสัญกรณ์บิ๊กโอ การดำเนินการ เฉลี่ย กรณีที่เลวร้ายที่สุด ค้นหา บน)​ บน)​ แทรก O(1) O(1) ลบ O(1) O(1) ความซับซ้อนของพื้นที่ ช่องว่าง บน)​ บน)​

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

• การเพิ่มเข้าไป ในคิว (Enqueue)ซึ่งเป็นการเพิ่มองค์ประกอบหนึ่งรายการเข้าไปที่ท้ายคิว
• Dequeue คือคำสั่งที่ลบองค์ประกอบหนึ่งรายการออกจากด้านหน้าของคิว

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

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

คิวเป็นฟังก์ชันการทำงานในวิทยาการคอมพิวเตอร์การขนส่งและการวิจัยเชิงปฏิบัติการโดยทำหน้าที่จัดเก็บและเก็บรักษาเอนทิตีต่างๆ เช่น ข้อมูล วัตถุ บุคคล หรือเหตุการณ์ เพื่อรอการประมวลผลในภายหลัง ในบริบทเหล่านี้ คิวทำหน้าที่เสมือนบัฟเฟอร์นอกจากนี้ คิวยังถูกนำมาใช้ในการค้นหาแบบกว้าง (breadth-first search ) อีกด้วย

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

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

คิวที่มีขอบเขตจำกัดคือคิวที่มีจำนวนรายการคงที่^{[ 1 ]}

มีวิธีการใช้งานคิว FIFO ที่มีประสิทธิภาพหลายวิธี วิธีการใช้งานที่มีประสิทธิภาพคือวิธีที่สามารถดำเนินการ—การเพิ่มคิวและการนำคิวออก—ได้ภายในเวลา O(1 )

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

คิวอาจถูกนำไปใช้เป็นประเภทข้อมูลแยกต่างหาก หรืออาจถือเป็นกรณีพิเศษของคิวแบบสองด้าน (deque) และไม่ได้นำไปใช้แยกต่างหาก ตัวอย่างเช่นPerlและRubyอนุญาตให้ผลักและดึงอาร์เรย์ออกจากปลายทั้งสองด้าน ดังนั้นจึงสามารถใช้ ฟังก์ชัน pushและshiftเพื่อใส่และดึงรายการออกจากคิว (หรือในทางกลับกัน สามารถใช้unshiftและpop ได้ ) ^{[ 2 ]}แม้ว่าในบางกรณีการดำเนินการเหล่านี้จะไม่มีประสิทธิภาพก็ตาม

ไลบรารีเทมเพลตมาตรฐานของ C++ มีqueueคลาสเทมเพลตที่จำกัดเฉพาะการดำเนินการ push/pop เท่านั้น ตั้งแต่ J2SE 5.0 เป็นต้นมา ไลบรารีของ Java มีQueueอินเทอร์เฟซที่ระบุการดำเนินการคิว โดยคลาสที่ใช้งานได้แก่LinkedListและ (ตั้งแต่ J2SE 1.6) ArrayDequePHP มี คลาส SplQueue และ ไลบรารี ของบุคคลที่สาม เช่นbeanstalk'dและGearman

ระบบคิวแบบง่ายที่เขียนด้วยTypeScript :

คลาสคิว< T > { private items : T [] = [];enqueue ( element : T ) : void { this . items . push ( element ); }dequeue ( ) : T | undefined { return this.items.shift ( ) ; }​isEmpty ( ) : boolean { return this.items.length === 0 ; } }​​​

คิวสามารถนำไปใช้เป็นโครงสร้างข้อมูลเชิงฟังก์ชันล้วนๆ ได้เช่น กัน^{[ 3 ]}มีการใช้งานสองแบบ แบบแรกทำได้เพียงเฉลี่ยต่อการดำเนินการ เท่านั้น นั่นคือเวลาเฉลี่ย คือ แต่การดำเนินการแต่ละครั้งอาจใช้เวลาโดยที่nคือจำนวนองค์ประกอบในคิว การใช้งานแบบที่สองเรียกว่าคิวแบบเรียลไทม์^{[ 4 ]}และช่วยให้คิวคงอยู่ได้ด้วยการดำเนินการในเวลา O(1) ในกรณีที่เลวร้ายที่สุด เป็นการใช้งานที่ซับซ้อนกว่าและต้องใช้ ลิสต์ แบบขี้เกียจพร้อมการจดจำผลลัพธ์ ${\displaystyle O(1)}$${\displaystyle O(1)}$${\displaystyle O(n)}$

ข้อมูลในคิวนี้ถูกเก็บไว้ใน ลิสต์แบบลิงก์เดี่ยวสอง รายการ ชื่อและลิสต์เก็บข้อมูลส่วนหน้าของคิว ส่วนลิสต์เก็บข้อมูลส่วนที่เหลือ (หรือส่วนท้ายของคิว) ในลำดับย้อนกลับการแทรกข้อมูลลงในส่วนหน้าของคิวทำได้ง่ายโดยการเพิ่มโหนดที่หัวของลิสต์และถ้าลิสต์ ไม่ว่างเปล่า การลบข้อมูลออกจากส่วนท้ายของคิวทำได้ง่ายโดยการลบโหนดที่หัวของลิสต์ เมื่อลิสต์ ว่างเปล่าจะถูกสลับลำดับและกำหนดให้กับ ลิสต์ จากนั้นหัวของลิสต์จะถูกลบออก ${\displaystyle f}$${\displaystyle r}$${\displaystyle f}$${\displaystyle r}$${\displaystyle f}$${\displaystyle r}$${\displaystyle r}$${\displaystyle r}$${\displaystyle f}$${\displaystyle r}$${\displaystyle r}$

การแทรก ("enqueue") ใช้เวลาเสมอ การลบ ("dequeue") จะใช้เวลาเมื่อรายการไม่ว่างเปล่า เมื่อ รายการ ว่างเปล่า การดำเนินการย้อนกลับจะใช้ เวลา โดยที่คือจำนวนองค์ประกอบในรายการ แต่เราสามารถกล่าวได้ว่าเป็น เวลา เฉลี่ยเนื่องจากทุกองค์ประกอบในรายการจะต้องถูกแทรก และเราสามารถกำหนดต้นทุนคงที่สำหรับแต่ละองค์ประกอบในการดำเนินการย้อนกลับให้กับเวลาที่แทรกได้ ${\displaystyle O(1)}$${\displaystyle O(1)}$${\displaystyle r}$${\displaystyle r}$${\displaystyle O(n)}$${\displaystyle n}$${\displaystyle f}$${\displaystyle O(1)}$${\displaystyle f}$

ระบบคิวแบบเรียลไทม์ช่วยให้การดำเนินการทั้งหมดเสร็จสิ้นได้ในเวลาที่เหมาะสม โดยไม่ต้องคิดค่าเสื่อมราคา การอธิบายในส่วนนี้จะเป็นเรื่องทางเทคนิค ดังนั้นโปรดจำไว้ว่า สำหรับลิสต์ นั้น n หมายถึงความยาวของลิสต์ NILหมายถึงลิสต์ว่าง และ n ' หมายถึงลิสต์ที่มีหัวเป็นhและท้ายเป็น t${\displaystyle O(1)}$${\displaystyle l}$${\displaystyle |l|}$${\displaystyle \operatorname {CONS} (h,t)}$

โครงสร้างข้อมูลที่ใช้ในการสร้างคิวของเราประกอบด้วยลิสต์แบบเชื่อมโยงเดี่ยว สามรายการ โดยที่fคือส่วนหน้าของคิว และrคือส่วนท้ายของคิวในลำดับย้อนกลับ เงื่อนไขคงที่ของโครงสร้างคือsคือส่วนท้ายของfโดยไม่รวมองค์ประกอบแรก นั่นคือส่วนท้ายของคิวจึงเกือบจะเป็นและการแทรกองค์ประกอบxลงใน ก็เกือบจะเป็นที่เรียกว่าเกือบจะ เพราะในทั้งสองผลลัพธ์นั้น จึงต้องเรียกใช้ ฟังก์ชันเสริมเพื่อให้เงื่อนไขคงที่นั้นเป็นจริง ต้องพิจารณาสองกรณี ขึ้นอยู่กับว่าเป็นลิสต์ว่างหรือไม่ ในกรณีนั้นหรือไม่ นิยามอย่างเป็นทางการคือและโดยที่คือfตามด้วยrที่กลับลำดับ ${\displaystyle (f,r,s)}$${\displaystyle |r|}$${\displaystyle |s|=|f|-|r|}$${\displaystyle (\operatorname {CONS} (x,f),r,s)}$${\displaystyle (f,r,s)}$${\displaystyle (f,r,s)}$${\displaystyle (f,\operatorname {CONS} (x,r),s)}$${\displaystyle |s|=|f|-|r|+1}$${\displaystyle aux}$${\displaystyle s}$${\displaystyle |r|=|f|+1}$${\displaystyle \operatorname {aux} (f,r,\operatorname {Cons} (\_,s))=(f,r,s)}$${\displaystyle \operatorname {aux} (f,r,{\text{NIL}})=(f',{\text{NIL}},f')}$${\displaystyle f'}$

ให้เราเรียกฟังก์ชันที่ส่งคืนfตามด้วยrที่กลับด้าน และสมมติว่าเนื่องจากเป็นกรณีที่ฟังก์ชันนี้ถูกเรียกใช้ กล่าวคือ เรากำหนดฟังก์ชันแบบ lazy ที่รับอินพุตเป็นลิสต์สามรายการ โดยที่และส่งคืนการต่อกันของf , ของrที่กลับด้าน และของaดังนั้นนิยามอุปนัยของ rotate คือและเวลาในการทำงานของมันคือแต่เนื่องจากใช้การประเมินแบบ lazy การคำนวณจึงล่าช้าออกไปจนกว่าผลลัพธ์จะถูกบังคับโดยการคำนวณ ${\displaystyle \operatorname {reverse} (f,r)}$${\displaystyle |r|=|f|+1}$${\displaystyle \operatorname {rotate} (f,r,a)}$${\displaystyle |r|=|f|+1}$${\displaystyle \operatorname {reverse} (f,r)=\operatorname {rotate} (f,r,{\text{NIL}})}$${\displaystyle \operatorname {rotate} ({\text{NIL}},\operatorname {Cons} (y,{\text{NIL}}),a)=\operatorname {Cons} (y,a)}$${\displaystyle \operatorname {rotate} (\operatorname {CONS} (x,f),\operatorname {CONS} (y,r),a)=\operatorname {Cons} (x,\operatorname {rotate} (f,r,\operatorname {CONS} (y,a)))}$${\displaystyle O(r)}$

ลิสต์sในโครงสร้างข้อมูลมีวัตถุประสงค์สองประการ ลิสต์นี้ทำหน้าที่เป็นตัวนับสำหรับf ก็ต่อเมื่อsเป็นลิสต์ว่างเท่านั้น ตัวนับนี้ช่วยให้เรามั่นใจได้ว่าลิสต์ส่วนท้ายจะไม่ยาวกว่าลิสต์ส่วนหน้า นอกจากนี้ การใช้sซึ่งเป็นส่วนท้ายของfจะบังคับให้คำนวณส่วนหนึ่งของลิสต์f (แบบไม่เร่งรีบ) ในระหว่างการดำเนินการเพิ่ม ส่วนท้ายและการแทรกแต่ละครั้งดังนั้น เมื่อ f เป็นค่าว่าง ลิสต์fจะถูกบังคับอย่างสมบูรณ์ หากไม่เป็นเช่นนั้น การแสดงผลภายในของfอาจเป็นการเพิ่มต่อจากการเพิ่มต่อจากการเพิ่มต่อจากการเพิ่มต่อไปเรื่อยๆ และการบังคับจะไม่ใช่การดำเนินการที่ใช้เวลาคงที่อีกต่อไป ${\displaystyle |f|-|r|}$${\displaystyle |f|=|r|}$${\displaystyle |f|=|r|}$

• ลูปเหตุการณ์ - เหตุการณ์ต่างๆ จะถูกจัดเก็บไว้ในคิว
• คิวข้อความ
• คิวลำดับความสำคัญ
• ทฤษฎีการเข้าคิว
• สแต็ก (ชนิดข้อมูลนามธรรม) – สิ่งที่ตรงข้ามกับคิว: LIFO (เข้าหลังออกก่อน)

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับโครงสร้างข้อมูลคิว

• คู่มืออ้างอิงฉบับย่อของ STL
• การใช้งาน Stack, Queue, Deque และ Red-Black Tree ด้วย VBScript