simple implementation of queue

Question

I have the following queue class (taken from 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:

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

Does anyone have any insights?

Answer 1

If your assignment is not directly related to queue implementation, you might want to use the built in std::queue class in C++:

#include <queue>

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

Answer 2

Why don't you just use the queue in standard C++ library?

#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 3

If you need this for BFS... just use 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::visit method 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()

This is how I always do it. Hope this helps.

Answer 4

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"?

Answer 5

It looks like your problem might have something to do with the fact that:

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

is defining a Queue class, and declaring head and tail as type Queue*. They do not look like members of the class, which they should be.

Answer 6

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:

1. It is a linear data structure - all components are arranged in a straight line.
2. It has a grow/decay rule - queues add and remove from opposite ends.
3. 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:

1. enqueue - Inserts an element at the back (tail) of the queue
2. dequeue - Remove an element from the front (head) of a non-empty queue.
3. empty - Returns whether the queue is empty or not
4. size - Returns the size of the queue

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.

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.