选项A正确，因为使用辅助队列可以在O(1)时间复杂度内返回最大元素，且空间复杂度为O(n)。选项B错误，因为遍历整个队列的时间复杂度为O(n)，不满足要求。选项C错误，因为当最大元素被弹出时，无法在O(1)时间内找到新的最大元素。选项D错误，因为这种方法虽然可以在O(1)时间内返回最大元素，但会显著增加每个节点的存储空间，且实现复杂。