реализовать очередь

Question

У меня есть следующий класс очереди (взят из 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;
    }

Я пытаюсь выяснить, почему компилятор говорит мне, что у меня есть множественное определение «голова» и «хвост» - без успеха.

edit: когда компилятор выдает сообщение об ошибке, он открывает файл locale_facets.tcc из я-не-знаю-где и говорит, что ошибка в строке 2497 в следующей функции:

bool
 __verify_grouping(const char* __grouping, size_t __grouping_size,
        const string& __grouping_tmp)

У кого-нибудь есть идеи?

Answer 1

Поскольку это домашнее задание, вот некоторая информация об очередях и о том, как вы могли бы реализовать их.

Очередь - это стандартный абстрактный тип данных. С ним связано несколько свойств:

1. Это линейная структура данных - все компоненты расположены по прямой линии.
2. У него есть правило роста / затухания - очереди добавляют и удаляют с противоположных концов.
3. Знание того, как они построены, не должно быть неотъемлемой частью их использования, потому что у них есть общедоступные интерфейсы.

Очереди могут быть смоделированы с использованием последовательных массивов или связанных списков.
Если вы используете массив, есть несколько вещей, на которые следует обратить внимание, потому что вы растете в одном направлении, поэтому у вас в конечном итоге будет исчерпан массив. Затем у вас есть выбор (сдвиг в сторону роста). Если вы решите вернуться к началу массива (обернуть вокруг), вы должны убедиться, что голова и хвост не перекрываются. Если вы решите просто увеличить очередь, у вас будет много потерянной памяти.

Если вы используете Linked-List, вы можете вставить куда угодно, и очередь будет расти от хвоста и уменьшаться от головы. Вам также не нужно беспокоиться о том, чтобы заполнить свой список, а также обернуть / переместить элементы или увеличить их.

Однако, если вы решите реализовать очередь, помните, что очереди должны предоставлять некоторый общий интерфейс для использования очереди. Вот несколько примеров:

1. enqueue - вставляет элемент в конец (хвост) очереди
2. dequeue - удаление элемента из передней части (головы) непустой очереди.
3. empty - Возвращает, пуста очередь или нет
4. size - возвращает размер очереди

Существуют и другие операции, которые вы, возможно, захотите добавить в свою очередь (в C ++ вам может потребоваться итератор в начале / конце вашей очереди), но то, как вы строите свою очередь, не должно иметь значения в отношении операций, которые она обеспечивает.

Однако, в зависимости от того, как вы хотите использовать свою очередь, существуют более эффективные способы ее создания. Обычный компромисс между временем вставки / удаления и временем поиска. Вот приличная ссылка .

Answer 2

Если ваше назначение не связано напрямую с реализацией очереди, вы можете использовать встроенный класс std::queue в C ++:

#include <queue>

void test() {
    std::queue<int> myQueue;
    myQueue.push(10);
    if (myQueue.size())
        myQueue.pop(); 
}

Answer 3

Почему бы вам просто не использовать очередь в стандартной библиотеке 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;
}

Answer 4

Есть пара неправильных вещей:

• Ваши методы объявлены как Enqueue и Dequeue, но определены как enqueue и dequeue: C ++ чувствителен к регистру.
• Ваши методы относятся к "головам", которых, кажется, не существует, вы имеете в виду "головы"?

Answer 5

Похоже, ваша проблема может как-то связана с тем, что:

class Queue {
  // blah
} *head, * tail;

определяет класс Queue и объявляет head и tail как тип Queue*. Они не похожи на членов класса, какими они должны быть.

Answer 6

Если вам это нужно для 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();
    }
}

Метод GraphNode::visit должен выполнить всю вашу "работу" и добавить больше узлов в очередь для посещения. единственные методы, которые вам нужны, это push_back(), front() и pop_front()

Так я всегда делаю. Надеюсь, это поможет.