คิวและ collections.deque
เพิ่มและนำข้อมูลออกจากทั้งสองด้านอย่างรวดเร็ว
คิวและ collections.deque เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
เข้าก่อน ออกก่อน
คิว จะให้บริการสมาชิกตามลำดับที่เข้ามา เช่นเดียวกับแถวรอหน้าร้าน สมาชิกที่เข้าก่อนจะออกก่อน
เหตุใดจึงไม่ใช้ลิสต์
ลิสต์สามารถนำสมาชิกจากด้านหน้าออกได้ แต่ pop(0) ใช้เวลา O(n) เพราะสมาชิกอื่นทุกตัวต้องเลื่อนไปทางซ้าย จึงช้าเกินไปสำหรับข้อมูลนำเข้าขนาดใหญ่
q = []
q.pop(0) # O(n), avoid thisพบกับ collections.deque
ดีคิว จาก collections คือคิวสองด้านที่เพิ่มและนำสมาชิกออกได้จากทั้งสองด้านในเวลา O(1) จึงเป็นตัวเลือกหลักสำหรับการแข่งขัน
from collections import deque
q = deque()ใส่เข้าทางด้านหลัง
เพิ่มสมาชิกใหม่ที่ด้านขวาด้วย append เช่นเดียวกับลิสต์ ด้านนี้คือส่วนท้ายของคิว
q.append(1)
q.append(2)นำออกจากด้านหน้า
นำสมาชิกที่เก่าที่สุดออกจากด้านซ้ายด้วย popleft ซึ่งทำงานในเวลาคงที่และให้พฤติกรรมแบบ FIFO อย่างแท้จริง
first = q.popleft() # returns 1เปิดใช้งานได้ทั้งสองด้าน
ดีคิวยังรองรับ appendleft และ pop จากด้านขวา ความยืดหยุ่นนี้ทำให้โครงสร้างเดียวทำหน้าที่เป็นสแตกหรือคิวได้
q.appendleft(0)
last = q.pop()ตรวจสอบก่อนนำออก
การนำสมาชิกออกจากดีคิวที่ว่างจะทำให้เกิดข้อผิดพลาด ดังนั้นในลูปให้ทดสอบ while q เพื่อให้การไล่ตรวจของคุณปลอดภัย
while q:
x = q.popleft()คิวขับเคลื่อน BFS
การใช้งานที่พบบ่อยที่สุดในการแข่งขันคือ BFS คุณใส่โหนดเริ่มต้นเข้าคิว จากนั้นนำสมาชิกด้านหน้าออกซ้ำ ๆ และใส่โหนดเพื่อนบ้านเข้าไป
โครงร่าง BFS ขนาดเล็ก
ลูปนี้จะเยี่ยมชมโหนดทีละชั้น เพื่อนบ้านแต่ละตัวจะถูก เพิ่มเข้าไป แล้วประมวลผลภายหลังตามลำดับที่เข้ามา
while q:
node = q.popleft()
for nb in graph[node]:
q.append(nb)จำกัดขนาดดีคิว
การส่งค่า maxlen จะทำให้ดีคิวทิ้งสมาชิกที่เก่าที่สุดเมื่อเต็ม เหมาะอย่างยิ่งสำหรับหน้าต่างเลื่อนและการติดตามประวัติล่าสุด
window = deque(maxlen=3)โครงสร้างเดียว หลายบทบาท
จำไว้ว่า ดีคิว ทำงานได้รวดเร็วที่ปลายทั้งสองด้าน ดังนั้นให้เลือกใช้เมื่อใดก็ตามที่ต้องการคิว สแตก หรือบัฟเฟอร์แบบเลื่อน
ตรวจสอบอย่างรวดเร็ว
คุณต้องการนำสมาชิกด้านหน้าออกจากคิวอย่างรวดเร็ว ควรเลือกวิธีใด
สรุป: ดีคิวคือคิวที่รวดเร็ว
คุณได้รู้จัก collections.deque: ใช้ append และ popleft เพื่อทำงานแบบ FIFO ในเวลา O(1) เปิดใช้ได้ทั้งสองด้าน และใช้ maxlen กับหน้าต่างเลื่อน ดีคิวคือโครงสร้างหลักของ BFS 🎯
คำถามที่พบบ่อย
บทเรียน “คิวและ collections.deque” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “คิวและ collections.deque” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “คิวและ collections.deque”
เพิ่มและนำข้อมูลออกจากทั้งสองด้านอย่างรวดเร็ว คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “คิวและ collections.deque” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- สแตกสำหรับจับคู่วงเล็บ
- สแตกโมโนโทน: สมาชิกที่มากกว่าถัดไป
- คิวและ collections.deque
- ค่าสูงสุดในหน้าต่างเลื่อนด้วยดีค