c++ - 在 C++ 中查找队列的重复状态(顺序相同的元素)

Question

在使用 C++ 解决一些问题时，我使用内置的队列模板来创建队列。现在我需要在队列上的每个操作之后检查队列的状态，并报告队列是否恰好包含与队列先前状态中的任何一个相同的元素(以相同的顺序)。例如，考虑以下对 Queue 的逐步操作(Left-hand-side 表示队列的前端，Right-hand-side 表示队列的后端/后端):

1. (2, 4, 5, 1)
2. (4, 5, 1)
3. (4, 5, 1, 3)
4. (4, 5, 1, 3, 2)
5. (4, 5, 1, 3, 2, 4)
6. (4, 5, 1, 3, 2, 4, 5)
7. (5, 1, 3, 2, 4, 5)
8. (5, 1, 3, 2, 4, 5, 1)
9. (1, 3, 2, 4, 5, 1)
10. (3, 2, 4, 5, 1)
11. (2, 4, 5, 1)

因此，第 11 步中队列的状态(元素以及元素的顺序)与第 1 步中的相同。我需要使用 C++ 找出这种情况何时发生。 我正在考虑使用 Map 来存储 Queue 的先前状态，但不知 Prop 体该怎么做？

Answer 1

我建议为此使用不同的容器，例如 std::list，因为不可能访问队列中的每个元素。

此外，您使用 map 的方法对我来说也不错。您可以按以下方式实现它:

std::list<int> q;
std::map<std::list<int> > previousQueues;

bool queueModified()
{
    //The insert function of a map Returns whether the
    //element was inserted or not.
    bool inserted = previousQueues.insert(q).second;
    return inserted;
}

然后你可以像下面这样使用它:

q.push_back(1);
if(queueModified())
{
    cout<<"Same state"<<endl;
}

唯一的问题是您必须在每次修改队列后调用该函数。