C++ 实现队列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/873389/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
implement a queue
提问by Meir
I have the following queue class (taken from wordpress):
我有以下队列类（取自 wordpress）：
#include<iostream.h>
class Queue
{
private:
int data;
Queue*next;
public:
void Enque(int);
int Deque();
}*head,*tail;
void Queue::enque(int data)
{
Queue *temp;
temp=new Queue;
temp->data=data;
temp->next=NULL;
if(heads==NULL)
heads=temp;
else
tail->next=temp;
tail=temp;
}
int Queue::deque()
{
Queue* temp;//
temp=heads;
heads=heads->next;
return temp->data;
}
I'm trying to figure out why the compiler tells me that I have a multiple definition of "head" and "tail"- without success.
我试图弄清楚为什么编译器告诉我我有“头”和“尾”的多重定义 - 没有成功。
edit: When the compiler gives the error message it opens up a locale_facets.tcc file from I-don't-know-where and says that the error is on line 2497 in the following function:
编辑：当编译器给出错误消息时，它会从 I-don't-know-where 打开一个 locale_facets.tcc 文件，并指出错误在以下函数中的第 2497 行：
bool
__verify_grouping(const char* __grouping, size_t __grouping_size,
const string& __grouping_tmp)
Does anyone have any insights?
有没有人有任何见解？
回答by Nick Presta
Since this is homework, here is some information about queues and how you could go about implementing one.
由于这是家庭作业，这里有一些关于队列的信息以及如何实现队列。
A Queue is a standard Abstract Data Type. It has several properties associated with it:
队列是标准的抽象数据类型。它有几个与之相关的属性：
- It is a linear data structure - all components are arranged in a straight line.
- It has a grow/decay rule - queues add and remove from opposite ends.
- Knowledge of how they're constructed shouldn't be integral in using them because they have public interfaces available.
- 它是一种线性数据结构——所有组件都排列在一条直线上。
- 它有一个增长/衰减规则 - 队列从两端添加和删除。
- 了解它们的构造方式不应成为使用它们不可或缺的一部分，因为它们具有可用的公共接口。
Queues can be modeled using Sequential Arrays or Linked-Lists.
If you're using an array there are some things to consider because you grow in one direction so you will eventually run out of array. You then have some choices to make (shift versus grow). If you choose to shift back to the beginning of the array (wrap around) you have to make sure the head and tail don't overlap. If you choose to simply grow the queue, you have a lot of wasted memory.
队列可以使用顺序数组或链表建模。
如果您使用的是数组，则需要考虑一些事项，因为您是朝一个方向发展，因此最终会用完数组。然后，您需要做出一些选择（转变与增长）。如果您选择移回数组的开头（环绕），则必须确保头部和尾部不重叠。如果您选择简单地增加队列，则会浪费大量内存。
If you're using a Linked-List, you can insert anywhere and the queue will grow from the tail and shrink from the head. You also don't have to worry about filling up your list and having to wrap/shift elements or grow.
如果您使用的是链表，则可以在任何位置插入，队列将从尾部增长并从头部缩小。您也不必担心填满您的列表以及必须包装/移动元素或增长。
However you decide to implement the queue, remember that Queues should provide some common interface to use the queue. Here are some examples:
无论您决定实现队列，请记住队列应该提供一些通用接口来使用队列。这里有些例子：
- enqueue - Inserts an element at the back (tail) of the queue
- dequeue - Remove an element from the front (head) of a non-empty queue.
- empty - Returns whether the queue is empty or not
- size - Returns the size of the queue
- enqueue - 在队列的后面（尾部）插入一个元素
- dequeue - 从非空队列的前端（头部）移除一个元素。
- empty - 返回队列是否为空
- size - 返回队列的大小
There are other operations you might want to add to your queue (In C++, you may want an iterator to the front/back of your queue) but how you build your queue should not make a difference with regards to the operations it provides.
您可能希望将其他操作添加到队列中（在 C++ 中，您可能需要一个迭代器到队列的前/后），但是您构建队列的方式不应对其提供的操作产生影响。
However, depending on how you want to use your queue, there are better ways to build it. The usual tradeoff is insert/removal time versus search time. Here is a decent reference.
但是，根据您想如何使用队列，有更好的方法来构建它。通常的权衡是插入/删除时间与搜索时间。这是一个不错的参考。
回答by Mehrdad Afshari
If your assignment is not directly related to queue implementation, you might want to use the built in std::queueclass in C++:
如果您的分配与队列实现没有直接关系，您可能希望使用std::queueC++ 中的内置类：
#include <queue>
void test() {
std::queue<int> myQueue;
myQueue.push(10);
if (myQueue.size())
myQueue.pop();
}
回答by Jasiu
Why don't you just use the queue in standard C++ library?
为什么不直接使用标准 C++ 库中的队列？
#include <queue>
using namespace std;
int main() {
queue<int> Q;
Q.push(1);
Q.push(2);
Q.push(3);
Q.top(); // 1
Q.top(); // 1 again, we need to pop
Q.pop(); // void
Q.top(); // 2
Q.pop();
Q.top(); // 3
Q.pop();
Q.empty(); // true
return 0;
}
回答by kdt
There are a couple of things wrong:
有几件事是错误的：
- Your methods are declared as Enqueue and Dequeue, but defined as enqueue and dequeue: C++ is case sensitive.
- Your methods refer to "heads" which doesn't appear to exist, do you mean "head"?
- 您的方法声明为入队和出队，但定义为入队和出队：C++ 区分大小写。
- 您的方法指的是似乎不存在的“头”，您的意思是“头”吗？
回答by Tom
It looks like your problem mighthave something to do with the fact that:
看起来您的问题可能与以下事实有关：
class Queue {
// blah
} *head, * tail;
is defining a Queueclass, and declaring headand tailas type Queue*. They do not look like members of the class, which they should be.
是定义一个Queue类，并且声明head和tail类型Queue*。他们看起来不像班级的成员，他们应该是。
回答by Tom
If you need this for BFS... just use deque.
如果你需要这个用于 BFS ......只需使用 deque。
#include <deque>
using namespace std;
void BFS() {
deque<GraphNode*> to_visit;
to_visit.push_back(start_node);
while (!to_visit.empty()) {
GraphNode* current = to_visit.front();
current->visit(&to_visit); // enqueues more nodes to visit with push_back
to_visit.pop_front();
}
}
The GraphNode::visitmethod should do all your "work" and add more nodes to the queue to visit. the only methods you should need are push_back(), front(), and pop_front()
该GraphNode::visit方法应该完成您所有的“工作”并将更多节点添加到要访问的队列中。您应该需要的唯一方法是push_back(), front(), 和pop_front()
This is how I always do it. Hope this helps.
这就是我总是这样做的方式。希望这可以帮助。
