Kiểu dữ liệu trừu tượng: hợp đồng thao tác
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| stack/stæk/ | ngăn xếp |
| queue/kjuː/ | hàng đợi |
Điều gì có thể giải thích quan sát này?
- Một mô phỏng hàng đợi cần xử lý mục đang chờ lâu nhất trước. Một ngăn xếp ưu tiên mục mới nhất, do đó hợp đồng thao tác rất quan trọng.
- Bắt đầu bằng một dự đoán. Nêu rõ các đại lượng hoặc đặc điểm bạn sẽ so sánh, sau đó quyết định bằng chứng nào có thể phân biệt hai lời giải thích.
Xây dựng mô hình
- Một kiểu dữ liệu trừu tượng (ADT) xác định các giá trị và thao tác độc lập với một triển khai cụ thể. Ngăn xếp là vào sau ra trước; hàng đợi là vào trước ra trước. Giao diện bộ thu thập cần có hành vi được xác định rõ ràng cho các trường hợp rỗng và thao tác không hợp lệ.
- ngăn xếp (stack): Loại dữ liệu trừu tượng theo nguyên tắc sau cùng vào trước ra (LIFO); hàng đợi (queue): Loại dữ liệu trừu tượng theo nguyên tắc đầu vào trước ra (FIFO).
Cấu trúc nào mô phỏng hàng đợi đến theo thứ tự thông thường?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Hàng chờ tuân theo nguyên tắc nhập trước ra trước, đúng với hợp đồng của hàng đợi (queue): enqueue ở cuối, dequeue ở đầu. Ngăn xếp (stack) tuân theo nguyên tắc nhập sau ra trước, và một cấu trúc không có hợp đồng sẽ không mô hình hóa điều gì đáng tin cậy.
Ghép mỗi thuật ngữ kỹ thuật với ý nghĩa chính xác của nó.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Sử dụng các định nghĩa để phân biệt các đại lượng và quá trình liên quan.
Chọn bằng chứng có thể kiểm chứng
- Chọn cấu trúc phù hợp với mẫu truy cập yêu cầu. Độ phức tạp phụ thuộc vào triển khai và giả thiết: việc xóa mục đầu tiên khỏi mảng dịch chuyển khác với việc di chuyển con trỏ đầu trong hàng đợi.
- Theo dõi chuỗi thao tác bằng tay, sau đó so sánh chương trình với các trạng thái mong đợi. Kiểm tra các trường hợp rỗng, đơn phần tử và các thao tác lặp lại. Mô tả hành vi tràn nếu dung lượng cố định.
Hai thói quen nào sau đây giúp việc nghiên cứu hoặc mô hình trong trường hợp này trở nên thuyết phục hơn?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Việc nêu rõ các điều kiện và giả thiết giúp người khác lặp lại công việc chính xác, và ghi lại bằng chứng hỗ trợ giúp họ kiểm tra kết luận. Giấu đi các kết quả mâu thuẫn sẽ loại bỏ bằng chứng có thể thách thức một kết luận sai, và một phép đo lường không thể khẳng định một tuyên bố rộng hơn.
Làm việc từ các đại lượng đã biết
- Nêu các giá trị đã biết và đơn vị của chúng. Chọn công thức vì các giả thiết của nó phù hợp với trường hợp này, sau đó biến đổi trước khi thay số.
- Đã biết: enqueue A, B và C, sau đó dequeue hai lần. A và B rời đi; C còn lại. Sau khi enqueue D, có hai mục đang chờ, C rồi đến D. Các phép push tương tự trên ngăn xếp sẽ loại bỏ C rồi đến B.
Hàng đợi bắt đầu rỗng, nhận 7 mục và loại bỏ 4. Tìm số lượng còn lại. Sử dụng cùng quy trình: các đại lượng đã biết → mô hình → mối liên hệ → thay thế → đơn vị và diễn giải.
Một hàng đợi bắt đầu trống, nhận 7 mục và loại bỏ 4. Tìm số lượng còn lại.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Kết quả là 3 mục. Đã biết: hàng đợi rỗng; 7 lần enqueue; 4 lần dequeue. Số còn lại = 7 - 4 = 3 mục. Theo thứ tự đến, ba lượt đến gần đây nhất vẫn đang chờ.
Kiểm tra kết luận và giới hạn của nó
- Một ADT không phải là bố trí bộ nhớ cụ thể. Hàng đợi không sắp xếp theo mức độ ưu tiên trừ khi hợp đồng của nó xác định là hàng đợi ưu tiên.
- Quay trở lại quan sát ban đầu. Giải thích kết quả hỗ trợ điều gì, những điều kiện nào mà nó giả định, và một cách để kiểm chứng một giải thích cạnh tranh.
Mọi hàng đợi tự động sắp xếp các mục theo mức ưu tiên. Nhận định này sai: Hàng đợi thông thường giải phóng các mục theo thứ tự đến hoàn toàn nghiêm ngặt. Việc phục vụ theo tầm quan trọng là hàng đợi PRIORITY - một hợp đồng khác nhau cần được nêu rõ ràng.
Các loại dữ liệu trừu tượng (ADT): Hợp đồng thao tác: Chọn cấu trúc phù hợp với mô hình truy cập yêu cầu. Độ phức tạp phụ thuộc vào cách triển khai và các giả định: việc xóa phần tử đầu tiên khỏi mảng dịch chuyển khác với việc di chuyển con trỏ đầu trong hàng đợi.
Mọi hàng đợi đều tự động sắp xếp các mục theo mức độ ưu tiên.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Hàng đợi thường giải phóng các mục严格按 thứ tự đến. Việc phục vụ theo mức độ ưu tiên là hàng đợi ưu tiên (priority queue) - một hợp đồng khác phải được nêu rõ ràng.
Một kiểu dữ liệu trừu tượng cuối vào - đầu ra: viết thuật ngữ kỹ thuật.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ngăn xếp (stack) là một kiểu dữ liệu trừu tượng theo nguyên tắc cuối vào - đầu ra (LIFO).