queue structure - linked list - empty element

[madeleine]

Hi,
I had to make a queue structure using linked list. (code below)
My next task is to change it, to have empty node in front and in the end of the queue.
I'm not shure how this structure should works, I'm not able to find this type of queue anywhere.

Could you please help me to unerstand how it should work.

  typedef struct tagQueueItem
{
	int value;
	struct tagQueueItem* pNext;
}QueueItem;

typedef struct tagQueue
{
	QueueItem* pFirst;
	QueueItem* pLast;
} Queue;

void InitQueue(Queue** q);

int main(int argc, char* argv[])
{
	Queue* q;
	InitQueue(&q);
return 0;
}

void InitQueue(Queue** q)
{
	*q = (Queue*)malloc(sizeof(Queue));
	if (!*q)
	{
		perror("Error memory allocation\n");
		return;
	}
	memset(*q, 0, sizeof(Queue));
}

[dhayden]

You shouldn't use an InitQueue() function. It requires that the Queue be placed on the heap, which means you have to delete it (something that can be forgotten). And you should initialize the member variables rather than using memset.

So use a constructor instead. I've also added a constructor for QueueItem:

typedef struct tagQueueItem
{
    int value;
    struct tagQueueItem *pNext;
    tagQueueItem(int v) :
	value(v),
	pNext(nullptr) {}
} QueueItem;

typedef struct tagQueue
{
    QueueItem *pFirst;
    QueueItem *pLast;
    tagQueue() :
	pFirst(nullptr),
	pLast(nullptr)
    {}
} Queue;

int
main(int argc, char *argv[])
{
    Queue q;
    return 0;
}

My next task is to change it, to have empty node in front and in the end of the queue.

Is that required for an assignment? It's probably easier not to have these sentinel values.

[madeleine]

Yes, it's for the assignment. And I don't really understand how to start.

And I get your advices, but it is the one and only right way of implementation according to my professor. The Init function is alos required by him.

[dhayden]

Well tell your professor that Dave on cplusplus.com says he's an idiot. :) Hmm. On second thought, maybe he's using this as a way to show the motivation for constructors.

Is this class for C or C++? The fact that you're using structs and Init functions and malloc() and memset() sounds like it's C to me.

If he/she insists on an init function then I'd model it after a constructor anyway. You can create first and last nodes as follows:

typedef struct tagQueueItem
{
    int value;
    struct tagQueueItem *pNext;
} QueueItem;

typedef struct tagQueue
{
    QueueItem *pFirst;
    QueueItem *pLast;
} Queue;

void InitQueue(Queue &q);

int
main(int argc, char *argv[])
{
    Queue q;
    InitQueue(q);
    return 0;
}

void
InitQueue(Queue &q)
{
    q->pLast = new QueueItem;
    q->pFirst = new QueueItem;
    q->pFirst->next = q->pLast;
    q->pLast->next = nullptr;
}