在 C++ 中查找队列的重复状态（顺序相同的元素）

Question

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

(2, 4, 5, 1)
(4, 5, 1)
(4, 5, 1, 3)
(4, 5, 1, 3, 2)
(4, 5, 1, 3, 2, 4)
(4, 5, 1, 3, 2, 4, 5)
(5, 1, 3, 2, 4, 5)
(5, 1, 3, 2, 4, 5, 1)
(1, 3, 2, 4, 5, 1)
(3, 2, 4, 5, 1)
(2, 4, 5, 1)

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

Answer 1

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

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

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;
}

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

Answer 2

std::deque 是适合操作队列的STL容器。它是 doubled_ended 队列的标准模板库实现。您可以随时使用 std::deque::size() 函数来检查队列的大小。此 URL http://www.cplusplus.com/reference/deque/deque/

中提供了更多详细信息

在 C++ 中查找队列的重复状态（顺序相同的元素）

Finding repeated state of the Queue (same elements in order) in C++

c++

queue

data-structures

c++11