运行在 c++ 中通过队列的有用方法是什么

Question

尽管我阅读了很多关于队列接口的内容，但我只能访问队列后面和前面的元素。

我的问题：

我想在添加新队列之前检查 "the same element" 是否存在于队列中。

我的第一个解决方案是使用 for 循环，运行 SIZE_OF_QUEUE 次迭代，并且每次检查元素是否存在于队列的前面，如果存在则 "raise a flag"。在任何情况下都会弹出元素并将其推到队列的后面，并且在任何情况下都会执行相同次数的迭代。

缺点是即使马上找到元素，for循环也会保持运行ning.

我想为此使用一个队列，因为我在使用它们时必须先弹出最旧的元素。

还有其他更有效的方法吗？

谢谢

Answer 1

双端队列可以满足您的要求，因为它允许随机访问元素。它可以做队列可以做的所有事情，包括从后面弹出以及遍历所有元素。

如果您真的必须使用队列，您可以使用虚拟对象或保留列表中第一项的引用并在您再次到达它时停止，但这两种解决方案都相当笨拙。根据您所需的用例判断，队列不是您所需要的。

Answer 2

编辑：

因为 accessing elements in a deque by offsetting a pointer to another element causes undefined behavior 你可以改用这个：

template<typename T>
struct iterable_queue : public std::queue<T>
{
    typedef container_type Cont;

    typename Cont::iterator begin()
    {
        return c.begin();
    }

    typename Cont::const_iterator begin() const
    {
        return c.begin();
    }

    typename Cont::iterator end()
    {
        return c.end();
    }

    typename Cont::const_iterator end() const
    {
        return c.end();
    }
};

Answer 3

现在每次插入队列时，都会迭代所有元素，这非常耗时。 Enqueue() 的时间复杂度从 O(1) 上升到 O(n)。

如果您可以牺牲一些内存（基于您的数据规模），您可以为您的队列维护一个散列 table。每次插入东西时，首先检查它是否在 hashtable 中。如果是这样，插入到散列table 和队列中。当您执行 Dequeue() 时，也删除 hashtable 中的元素。这样，你Enqueue和Dequeue的时间复杂度还是O(1)。但正如我所说，您使用额外的内存来获得收益。

运行 在 c++ 中通过队列的有用方法是什么

what is the usefule way to run over a queue in c++

c++

queue

运行在 c++ 中通过队列的有用方法是什么