อะไรจะเป็นคำอธิบายสำหรับการสังเกตนี้?
การจำลองแถวรอต้องการรายการที่ยังค้างไว้นานที่สุดก่อน Stack ให้รายการล่าสุดก่อน ดังนั้นสัญญาการดำเนินการจึงสำคัญ
เริ่มต้นด้วยการทำนาย ระบุปริมาณหรือลักษณะที่คุณจะเปรียบเทียบ แล้วตัดสินใจว่าหลักฐานอะไรที่จะแยกแยะคำอธิบายสองแบบได้
สร้างโมเดล
Abstract data type ระบุค่าและการดำเนินการโดยไม่ขึ้นอยู่กับ Implementation เฉพาะ Stack เป็น Last in First Out Queue เป็น First in First Out Collection interface ต้องการพฤติกรรมที่กำหนดสำหรับ Operation ที่ว่างและ Operation ที่ไม่ถูกต้อง
stack: ประเภทข้อมูลนามธรรมแบบเข้า-last-ออก-first; queue: ประเภทข้อมูลนามธรรมแบบเข้า-first-ออก-first
เลือกหลักฐานที่นำมาทดสอบได้
เลือกโครงสร้างตามรูปแบบการเข้าถึงที่ต้องการ ความซับซ้อนขึ้นอยู่กับ Implementation และสมมติฐาน: การลบรายการแรกออกจาก Shift array แตกต่างจากการเลื่อน head pointer ใน queue
Trace ลำดับการดำเนินการด้วยมือ แล้วเปรียบเทียบโปรแกรมกับสถานะที่คาดหวัง ทดสอบ Operation ที่ว่างvisions singleton และซ้ำซ้อน State溢出 พฤติกรรมหากความจุถูกกำหนดไว้
เริ่มจากปริมาณที่ทราบแล้ว
ระบุค่าที่ทราบและหน่วยของมัน เลือกความสัมพันธ์โดยพิจารณาว่าข้อสมมติฐานสอดคล้องกับเคสนี้ แล้วจัดรูปสมการก่อนแทนค่า
Known: เควอ A, B และ C แล้วดีควอสองครั้ง A และ B ออก; C คงอยู่ หลังจากเควอ D จะมีรายการรอสองรายการ คือ C แล้ว D การกด push เดียวกันบน stack จะเอา C ออกก่อนแล้วจึงเอา B ออก
ตัวอย่าง:
Queue เริ่มว่าง รับ 7 รายการ และเอาออก 4. หาจำนวนที่เหลือ ใช้ลำดับเดียวกัน: จำนวน Known → โมเดล → ความสัมพันธ์ → การแทนค่า → หน่วยและการตีความ
ตรวจสอบข้อสรุปและขอบเขต
ADT ไม่ใช่การจัดวางหน่วยความจำเฉพาะ Queue ไม่เรียงลำดับตามความสำคัญเว้นแต่สัญญาจะกำหนด priority queue
กลับไปที่การสังเกตเดิม อธิบายว่าผลลัพธ์นี้สนับสนุนสิ่งใด มีเงื่อนไขใดบ้าง และเป็นอย่างไรในการทดสอบคำอธิบายอื่นที่ขัดแย้งกัน
เตือน:
คิวจะจัดลำดับรายการโดยอัตโนมัติตามระดับความสำคัญ ข้ออ้างนี้ไม่ถูกต้อง: ADT ไม่ใช่การจัดเก็บข้อมูลจำเพาะ คิวจะไม่จัดลำดับตามระดับความสำคัญเว้นแต่สัญญาของคิวจะกำหนดว่าเป็นคิวน้ำหนัก
จุดสำคัญ:
ประเภทข้อมูลเชิงนามธรรม: สัญญาการดำเนินการ: เลือกโครงสร้างสำหรับการเข้าถึงรูปแบบที่ต้องการ ความซับซ้อนขึ้นอยู่กับวิธีนำไปใช้และสมมติฐาน: การลบรายการแรกออกจากอาร์เรย์ที่เลื่อนตำแหน่ง differs from การเคลื่อนหัวชี้ชี้ในคิว
ลายเส้นที่ดำเนินการได้และขอบเขต
from collections import deque
queue = deque()
queue.extend(["A", "B"])
print(queue.popleft())
queue.append("C")
print(queue.popleft())
print(list(queue))
queue.clear()
print(queue.popleft() if queue else "EMPTY")
ผลลัพธ์ที่คาดหวัง:
A
B
['C']
EMPTY
การลบจากด้านซ้ายใช้หลัก FIFO การตรวจสอบความว่างอย่างชัดเจนกำหนดผลลัพธ์ที่ขอบเขต; การใช้ deque.popleft โดยไม่มีเงื่อนไขนี้จะทำให้เกิด IndexError ในทางกลับกัน Stack จะลบข้อมูลจากด้านขวา
