求解Kattis《I can guess the data structure!》算法报错求助

我在解决Kattis平台的《我能猜出数据结构！》题目时，提交的Python脚本未通过第二个测试用例，返回"wrong answer"。自行测试若干输入均输出正确，但存在未正确处理的输入场景，以下是我的代码：

import sys


def determine_data_structure():
    hand = []
    is_stack = True
    is_queue = True
    is_priority_queue = True
    impossible = False
    num_operations = None

    for line in sys.stdin:
        if " " not in line:
            num_operations = int(line)
        else:
            line_values = line.split(" ")
            operation = int(line_values[0])
            value = int(line_values[1])
            if operation == 1:
                # Take a value from the bag
                hand.append(value)
            elif operation == 2 and value in hand:
                # Check if the value matches the expected value for each data structure
                if value in hand:
                    if is_stack and value != hand[-1]:
                        is_stack = False
                    if is_queue and value != hand[0]:
                        is_queue = False
                    if is_priority_queue and value != max(hand):
                        is_priority_queue = False
                    hand.remove(value)
            elif operation == 2 and value not in hand:
                impossible = True
                is_stack = False
                is_queue = False
                is_priority_queue = False

            num_operations -= 1

        if num_operations == 0:
            if impossible or sum([is_stack, is_queue, is_priority_queue]) == 0:
                print("impossible")
            elif sum([is_stack, is_queue, is_priority_queue]) > 1:
                print("not sure")
            elif is_stack:
                print("stack")
            elif is_queue:
                print("queue")
            elif is_priority_queue:
                print("priority queue")
            is_stack = True
            is_queue = True
            is_priority_queue = True
            impossible = False
            hand.clear()


determine_data_structure()

问题分析 #

• 共用模拟容器的逻辑错误：用同一个hand列表同时模拟栈、队列和优先队列的操作，三种结构的操作会互相干扰。例如执行队列的删除操作（移除第一个元素）后，栈和优先队列的模拟数据已被修改，后续判断必然出错。
• 重复元素处理错误：list.remove(value)只会删除第一个匹配的元素，但栈需要删除最后一个元素、优先队列需要删除最大元素，共用列表时无法分别满足不同结构的删除逻辑，会导致判断失效。
• 冗余判断：operation == 2 and value in hand分支内重复判断if value in hand，属于无效代码，但不影响结果。

修正后的代码 #

修正思路是分别维护三个独立的模拟结构，各自处理对应操作，互不干扰：

import sys
from collections import deque
import heapq

def determine_data_structure():
    for line in sys.stdin:
        line = line.strip()
        if not line:
            continue
        num_operations = int(line)
        stack = []
        queue = deque()
        max_heap = []
        is_stack = True
        is_queue = True
        is_priority = True
        
        for _ in range(num_operations):
            parts = sys.stdin.readline().strip().split()
            op = int(parts[0])
            val = int(parts[1])
            
            if op == 1:
                stack.append(val)
                queue.append(val)
                heapq.heappush(max_heap, -val)  # 用负值模拟最大堆
            else:
                # 先检查结构是否为空，为空则直接排除
                if not stack:
                    is_stack = False
                if not queue:
                    is_queue = False
                if not max_heap:
                    is_priority = False
                
                if is_stack:
                    if stack.pop() != val:
                        is_stack = False
                if is_queue:
                    if queue.popleft() != val:
                        is_queue = False
                if is_priority:
                    if -heapq.heappop(max_heap) != val:
                        is_priority = False
        
        # 判断最终结果
        count = sum([is_stack, is_queue, is_priority])
        if count == 0:
            print("impossible")
        elif count > 1:
            print("not sure")
        elif is_stack:
            print("stack")
        elif is_queue:
            print("queue")
        else:
            print("priority queue")

determine_data_structure()

修正说明 #

1. 独立维护三个结构：栈、队列、优先队列各自有专属存储容器，操作互不干扰，保证每个结构的模拟逻辑正确。
2. 优先队列优化：通过存储负值实现最大堆，heappop取出的最小负值对应原数据的最大值，符合优先队列的出队逻辑。
3. 空值检查：执行操作2时先检查结构是否为空，避免抛出异常，同时直接标记该结构不符合要求。
4. 输入处理优化：添加strip()处理输入行，避免空行或换行符导致的解析错误。

内容的提问来源于stack exchange，提问作者Fredrik Schultz