implement of a queue(fifo)

Question

Iv'e been given a mission to implement a dynamic queue in c language without any loops and any recursion. the queue should contain the next function: installation, destruct, add, remove and peek. I thought to make a link structure, that way each link will have a pointer the next link and so on..but the problem is that I don't know how to do the destruct function without any loops, the only solution I can think of is making a loop that will send each one of the links to the remove function(but again, I need to it without any loops). Is their any possibility to do the destruct function without any loops?

p.s the destruct function should free all of the memory that we used for the queue.

"Without loops" usually means: use recursion. It's hard to be more precise without giving away the answer, and I assume this "mission" is your homework. — Fred Foo
– Fred Foo, Commented Oct 4, 2013 at 12:45
Yea it's homework, and I forgot that it says without recursion too. there is a way that I can hold all of the links in the same block in the memory and than, free all of it with one call to the fee function? — user2559696
– user2559696, Commented Oct 4, 2013 at 12:49
What kind of data is in your queue - are these elements of constant size? Numbers, structures, variable length strings, ...? — Floris
– Floris, Commented Oct 4, 2013 at 12:59

nos · Accepted Answer · 2013-10-04 12:48:16Z

1

If a recursing function doesn't count as a loop for your constrains, you could use recursion to traverse the list and destroy the items.

Another approach is to store items in an array, and maintain a pointer into the array for the head and tail of the queue. Destroying the queue just means freeing the array or resetting the head/tail pointers, and no loops would be required.

answered Oct 4, 2013 at 12:48

nos

231k60 gold badges436 silver badges516 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user2559696 Over a year ago

It's correct, but than my queue will have a limited size, and won't be dynamic(it should).

nos Over a year ago

@user2559696 not necessarily, you can malloc() the array with a given initial size, when it's full, you can use realloc() to expand it.

Leeor · Accepted Answer · 2013-10-04 12:54:48Z

There's no real need to make a queue based on a linked list, it would have all the downside of random allocated elements and lack of spatial locality, would be relatively harder to debug, and won't use the main benefit of a linked list (insertion at O(1)) since it's a queue with only one insertion point anyway (or 2 for a double-ended one).

Instead you could use an array, and maintain a head and tail index variables, use cyclic incrementation when they wrap around at the end, and reallocate when required. If the queue holds basic data types this would also allow you to deallocate the entire queue in one go, just free the array (although for elements you had to manually allocate, I can't see any way to avoid iterated removal, unless you move to c++).

Floris · Accepted Answer · 2013-10-04 13:09:35Z

I am assuming that the item to be inserted in memory is of constant size. If needed, it could be a pointer to a block of memory. In that case, you can use a circular buffer with a head and tail pointer. When either pointer "gets to the end of the block" it should wrap - i.e. you increment / decrement modulo queue size.

Initialization:

Create a memory space of finite size (max size of the buffer)

Add:

Update memory location at the current tail (if add to end) 
or head (if add to beginning), and update the tail/head pointer.

Remove:

Read the data at the head/tail, and update the pointer

Peek:

Read the data at the head/tail, and don't move the pointer

Destruct:

Free the memory block

No loops, no recursion. It uses the fact that a FIFO buffer only allows changes at the beginning / end of the queue- it is not possible to remove elements "in the middle".

If the head and tail pointers meet, the queue is "full". In that case, the "insert" function should return an error, unless you add a "insert destructively" flag that says "overwrite the oldest element". That seems beyond the scope of your homework, but it is important in real life applications. Sometimes you care about the oldest data - at other times you care about the latest data. But usually, if your queue is filling up, there is a problem with the over all system design (you didn't scale the process that empties the queue to deal with the rate at which it is filling, basically).

Note - if each element in the queue is a pointer to dynamically allocated memory you WILL need to iterate over all elements to free that memory, or you will create a memory leak. But if the queue is of constant size, this is not needed. Given the constraints given, and the lack of specification that queue element size should be variable, I would recommend you write your solution for a fixed size queue element.

Collectives™ on Stack Overflow

implement of a queue(fifo)

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related