DOUG LLOYD: ดังนั้นถ้าคุณได้ ดูวิดีโอบนกอง
นี้อาจจะรู้สึกว่า เช่นเล็กน้อยของ Deja Vu
มันจะเป็นแนวคิดที่คล้ายกันมาก เพียงกับบิดเล็กน้อยเกี่ยวกับมัน
เรากำลังจะพูดคุยเกี่ยวกับการรอคิวในขณะนี้
ดังนั้นคิวคล้ายกับสแต็ค, เป็นชนิดของโครงสร้างข้อมูลอื่น
ที่เราสามารถใช้ในการรักษา ข้อมูลในทางที่จัด
คล้ายกับสแต็ค, จะสามารถดำเนินการ
เป็นอาร์เรย์หรือรายการที่เชื่อมโยง
ซึ่งแตกต่างจากกองกฎ ที่เราใช้ในการตรวจสอบ
เมื่อสิ่งที่ได้รับการเพิ่มและลบออกจาก คิวมีความแตกต่างกันเล็กน้อย
>> ซึ่งแตกต่างจากกองที่ เป็นโครงสร้าง LIFO ที่
สุดท้ายในออกครั้งแรกคิวเป็นแบบ FIFO โครงสร้าง FIFO ครั้งแรกในครั้งแรกออกมา
ตอนนี้คิวคุณอาจ มีเปรียบเทียบกับคิว
หากคุณเคยอยู่ในสายที่ สวนสนุกหรือธนาคาร
มีการเรียงลำดับของความเป็นธรรม โครงสร้างการดำเนินการ
คนแรกในสายที่ ธนาคารเป็นคนแรก
ผู้ที่ได้รับเพื่อพูดคุยกับหมอดู
>> มันจะเรียงลำดับของการแข่งขัน ไปที่ด้านล่างถ้าวิธีเดียวที่
คุณได้พูดคุยกับพนักงานที่ได้ ธนาคารจะเป็นคนสุดท้ายที่อยู่ในแนวเดียวกัน
ทุกคนมักจะต้องการ จะเป็นคนสุดท้ายที่อยู่ในแถว
และคนที่อยู่ที่นั่นเป็นครั้งแรก ที่ได้รับการรอในขณะที่
อาจจะมีเวลาหลายชั่วโมง และชั่วโมงและชั่วโมง
ก่อนที่พวกเขามีโอกาสที่จะเป็นจริง เบิกเงินใด ๆ ที่ธนาคาร
และการรอคิวเพื่อให้มีการจัดเรียงของ ความเป็นธรรมโครงสร้างการดำเนินการ
แต่นั่นไม่ได้หมายความว่า ที่กองเป็นสิ่งที่ไม่ดีเพียง
ที่รอคิวเป็นวิธีที่จะทำมันอีก
ดังนั้นอีกครั้งคิวเป็นครั้งแรกในครั้งแรก ออกเมื่อเทียบกับสแต็คที่สุดท้ายในการ
ก่อนออก
คล้ายกับสแต็ค, เรามีสองการดำเนินงาน
ที่เราจะได้ดำเนินการเกี่ยวกับการรอคิว
ชื่อเป็น Enqueue ซึ่งก็คือการเพิ่ม องค์ประกอบใหม่ที่ส่วนท้ายของคิว
และ dequeue ซึ่งเป็น การลบที่เก่าแก่ที่สุด
องค์ประกอบจากด้านหน้าของคิว
ดังนั้นเรากำลังจะเพิ่มองค์ประกอบ เข้าสู่ท้ายของคิว
และเรากำลังจะลบองค์ประกอบ จากด้านหน้าของคิว
อีกครั้งกับสแต็คเราได้เพิ่ม องค์ประกอบที่ด้านบนสุดของสแต็ค
และลบองค์ประกอบ จากด้านบนของสแต็ค
ดังนั้นด้วย Enqueue ก็เพิ่มให้ ท้ายที่สุดออกจากด้านหน้า
ดังนั้นสิ่งที่เก่าแก่ที่สุดในการมี มักจะเป็นสิ่งต่อไปที่
ที่จะออกมาถ้าเราพยายาม และบางสิ่งบางอย่าง dequeue
>> ดังนั้นอีกครั้งกับคิวที่เราสามารถทำได้ การใช้งานอาร์เรย์ตาม
และการใช้งานที่เชื่อมโยงตามรายการ
เราจะเริ่มต้นอีกครั้งกับ การใช้งานอาร์เรย์ตาม
ความหมายโครงสร้าง มีลักษณะคล้ายสวย
เรามีอาร์เรย์อื่น มีข้อมูลค่าชนิด
เพื่อที่จะสามารถถือชนิดข้อมูลโดยพลการ
เรากำลังอีกครั้งจะใช้ จำนวนเต็มในตัวอย่างนี้
>> และเช่นเดียวกับเรา การดำเนินการสแต็คอาร์เรย์ตาม
เพราะเรากำลังใช้ อาร์เรย์เราจำเป็นต้อง
มีข้อ จำกัด ว่าชนิด C บังคับใช้ของเราซึ่งก็คือเรา
ไม่ได้มีชีวิตชีวาในของเรา ความสามารถในการเติบโตและหดอาร์เรย์
เราต้องตัดสินใจที่จุดเริ่มต้น สิ่งที่เป็นจำนวนสูงสุดของสิ่งที่
ที่เราสามารถใส่ลงไปในนี้ คิวและในกรณีนี้
กำลังการผลิตจะเป็นปอนด์บาง ที่กำหนดไว้คงที่ในรหัสของเรา
และเพื่อวัตถุประสงค์นี้ วิดีโอกำลังการผลิตเป็นไปได้ 10
>> เราจำเป็นต้องติดตาม ด้านหน้าของคิว
ดังนั้นเราจึงได้รู้ว่าที่องค์ประกอบ เราต้องการที่จะ dequeue,
และเรายังต้องติดตาม บางสิ่งบางอย่าง else-- จำนวนขององค์ประกอบ
ที่เรามีอยู่ในคิวของเรา
ขอให้สังเกตเราไม่ได้ติดตาม ของการสิ้นสุดของคิวเพียง
ขนาดของคิว
และเหตุผลที่จะหวังว่า เป็นบิตที่ชัดเจนในช่วงเวลาที่
เมื่อเราได้เสร็จสิ้น การกำหนดประเภทนี้
เรามีชนิดข้อมูลใหม่ ที่เรียกว่าคิวที่เราสามารถทำได้ในขณะนี้
ประกาศตัวแปรของชนิดข้อมูลที่
และค่อนข้างพลุกพล่านฉันได้ตัดสินใจ ที่จะเรียกคิวคิวนี้ตัวอักษร
คิวแทนชนิดข้อมูลคิว
>> ดังนั้นนี่คือคิวของเรา
มันเป็นโครงสร้าง
มันมีสมาชิกสามคนหรือสาม เขตข้อมูลอาร์เรย์ของความจุขนาด
ในกรณีนี้กำลังการผลิตอยู่ที่ 10
และอาเรย์นี้ ไปถือจำนวนเต็ม
สีเขียวเป็นด้านหน้าของคิวของเราที่ องค์ประกอบถัดไปจะถูกลบออกและสีแดง
จะเป็นขนาดของคิว วิธีการหลายองค์ประกอบที่มีอยู่ในปัจจุบัน
ที่มีอยู่ในคิว
ดังนั้นถ้าเราพูด q.front เท่ากับ 0 และขนาด q.size เท่ากับ 0--
เรากำลังวาง 0s ลงในเขตข้อมูลเหล่านั้น
และที่จุดนี้เราสวยมาก พร้อมที่จะเริ่มทำงานกับคิวของเรา
>> ดังนั้นการดำเนินการครั้งแรกที่เราสามารถทำได้ ดำเนินการคือการ enqueue บางสิ่งบางอย่าง
เพื่อเพิ่มองค์ประกอบใหม่ใน ในตอนท้ายของคิว
ดีทำในสิ่งที่เราจำเป็นต้อง ทำอย่างไรในกรณีทั่วไป?
ดีฟังก์ชั่นนี้ enqueue ความต้องการ ที่จะยอมรับตัวชี้ไปยังคิวของเรา
อีกครั้งถ้าเราได้ประกาศ คิวของเราทั่วโลก
เราจะไม่ต้องทำเช่นนี้ จำเป็นต้อง แต่โดยทั่วไปเรา
ต้องยอมรับคำแนะนำ โครงสร้างข้อมูล
เช่นนี้เพราะมิฉะนั้น, เรากำลังผ่าน value-- เรา
ผ่านในสำเนาของคิว และเพื่อให้เราไม่ได้มีการเปลี่ยนแปลงจริง
คิวที่เราตั้งใจที่จะเปลี่ยน
>> สิ่งอื่น ๆ ที่จะต้องทำคือการยอมรับ องค์ประกอบของข้อมูลประเภทที่เหมาะสม
อีกครั้งในกรณีนี้ก็ จะเป็นจำนวนเต็ม
แต่คุณสามารถทำได้โดยพลการ ประกาศชนิดข้อมูลเป็นค่า
และการใช้งานนี้มากขึ้นโดยทั่วไป
นั่นเป็นองค์ประกอบที่เราต้องการ enqueue, เราต้องการที่จะเพิ่มถึงจุดสิ้นสุดของคิว
แล้วเราจริงต้องการ วางข้อมูลที่อยู่ในคิว
ในกรณีนี้วางไว้ใน ตำแหน่งที่ถูกต้องของอาร์เรย์ของเรา
แล้วเราต้องการที่จะเปลี่ยนขนาด ของคิวกี่องค์ประกอบเรา
ในขณะนี้มี
>> ดังนั้นขอเริ่มต้น
นี่คืออีกครั้งที่ทั่วไป รูปแบบการประกาศฟังก์ชัน
สำหรับสิ่งที่ Enqueue อาจมีลักษณะเช่น
และที่นี่เราไป
ลอง enqueue จำนวน 28 เข้าไปในคิว
ดังนั้นสิ่งที่เราจะทำอย่างไร
ดีด้านหน้าของคิวของเราเป็น ที่ 0 และขนาดของคิวของเรา
อยู่ที่ 0 และเพื่อให้เราอาจจะต้องการที่จะนำ หมายเลข 28 ในหลายองค์ประกอบอาร์เรย์
0 ใช่มั้ย?
ดังนั้นเราจึงได้วางไว้ในขณะนี้ว่าในการมี
ดังนั้นตอนนี้สิ่งที่เราจำเป็นต้องเปลี่ยน?
เราไม่ต้องการที่จะเปลี่ยน ด้านหน้าของคิว
เพราะเราต้องการที่จะรู้ว่าสิ่งที่องค์ประกอบ เราอาจจะต้อง dequeue ภายหลัง
ดังนั้นเหตุผลที่เรามีหน้ามี คือการจัดเรียงของตัวบ่งชี้ของสิ่งที่เป็น
สิ่งที่เก่าแก่ที่สุดในอาร์เรย์
ดีสิ่งที่เก่าแก่ที่สุดใน array-- ใน ความเป็นจริงมีเพียงสิ่งเดียวในอาร์เรย์ที่เหมาะสม
now-- เป็น 28 ซึ่งเป็น ในสถานที่อาร์เรย์ 0
ดังนั้นเราจึงไม่ต้องการที่จะ เปลี่ยนที่หมายเลขสีเขียว
เนื่องจากว่าเป็นองค์ประกอบที่เก่าแก่ที่สุด
แต่เราต้องการที่จะเปลี่ยนขนาด
ดังนั้นในกรณีนี้เราจะ ขนาดที่เพิ่มขึ้นถึง 1
>> ตอนนี้เป็นประเภททั่วไปของความคิดในการที่ องค์ประกอบถัดไปจะไปในคิว
คือการเพิ่มตัวเลขทั้งสอง ร่วมกันด้านหน้าและขนาด
และที่จะบอกคุณที่ต่อไป องค์ประกอบในคิวจะไป
ดังนั้นตอนนี้ขอ enqueue หมายเลขอื่น
ลอง enqueue 33
ดังนั้น 33 จะไปลงใน สถานที่ตั้งของอาร์เรย์ 0 บวก 1
ดังนั้นในกรณีนี้ก็จะ ที่จะเข้าไปในสถานที่อาร์เรย์ 1,
และตอนนี้ขนาดของคิวของเราคือ 2
>> อีกครั้งที่เราไม่ได้เปลี่ยน ด้านหน้าของคิวของเรา
เพราะวันที่ 28 ยังคงเป็น องค์ประกอบที่เก่าแก่ที่สุดและเรา
ต้องการ to-- เมื่อเราได้รับในที่สุด เพื่อ dequeuing ลบองค์ประกอบ
จากคิวนี้เราต้องการที่จะรู้ องค์ประกอบที่เก่าแก่ที่สุดคือ
และเพื่อให้เรามักจะต้องรักษา ตัวบ่งชี้ที่บางส่วนของที่เป็น
ดังนั้นสิ่งที่ 0 จะมีสำหรับ
นั่นคือสิ่งที่ด้านหน้าจะมีสำหรับ
>> ลองในองค์ประกอบของ Enqueue อีกหนึ่ง 19
ฉันแน่ใจว่าคุณสามารถคาดเดา 19 ที่จะไป
มันจะไปลง สถานที่ตั้งจำนวน 2 อาร์เรย์
นั่นเป็นบวก 2 0
และตอนนี้ขนาดของคิวของเราคือ 3
เรามี 3 องค์ประกอบในนั้น
ดังนั้นถ้าเราจะและเราจะไม่ ไปทางขวาตอนนี้ enqueue องค์ประกอบอื่น
มันจะไปในสถานที่อาร์เรย์ 3 จำนวนและขนาดของคิวของเรา
จะเป็น 4
ดังนั้นเราจึงได้ enqueued หลายองค์ประกอบในขณะนี้
ตอนนี้ขอเริ่มต้นที่จะลบออก
ลอง dequeue พวกเขาจากคิว
>> ดังนั้นคล้ายกับป๊อปอัพซึ่งเป็นประเภท อนาล็อกนี้สำหรับกอง
dequeue ต้องการที่จะยอมรับ ตัวชี้ไปยัง queue-- อีกครั้ง
เว้นแต่จะประกาศทั่วโลก
ตอนนี้เราต้องการที่จะเปลี่ยนสถานที่ ด้านหน้าของคิว
ซึ่งเป็นที่ที่จัดเรียงของมันมา ลงเล่นที่ตัวแปรด้านหน้า
เพราะเมื่อเราลบ องค์ประกอบที่เราต้องการ
ที่จะย้ายไปยังองค์ประกอบที่เก่าแก่ที่สุดต่อไป
>> จากนั้นเราก็ต้องการที่จะลดลง ขนาดของคิว
แล้วเราต้องการที่จะส่งกลับค่า ที่ถูกเอาออกจากคิว
อีกครั้งที่เราไม่ได้ต้องการเพียงแค่ทิ้งมัน
เราน่าจะมีการสกัด ได้จาก queue-- ที่เรากำลัง
dequeuing เพราะเราดูแลเกี่ยวกับเรื่องนี้
ดังนั้นเราจึงต้องการฟังก์ชั่นนี้เพื่อกลับ องค์ประกอบข้อมูลค่าชนิด
อีกครั้งในกรณีนี้ค่าเป็นจำนวนเต็ม
>> ดังนั้นตอนนี้ขอ dequeue บางสิ่งบางอย่าง
ลองลบองค์ประกอบจากคิวที่
ถ้าเราบอก int x เท่ากับ & Q, เครื่องหมาย q-- อีกครั้งที่ชี้ไปยังข้อมูลคิวนี้
structure-- สิ่งที่องค์ประกอบ เป็นไปได้ dequeued?
ในกรณีนี้เพราะมันเป็นครั้งแรก ในครั้งแรกจากโครงสร้างข้อมูลแบบ FIFO,
สิ่งแรกที่เราใส่ลงไปในนี้ คิว 28 และอื่น ๆ ในกรณีนี้
เรากำลังจะใช้เวลา 28 ออกจาก คิวไม่ได้ 19 ซึ่งเป็นสิ่งที่
เราจะได้ทำถ้านี่เป็นกอง
เรากำลังจะไปใช้เวลา 28 ออกจากคิว
>> คล้ายกับสิ่งที่เราทำกับ กองเราไม่จริง
จะลบ 28 จากคิวของตัวเอง
เราเพียงแค่จะไปชนิด ของแสร้งทำเป็นว่ามันไม่ได้มี
ดังนั้นก็จะอยู่ที่นั่น ในหน่วยความจำ แต่เราเพียงแค่
ไปชนิดไม่สนใจมันโดยการย้าย อีกสองด้านของข้อมูลคิวของเรา
โครงสร้าง
เรากำลังจะเปลี่ยนหน้า
Q.front คือตอนนี้ไป เป็น 1 เพราะที่อยู่ในขณะนี้
องค์ประกอบที่เก่าแก่ที่สุดที่เรามีในของเรา คิวเพราะเราได้ลบแล้ว 28
ซึ่งเป็นองค์ประกอบที่เก่าแก่ที่สุดในอดีต
>> และตอนนี้เราต้องการที่จะเปลี่ยน ขนาดของคิว
สององค์ประกอบแทนสาม
จำได้ว่าก่อนหน้านี้ตอนนี้ผมบอกว่าเมื่อเรา ต้องการเพิ่มองค์ประกอบคิว
เราใส่ไว้ในตำแหน่งอาร์เรย์ ซึ่งเป็นผลรวมของด้านหน้าและขนาด
ดังนั้นในกรณีนี้เราก็ยังคงวาง มันองค์ประกอบถัดไปในคิว
ในสถานที่อาร์เรย์ 3 และ เราจะเห็นว่าในครั้งที่สอง
>> ดังนั้นเราจึงได้ตอนนี้ dequeued ของเรา องค์ประกอบแรกจากคิว
มาทำกันอีกครั้งเถอะ.
ลองเอาอีก องค์ประกอบจากคิว
ในกรณีที่เก่าแก่ที่สุดในปัจจุบัน องค์ประกอบที่เป็นที่ตั้งอาร์เรย์ 1
นั่นคือสิ่งที่บอกเรา q.front
ที่กล่องสีเขียวบอกเราว่า นั่นคือองค์ประกอบที่เก่าแก่ที่สุด
ดังนั้น x จะกลายเป็น 33
เราจะเพียงแค่ชนิดของลืม 33 ที่มีอยู่ในอาร์เรย์
และเราจะบอกว่าตอนนี้ องค์ประกอบที่เก่าแก่ที่สุดใหม่ในคิว
เป็นที่ตั้งของอาร์เรย์ที่ 2 และขนาด ของคิวจำนวนขององค์ประกอบ
ที่เรามีในคิว 1
ตอนนี้ขอ enqueue บางสิ่งบางอย่างและฉัน การจัดเรียงของให้นี้ไปที่สองที่ผ่านมา
แต่ถ้าเราต้องการที่จะนำเข้ามาใน 40 คิวที่ 40 ที่จะไป?
ดีที่เราได้รับการวางไว้ ใน q.front ขนาดบวกคิว
และดังนั้นจึงทำให้ความรู้สึกที่ จริงที่จะนำ 40 ที่นี่
ตอนนี้สังเกตเห็นว่าที่ บางจุดที่เรากำลังจะ
ที่จะได้รับในตอนท้ายของ อาร์เรย์ของเราภายในของคิว
แต่ที่จางหายไป 28 และ 33-- พวกเขากำลังจริงในทางเทคนิค
เปิดช่องว่างใช่มั้ย?
ดังนั้นเราอาจ eventually-- ว่ากฎของการเพิ่ม
ทั้งสอง together-- ในที่สุดเราก็อาจจะ ต้อง mod ตามขนาดของความจุ
เพื่อให้เราสามารถห่อรอบ
>> ดังนั้นถ้าเราได้รับไปยังองค์ประกอบ เลขที่ 10 ถ้าเรา
แทนที่มันในองค์ประกอบจำนวน 10 เราต้องการ จริงใส่ไว้ในตำแหน่งอาร์เรย์ 0
และถ้าเรากำลังจะไป อาร์เรย์ location-- ขอโทษนะ
ถ้าเราเพิ่มพวกเขาขึ้นมาด้วยกัน และเราได้ไปที่หมายเลข
11 จะเป็นที่ที่เราจะต้องใส่ มันซึ่งไม่อยู่ใน array-- นี้
มันจะออกไปจากตัว
เราสามารถ mod 10 และวาง ไว้ในตำแหน่งอาร์เรย์ 1
เพื่อให้เป็นวิธีการทำงานของคิว
พวกเขากำลังเสมอไปที่จะไปจากทางด้านซ้าย ไปทางขวาและอาจจะห่อรอบ
และคุณรู้ว่าพวกเขากำลัง เต็มถ้าขนาดกล่องสีแดง
กลายเป็นเท่ากับกำลังการผลิต
ดังนั้นหลังจากที่เราได้เพิ่ม 40 ไปยัง คิวดีทำในสิ่งที่เราต้องทำอย่างไร
ดีองค์ประกอบที่เก่าแก่ที่สุด ในคิวยังคงที่ 19
ดังนั้นเราจึงไม่ต้องการที่จะเปลี่ยน ด้านหน้าของคิว
แต่ตอนนี้เรามีสอง องค์ประกอบในคิว
และเพื่อให้เราต้องการที่จะเพิ่ม ขนาดของเรา 1-2
>> ที่สวยมากด้วย การทำงานร่วมกับคิวอาเรย์ที่ใช้
และคล้ายกับกอง นอกจากนี้ยังมีวิธีการที่
ที่จะใช้คิวเป็นรายการที่เชื่อมโยง
ตอนนี้ถ้าโครงสร้างข้อมูลประเภทนี้ มีลักษณะที่คุ้นเคยกับคุณมันเป็น
มันไม่ได้เป็นรายการที่เชื่อมโยงโดยลำพัง มันเป็นรายการที่เชื่อมโยงเป็นทวีคูณ
และตอนนี้เป็นกันก็คือ จริงที่เป็นไปได้ในการดำเนินการ
คิวเป็นรายการที่เชื่อมโยงโดยลำพัง แต่ ผมคิดว่าในแง่ของการสร้างภาพ
จริง ๆ แล้วมันอาจจะช่วยในการดู นี้เป็นรายการที่เชื่อมโยงเป็นทวีคูณ
แต่มันก็เป็นไปได้ที่จะแน่นอน ทำเช่นนี้เป็นรายการที่เชื่อมโยงโดยลำพัง
>> ดังนั้นเรามาดูได้ที่ สิ่งนี้อาจจะมีลักษณะ
ถ้าเราต้องการที่จะ enquue-- ดังนั้นตอนนี้เราอีกครั้ง
เปลี่ยนเป็นรายการที่เชื่อมโยง รูปแบบตามที่นี่
ถ้าเราต้องการที่จะ enqueue เราต้องการ เพื่อเพิ่มองค์ประกอบใหม่ที่ดี
ทำในสิ่งที่เราต้องทำอย่างไร
ดีแรกของทั้งหมดเพราะ เรากำลังเพิ่มไปยังจุดสิ้นสุด
และลบจาก จุดเริ่มต้นที่เราอาจ
ต้องการที่จะรักษาตัวชี้ไปยังทั้งสอง หัวและหางของรายการที่เชื่อมโยงหรือไม่
หางเป็นระยะอีก ในตอนท้ายของรายการที่เชื่อมโยง
องค์ประกอบสุดท้ายในรายการที่เชื่อมโยง
และสิ่งเหล่านี้อาจจะ อีกครั้งจะเป็นประโยชน์กับเรา
หากพวกเขาเป็นตัวแปรทั่วโลก
แต่ตอนนี้ถ้าเราต้องการที่จะเพิ่มใหม่ องค์ประกอบสิ่งที่เราจะต้องทำอย่างไร
สิ่งที่เราเพียง [? Malak?] หรือแบบไดนามิก จัดสรรโหนดใหม่ของเราเพื่อตัวเราเอง
และจากนั้นก็เช่นเดียวกับเมื่อเราเพิ่มใด ๆ องค์ประกอบเรารายการที่เชื่อมโยงทวีคูณ
เพียงแค่มีการจัดเรียง of-- ผู้ที่ผ่านขั้นตอนที่สามที่นี่
เป็นเพียงข้อมูลเกี่ยวกับการเคลื่อนย้าย คำแนะนำในทางที่ถูกต้อง
เพื่อให้องค์ประกอบที่จะได้รับเพิ่ม ห่วงโซ่โดยไม่ทำลายห่วงโซ่
หรือการเรียงลำดับของความผิดพลาดบางอย่าง หรือมีการเรียงลำดับของการเกิดอุบัติเหตุบางอย่าง
เกิดขึ้นโดยที่เราไม่ได้ตั้งใจ เด็กกำพร้าองค์ประกอบบางอย่างของคิวของเรา
นี่คือสิ่งที่อาจมีลักษณะเหมือน
เราต้องการที่จะเพิ่มองค์ประกอบ 10 ที่ส่วนท้ายของคิวนี้
ดังนั้นองค์ประกอบที่เก่าแก่ที่สุดที่นี่ เป็นตัวแทนจากหัว
นั่นเป็นสิ่งแรกที่เราใส่ ในนี้คิวสมมุติที่นี่
และหาง, 13, เป็นส่วนใหญ่ องค์ประกอบที่เพิ่งเพิ่ม
ดังนั้นถ้าเราต้องการที่จะเข้ามาใน enqueue 10 คิวนี้เราต้องการที่จะนำมันหลังจาก 13
และเพื่อให้เรากำลังจะไปแบบไดนามิก จัดสรรพื้นที่สำหรับโหนดใหม่
และตรวจสอบ null เพื่อให้แน่ใจว่า เราไม่ได้มีความล้มเหลวของหน่วยความจำ
แล้วเรากำลังจะไป วางลงใน 10 โหนดนั้น
และตอนนี้เราจะต้องระมัดระวัง เกี่ยวกับวิธีการที่เราจัดระเบียบตัวชี้
ดังนั้นเราจึงไม่ทำลายห่วงโซ่
>> เราสามารถตั้งค่าฟิลด์ก่อนหน้า 10 ที่จะชี้กลับไปที่หางเก่า
และตั้งแต่ '10 จะเป็น หางใหม่ในบางจุด
ตามเวลาทั้งหมดของเหล่านี้ เครือข่ายมีการเชื่อมต่อ
ไม่มีอะไรที่จะมา หลังจากวันที่ 10 ในขณะนี้
และอื่น ๆ 10 ตัวชี้ต่อไป จะชี้ให้เป็นโมฆะ,
และหลังจากนั้นเราทำเช่นนี้หลังจากที่เราได้ การเชื่อมต่อ 10 ข้างหลังเพื่อโซ่
เราสามารถใช้หัวเก่าหรือข้ออ้าง ผมหางเก่าคิว
ปลายเก่าคิว 13 และทำให้มันชี้ไปที่ 10
และตอนนี้ที่จุดนี้เรามี enqueued จำนวน 10 เข้าไปในคิวนี้
ทั้งหมดที่เราต้องทำตอนนี้เป็นเพียงการย้าย หางจะชี้ไปที่ 10 แทน 13
>> Dequeuing เป็นจริง คล้ายกันมากกับ popping
จากสแต็คที่เป็น นำมาใช้เป็นรายการที่เชื่อมโยง
ถ้าคุณเคยเห็นวิดีโอกอง
ทั้งหมดที่เราต้องทำคือการเริ่มต้นที่ เริ่มต้นพบว่าองค์ประกอบที่สอง
ฟรีองค์ประกอบแรก และจากนั้นย้ายหัว
ให้ชี้ไปที่องค์ประกอบที่สอง
อาจจะดีกว่าที่จะเห็นภาพมัน เพียงเพื่อจะเพิ่มความชัดเจนเกี่ยวกับเรื่องนี้
ดังนั้นนี่คือคิวของเราอีกครั้ง
12 เป็นธาตุที่เก่าแก่ที่สุด ในคิวของเราหัว
10 เป็นองค์ประกอบใหม่ล่าสุด ในคิวของเราหางของเรา
>> ดังนั้นเมื่อเราต้องการ เพื่อ dequeue องค์ประกอบ
เราต้องการที่จะเอาองค์ประกอบที่เก่าแก่ที่สุด
ดังนั้นสิ่งที่เราจะทำ?
ดีที่เรากำหนดตัวชี้สำรวจเส้นทาง ที่เริ่มต้นที่หัว
และเราย้ายมันเพื่อให้มัน ชี้ไปที่องค์ประกอบที่สอง
นี้ queue-- บางสิ่งบางอย่างด้วยการพูดว่า Trav เท่ากับลูกศร Trav ต่อไปตัวอย่างเช่น
จะย้าย Trav มีให้ชี้ไปที่ 15 ซึ่งหลังจากที่เรา dequeue 12
หรือหลังจากที่เราเอา 12 จะ กลายเป็นองค์ประกอบแล้วที่เก่าแก่ที่สุด
>> ตอนนี้เราได้มีไว้ในครั้งแรก องค์ประกอบผ่านหัวตัวชี้
และองค์ประกอบที่สอง ผ่านตัวชี้ Trav
เราสามารถหัวฟรีในขณะนี้และจากนั้นเราสามารถ บอกว่าไม่มีอะไรมาก่อนวันที่ 15 อีกต่อไป
ดังนั้นเราจึงสามารถเปลี่ยน 15 ก่อนหน้านี้ ตัวชี้จะชี้ให้เป็นโมฆะ,
และเราก็ย้ายหัวมากกว่า
และมีที่เราจะไป
ตอนนี้เรามีประสบความสำเร็จ dequeued 12 และตอนนี้เรา
มีคิว 4 องค์ประกอบอื่น
ที่สวยมากทั้งหมด ที่มีให้คิว
ทั้งอาร์เรย์ที่ใช้และรายชื่อที่เชื่อมโยงตาม
ฉันลอยด์ดั๊ก
นี่คือซี 50