บทที่ 17 stack queue deque ใน STL
จบบทนี้ น้องจะใช้ stack queue deque และ list ที่ C++ ทำไว้ให้ แทนของที่เขียนเองด้วยอาเรย์ในบทที่ 14 โค้ดสั้นลงและไม่ต้องคิดขนาดอาเรย์ แล้วเอาไปแก้โจทย์ที่วิธีลูปซ้อนไม่ทันเวลา เช่น หาวันแรกที่ร้อนกว่าวันนี้ของทุกวัน หรือหาค่ามากสุดของทุกช่วงยาว k ด้วยการเดินรอบเดียว สองเทคนิคนี้คือ monotonic stack กับ monotonic deque ซึ่งโผล่ในโจทย์ค่ายและ TOI บ่อย และเป็นจุดเริ่มของบทอัลกอริทึมที่ต้องเลือกวิธีให้ทันตามขอบเขตโจทย์
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 17.1 stack และ queue สำเร็จรูป | คำสั่งของ stack กับ queue เวลา O(1) ของทุกคำสั่ง เทียบความยาวและความเร็วกับบทที่ 14 และอาการจริงเมื่อ pop หรือดูตัวบนสุดตอนว่าง |
| 17.2 deque และ list | เพิ่มลบได้ทั้งสองหัวด้วย deque ทำไมไม่แทรกหัวด้วย vector และ list กับ iterator แบบสั้น |
| 17.3 งานที่ใช้ stack | ตรวจวงเล็บ ปุ่ม back กับ undo คำนวณ postfix และ monotonic stack หาตัวถัดไปที่มากกว่า พร้อมเวลาที่วัดเทียบกับลูปซ้อน |
| 17.4 งานที่ใช้ queue และ deque | จำลองคิวแบบ round robin queue กับ BFS และค่ามากสุดของทุกหน้าต่างยาว k ด้วย monotonic deque |