บทนำ
คิวคือคอลเลกชั่นของไอเท็ม โดยที่ไอเท็มแรกที่เพิ่มเข้าไปในรายการ จะต้องเป็นไอเท็มแรกที่จะลบออกในลำดับถัดไป เมื่อมีการเพิ่มไอเท็มในคอลเลกชั่น มันมีขนาดโตขึ้น กล่าวคือ มีความยาวเพิ่มขึ้น เมื่อใดก็ตามที่จะลบรายการใด ๆ รายการนั้นจะต้องเป็นรายการแรกที่เพิ่มเข้ามา หากรายการถูกลบอย่างต่อเนื่อง รายการถัดไปจะถูกลบคือรายการที่สอง ที่สามจะถูกลบออกหลังจากนั้นเป็นต้น
หลังจากลบรายการแรกของรายการดั้งเดิม รายการที่สองจะกลายเป็นรายการแรก หลังจากที่รายการที่สองถูกลบ รายการที่สามจะกลายเป็นรายการแรก และอื่นๆ
ตัวอย่างในชีวิตจริงที่ดีของคิวคือเวลาที่คนเข้าแถวรอรับบริการหรือคิวรอคิว คนแรกเสิร์ฟก่อนคนสุดท้าย อย่างไรก็ตาม คิวที่กล่าวถึงในบทช่วยสอนนี้คือ คิวซอฟต์แวร์ ตามที่ออกแบบใน C++
FIFO
FIFO ย่อมาจาก First-In, First-Out เป็นอีกวิธีหนึ่งในการชื่นชมคิว ซึ่งหมายความว่า รายการแรกที่เข้าสู่รายการ คือรายการแรกที่จะลบ เมื่อใดก็ตามที่มีการลบ จุดเริ่มต้นของรายการเรียกว่าส่วนหัวหรือส่วนหน้า ส่วนท้ายของรายการเรียกว่าส่วนหลังหรือส่วนท้าย
ปฏิบัติการที่จำเป็น
คิวซอฟต์แวร์ต้องมีการดำเนินการต่อไปนี้เป็นอย่างน้อย:
ดัน
การดำเนินการนี้ เพิ่มองค์ประกอบใหม่ที่ด้านหลังของคิว การดำเนินการนี้เรียกอย่างเป็นทางการว่าเข้าคิว
กะ
การดำเนินการนี้จะลบองค์ประกอบแรกของคิว และองค์ประกอบที่สองจะกลายเป็นองค์ประกอบแรกใหม่ การดำเนินการนี้เรียกอย่างเป็นทางการว่า dequeue เรียกว่าป๊อปใน C ++
บทความนี้อธิบายวิธีการใช้โครงสร้างข้อมูลคิว C++ คุณควรทราบพอยน์เตอร์และการอ้างอิง C++ เพื่อทำความเข้าใจส่วนที่เหลือของบทความนี้
คลาสและวัตถุ
คลาสคือชุดของตัวแปรและฟังก์ชันที่ทำงานร่วมกัน โดยที่ตัวแปรไม่ได้กำหนดค่าไว้ เมื่อกำหนดค่าให้กับตัวแปร คลาสจะกลายเป็นวัตถุ ค่าต่าง ๆ ที่มอบให้กับคลาสเดียวกันส่งผลให้เกิดอ็อบเจกต์ต่างกัน กล่าวคือ วัตถุต่าง ๆ เป็นคลาสเดียวกันที่มีค่าต่างกัน กล่าวกันว่าการสร้างวัตถุจากคลาสนั้นเป็นการสร้างอินสแตนซ์ของวัตถุ
ชื่อคิวเป็นคลาส อ็อบเจ็กต์ที่สร้างจากคลาสคิวมีชื่อโปรแกรมเมอร์ที่เลือกไว้
จำเป็นต้องใช้ฟังก์ชันที่เป็นของคลาสเพื่อสร้างอินสแตนซ์ของอ็อบเจ็กต์จากคลาส ใน C++ ฟังก์ชันนั้นมีชื่อเดียวกับชื่อของคลาส ออบเจ็กต์ที่สร้าง (ทันที) จากคลาสมีชื่อเรียกต่างกันโดยโปรแกรมเมอร์
การสร้างวัตถุจากคลาสหมายถึงการสร้างวัตถุ มันยังหมายถึงการสร้างอินสแตนซ์
โปรแกรม C++ ซึ่งใช้คลาสคิว เริ่มต้นด้วยบรรทัดต่อไปนี้ที่ด้านบนของไฟล์:
#รวม#รวม
ใช้เนมสเปซ std;
บรรทัดแรกเป็นอินพุต/เอาต์พุต บรรทัดที่สองคือการอนุญาตให้โปรแกรมใช้คุณลักษณะทั้งหมดของคลาสคิว บรรทัดที่สามอนุญาตให้โปรแกรมใช้ชื่อในเนมสเปซมาตรฐาน
โอเวอร์โหลดฟังก์ชัน
เมื่อลายเซ็นของฟังก์ชันที่แตกต่างกันตั้งแต่สองรายการขึ้นไปมีชื่อเหมือนกัน แสดงว่าชื่อนั้นโอเวอร์โหลด เมื่อฟังก์ชันหนึ่งถูกเรียก จำนวนและประเภทของอาร์กิวเมนต์ เป็นตัวกำหนดว่าฟังก์ชันใดที่จะดำเนินการจริง
การก่อสร้าง
คิว<พิมพ์>ชื่อ()การประกาศต่อไปนี้สร้างอินสแตนซ์ของคิวที่ชื่อ que ของชนิด int
คิว<int>นั่น;คิวว่าง การประกาศเริ่มต้นด้วยคำสงวน คิว ตามด้วยวงเล็บมุมด้วยชนิดข้อมูล จากนั้นคุณมีชื่อโปรแกรมเมอร์สำหรับคิว
การสร้างด้วย Initializer List
คำจำกัดความต่อไปนี้แสดงวิธีสร้างคิวด้วยรายการตัวเริ่มต้น:
คิว<ลอย>นั่น({1.1, 2.2, 3.3, 4.4});การทำลายคิว
หากต้องการทำลายคิว ก็ปล่อยให้มันอยู่นอกขอบเขต
การเข้าถึงองค์ประกอบคิว
ดัน(ค่า)
คิวคือรายการเข้าก่อนออกก่อน ดังนั้นแต่ละค่าจะถูกเพิ่มจากด้านหลัง ส่วนรหัสต่อไปนี้สร้างคิวว่าง หลังจากนั้นเพิ่มค่าทศนิยมห้าค่าจากด้านหลัง:
คิว<ลอย>นั่น;นั่น.ดัน(1.1);
นั่น.ดัน(2.2);
นั่น.ดัน(3.3);
นั่น.ดัน(4.4);
นั่น.ดัน(5.5);
ขนาด() const
ส่งคืนจำนวนองค์ประกอบในคิว รหัสต่อไปนี้แสดงให้เห็น:
คิว<ลอย>นั่น;นั่น.ดัน(1.1);นั่น.ดัน(2.2);นั่น.ดัน(3.3);นั่น.ดัน(4.4);นั่น.ดัน(5.5);
ค่าใช้จ่าย<<นั่น.ขนาด() << 'NS';
ผลลัพธ์คือ 5
ด้านหน้า()
ส่งคืนการอ้างอิงไปยังองค์ประกอบแรกของคิว โดยไม่ต้องลบองค์ประกอบ ผลลัพธ์ของรหัสต่อไปนี้คือ 1.1
คิว<ลอย>นั่น;นั่น.ดัน(1.1);นั่น.ดัน(2.2);นั่น.ดัน(3.3);นั่น.ดัน(4.4);นั่น.ดัน(5.5);
ค่าใช้จ่าย<<นั่น.ด้านหน้า() << 'NS';
องค์ประกอบจะไม่ถูกลบออกจากคิว
front() const
เมื่อการสร้างคิวนำหน้าด้วย const นิพจน์ front() const จะถูกดำเนินการแทน front() มันถูกใช้ในรหัสต่อไปนี้เช่น
constคิว<ลอย>นั่น({1.1, 2.2, 3.3, 4.4, 5.5});ค่าใช้จ่าย<<นั่น.ด้านหน้า() << 'NS';
การอ้างอิงคงที่จะถูกส่งกลับ องค์ประกอบไม่ถูกลบออกจากเวกเตอร์ องค์ประกอบของคิวไม่สามารถเปลี่ยนแปลงได้
กลับ()
ส่งคืนการอ้างอิงไปยังองค์ประกอบสุดท้ายของคิว โดยไม่ต้องลบองค์ประกอบ ผลลัพธ์ของรหัสต่อไปนี้คือ 5.5
คิว<ลอย>นั่น;นั่น.ดัน(1.1);นั่น.ดัน(2.2);นั่น.ดัน(3.3);นั่น.ดัน(4.4);นั่น.ดัน(5.5);
ค่าใช้จ่าย<<นั่น.กลับ() << 'NS';
back() const
เมื่อการสร้างคิวนำหน้าด้วย const นิพจน์ back() const จะถูกดำเนินการแทน back() มันถูกใช้ในรหัสต่อไปนี้เช่น
constคิว<ลอย>นั่น({1.1, 2.2, 3.3, 4.4, 5.5});ค่าใช้จ่าย<<นั่น.กลับ() << 'NS';
การอ้างอิงคงที่จะถูกส่งกลับ องค์ประกอบจะไม่ถูกลบออกจากคิว ด้วยเงื่อนไขก่อนหน้าสำหรับการสร้างคิว อิลิเมนต์ในคิวไม่สามารถเปลี่ยนแปลงได้
ความจุของคิว
ขนาด() const
- ดูด้านบน
ว่างเปล่า() const
ค่านี้จะคืนค่า 1 สำหรับค่า true หากไม่มีองค์ประกอบในคิว หรือ 0 สำหรับค่า false หากคิวว่าง รหัสต่อไปนี้แสดงให้เห็นสิ่งนี้:
คิว<ลอย>that1({1.1, 2.2, 3.3, 4.4, 5.5});ค่าใช้จ่าย<<นั่น1.ว่างเปล่า() << 'NS';
คิว<ลอย>that2;
ค่าใช้จ่าย<<นั่น2.ว่างเปล่า() << 'NS';
ผลลัพธ์คือ:
01
ตัวปรับเปลี่ยนคิว
โผล่ ()
คิวคือ FIFO ดังนั้นองค์ประกอบใด ๆ ที่ต้องถูกลบจะต้องถูกลบออกจากด้านบน (ส่วนหัว) ของคิว ฟังก์ชันสมาชิกนี้จะลบองค์ประกอบแรกโดยไม่ส่งคืน รหัสต่อไปนี้แสดงให้เห็นสิ่งนี้:
คิว<ลอย>นั่น({1.1, 2.2, 3.3, 4.4, 5.5});ค่าใช้จ่าย<<นั่น.ด้านหน้า() << 'NS';
นั่น.โผล่();
ค่าใช้จ่าย<<นั่น.ขนาด() << 'NS';
ผลลัพธ์คือ:
1.14
a.swap(b)
สามารถเปลี่ยนคิวได้ 2 คิว ดังที่แสดงไว้ในส่วนโค้ดนี้:
คิว<ลอย>that1({1.1, 2.2, 3.3, 4.4, 5.5});คิว<ลอย>that2({10, ยี่สิบ});
นั่น1.แลกเปลี่ยน(that2);
ค่าใช้จ่าย<< 'องค์ประกอบแรกและขนาดของ que1:
'<<นั่น1.ด้านหน้า() <<','<<นั่น1.ขนาด() << 'NS';
ค่าใช้จ่าย<< 'องค์ประกอบแรกและขนาดของ que2'<<
นั่น2.ด้านหน้า() <<','<<นั่น2.ขนาด() << 'NS';
ผลลัพธ์คือ:
องค์ประกอบแรกและขนาดของ que1: 10, 2
องค์ประกอบแรกและขนาดของ que2: 1.1, 5
โปรดทราบว่าความยาวของคิวจะเพิ่มขึ้นหากจำเป็น นอกจากนี้ ค่าที่ไม่มีการแทนที่จะถูกแทนที่ด้วยค่าดีฟอลต์บางค่า ชนิดข้อมูลต้องเป็นชนิดเดียวกัน
ความเท่าเทียมกันและตัวดำเนินการเชิงสัมพันธ์สำหรับคิว
สำหรับอักขระธรรมดาในภาษา C++ เรียงลำดับจากน้อยไปมาก ตัวเลขจะมาก่อนอักษรตัวพิมพ์ใหญ่ ซึ่งมาก่อนอักษรตัวพิมพ์เล็ก อักขระช่องว่างมาก่อนศูนย์และทั้งหมด
ตัวดำเนินการความเท่าเทียม
ส่งกลับ 1 สำหรับจริงและ 0 สำหรับเท็จ
ตัวดำเนินการ ==
คืนค่า 1 หากคิวทั้งสองมีขนาดเท่ากันและองค์ประกอบที่เกี่ยวข้องเท่ากัน มิฉะนั้นจะคืนค่า 0 ตัวอย่าง:
คิว<const char*>that1({'ใจดี', 'อื่น ๆ อีก'});คิว<const char*>that2({'ชั่วร้าย'});
intหนึ่ง=that1==that2;
ค่าใช้จ่าย<<หนึ่ง<< 'NS';
ผลลัพธ์คือ: 0
!= โอเปอเรเตอร์
- ตรงข้ามกับด้านบน ตัวอย่าง:
คิว<const char*>that1({'ใจดี', 'อื่น ๆ อีก'});คิว<const char*>that2({'ชั่วร้าย'});
intหนึ่ง=that1! =that2;
ค่าใช้จ่าย<<หนึ่ง<< 'NS';
ผลลัพธ์คือ: 1
ผู้ประกอบการสัมพันธ์
ส่งกลับ 1 สำหรับจริงและ 0 สำหรับเท็จ
NS
คืนค่า 1 หากคิวแรกเป็นเซตย่อยเริ่มต้นของคิวที่สอง โดยองค์ประกอบของสองส่วนที่เท่ากันจะเหมือนกันและอยู่ในลำดับเดียวกัน หากทั้งสองคิวมีขนาดเท่ากันหรือมีขนาดต่างกัน และย้ายจากซ้ายไปขวา พบองค์ประกอบในคิวแรกซึ่งน้อยกว่าองค์ประกอบที่สอดคล้องกันในคิวที่สอง ดังนั้น 1 จะยังคงถูกส่งกลับ มิฉะนั้นจะส่งคืน 0 ตัวอย่าง:
คิว<const char*>that1({'ใจดี', 'อื่น ๆ อีก'});คิว<const char*>that2({'ชั่วร้าย'});
intหนึ่ง=that1<that2;
ค่าใช้จ่าย<<หนึ่ง<< 'NS';
ผลลัพธ์คือ 1 ที่ > โอเปอเรเตอร์ - ตรงข้ามกับด้านบน ตัวอย่าง: เอาท์พุต: 0 NS<= Operator - เหมือนกับ เอาท์พุต: 1 >= โอเปอเรเตอร์ - ตรงข้ามกับด้านบน ตัวอย่าง: เอาท์พุต: 0 ค่าเป็นประเภทข้อมูล เนื่องจากวัตถุที่สร้างอินสแตนซ์คือคลาส การสร้างคิวยังสามารถยอมรับคลาสเป็นชนิดข้อมูลได้ โปรแกรมต่อไปนี้แสดงให้เห็นสิ่งนี้: ผลลัพธ์คือ 5 รายการคิวในทางเทคนิคเรียกว่ารายการที่เชื่อมโยง รายการที่เชื่อมโยงสำหรับคิวมีสองประเภท: รายการที่เชื่อมโยงแบบเดี่ยวและรายการที่เชื่อมโยงแบบทวีคูณ องค์ประกอบรายการที่เชื่อมโยงเพียงอย่างเดียวสามารถนำไปใช้โดยโครงสร้างของสมาชิกสองคน สมาชิกคนหนึ่งถือตัวชี้ไปยังองค์ประกอบถัดไป และสมาชิกอีกคนถือ datum (เอกพจน์สำหรับข้อมูล) องค์ประกอบรายการที่เชื่อมโยงแบบทวีคูณสามารถนำไปใช้โดยโครงสร้างของสมาชิกสามคน สมาชิกตรงกลางถือ datum ในขณะที่สมาชิกที่หนึ่งและสามถือตัวชี้ไปยังองค์ประกอบที่อยู่ติดกัน คิวเป็นโครงสร้างข้อมูลเข้าก่อนออกก่อน มีบางสถานการณ์ในการคำนวณเมื่อข้อมูลมาถึงในรูปแบบของคิว ซึ่งจำเป็นต้องมีพฤติกรรมเข้าก่อนออกก่อน ทรัพยากรในคอมพิวเตอร์คือส่วนประกอบทางกายภาพหรือเสมือนของความพร้อมใช้งานที่จำกัด ได้แก่ CPU การ์ดแสดงผล ฮาร์ดไดรฟ์ และหน่วยความจำ การแบ่งปันทรัพยากรดังกล่าวจำเป็นต้องมีคิว อุปกรณ์ต่อพ่วงคอมพิวเตอร์จำเป็นต้องขัดจังหวะคอมพิวเตอร์เป็นครั้งคราว การขัดจังหวะต้องได้รับการจัดการในลักษณะเดียวกับที่พวกเขามาถึง สิ่งนี้ต้องการคิว สามารถใช้คิวได้ ตัวอย่างเช่น เพื่อจัดการไฟล์แอปพลิเคชันสำหรับงาน หากไฟล์ถูกจัดเก็บไว้ในคอมพิวเตอร์ คิวเป็นโครงสร้างข้อมูลรายการ ซึ่งเป็นรายการที่เชื่อมโยงแบบเดี่ยวหรือรายการที่เชื่อมโยงแบบทวีคูณ ตามกฎแล้ว องค์ประกอบแรกที่เข้าสู่รายการคือองค์ประกอบแรกที่ออกมา C++ จัดเตรียมโครงสร้างข้อมูลคิวในไลบรารีมาตรฐาน หมวดหมู่ของฟังก์ชันสมาชิกและตัวดำเนินการที่พร้อมใช้งานสำหรับโครงสร้างนี้ ได้แก่ การสร้างคิว การเข้าถึงองค์ประกอบคิว ความจุของคิว ตัวแก้ไขคิว และตัวดำเนินการคิวโอเวอร์โหลด โครงสร้างข้อมูลคิวอย่างน้อยต้องมีฟังก์ชัน push() และ pop() ของสมาชิก push() หมายถึง การส่งองค์ประกอบใหม่ที่ด้านหลังของคิว และ pop() หมายถึงการลบองค์ประกอบที่อยู่ด้านหน้าของคิว ขออภัย ใน C++ ฟังก์ชันเหล่านี้ไม่คืนค่าที่ผลักหรือแตก ดังนั้น หากต้องการทราบองค์ประกอบสุดท้ายก่อนที่จะกด จำเป็นต้องใช้ฟังก์ชัน extra back() และเพื่อให้ทราบองค์ประกอบแรกก่อนที่จะ popping จำเป็นต้องใช้ฟังก์ชัน front() พิเศษ ค่าเป็นประเภทข้อมูล เนื่องจากวัตถุที่สร้างอินสแตนซ์คือคลาส ดังนั้น คลาสเฉพาะสามารถใช้เป็นชนิดข้อมูลสำหรับการสร้างอินสแตนซ์เท็มเพลตคิวได้ วัตถุที่แตกต่างกันสำหรับชั้นเรียนจะกลายเป็นเหมือนค่าที่แตกต่างกันสำหรับชั้นเรียน คิวมีแอปพลิเคชันบนคอมพิวเตอร์ สามารถใช้ ตัวอย่างเช่น เพื่อจัดการไฟล์แอปพลิเคชันสำหรับงาน หากไฟล์ถูกจัดเก็บไว้ในคอมพิวเตอร์ คริส
คิว<const char*>that2({'ชั่วร้าย'});
intหนึ่ง=that1>that2;
ค่าใช้จ่าย<<หนึ่ง<< 'NS';
คิว<const char*>that2({'ชั่วร้าย'});
intหนึ่ง=that1<=that2;
ค่าใช้จ่าย<<หนึ่ง<< 'NS';
คิว<const char*>that2({'ชั่วร้าย'});
intหนึ่ง=that1> =that2;
ค่าใช้จ่าย<<หนึ่ง<< 'NS'; คลาสและออบเจกต์ที่สร้างอินสแตนซ์
#รวม
ใช้เนมสเปซ std;
คลาส TheCla
{
สาธารณะ:
intหนึ่ง;
คงที่ charch;
โมฆะการทำงาน(charไม่, const char *NS)
{
ค่าใช้จ่าย<< 'มี' <<หนึ่ง<< 'หนังสือคุ้ม' <<ไม่<<NS<< ' ในร้าน.' << 'NS';
}
คงที่ โมฆะสนุก(charch)
{
ถ้า (ch== 'ถึง')
ค่าใช้จ่าย<< 'ฟังก์ชั่นสมาชิกคงที่อย่างเป็นทางการ' << 'NS';
}
};
intหลัก()
{
TheCla obj1;TheCla obj2;TheCla obj3;TheCla obj4;TheCla obj5;
คิว<TheCla>นั่น;
นั่น.ดัน(obj1);นั่น.ดัน(obj2);นั่น.ดัน(obj3);นั่น.ดัน(obj4);นั่น.ดัน(obj5);
ค่าใช้จ่าย<<นั่น.ขนาด() << 'NS';
กลับ 0;
} รายการที่เชื่อมโยง
แอพพลิเคชั่นของคิว
การแบ่งปันทรัพยากรคอมพิวเตอร์
การจัดการการขัดจังหวะ
จัดการข้อมูล
บทสรุป