Thread: free() problem

1. malloc() doesn't work like that. You allocate blocks of memory and you free() them exactly as you have allocated them. You're unable to change the blocks unless you realloc(), which doesn't seem to fit your design.
2. A linked list can be a queue with relatively good performance if:
   
   1. You have a reference to the beginning of the queue, and can easily delete at the beginning of the list without any ridiculous shifting of the entire queue.
   2. You have a reference to the end of the queue and can easily insert at the end of the list. Otherwise insertion will be O(n).

Originally Posted by audinue

So... *thinking*

Its efficient to implement Stack if we use array and implement Queue if we use linked-list.

If you use an array, you can make the buffer circular. That way you don't have to shift the array, you just decrement or increment the beginning and end pointers, handling wrap around correctly. You'd still have to copy the whole buffer over when it gets full, but you can use realloc() for that.

This approach should be faster then a linked list if the correct capacity is given initially.

Why would you want to implement a queue with an array?

Memory size used by array are quite smaller than linked list.

If you use an array, you can make the buffer circular. That way you don't have to shift the array, you just decrement or increment the beginning and end pointers, handling wrap around correctly. You'd still have to copy the whole buffer over when it gets full, but you can use realloc() for that.

I dont get it. Would you like to explain the design?

However, my goal is designing an efficient deque or dequeue which could be used for good dynamic array manipulation.
If I use linked-list, I will got trouble to get the element by index... >_< * confuse...

Originally Posted by audinue

Memory size used by array are quite smaller than linked list.

How so? This is the same (if both array and linked list have the same number of elements)

How so??

Using linked-list:

Code:

typedef struct node
{
   int data;
   node *next;
} node;

typedef struct
{
   node *first;
} stack;

4 elements of linked-listed stack:
[data, next][data, next][data, next][data, next] = 8 blocks

Using array:

Code:

typedef struct
{
   char *data; <-- the array
   size_t offset;
   size_t allocated;
} stack;

4 elements of array:
[offset, allocated][data][data][data][data] = 6 blocks

How so??

Originally Posted by audinue

How so??

...

How so??

Oops, I'm a fool, damn it.
But you still have to consider that the number of elements in a linked list is flexible while an array is not (and the linked-list might take less memory than the array in some situations)

A queue (and stack) by definition needn't be indexable. Pretty much push and pop should be the only things that are required.

As to implementing a queue as an array: perhaps you can postpone moving array contents forward to fill the unused space at the beginning of the array until you really need to (e.g when user tries to push an item and there is no more space left at the end of the array). That is, you wouldn't need to do it every-time something is popped, only occasionally when something is pushed.

The problem description is a perfect description of when to use a circular buffer.

Originally Posted by audinue

Memory size used by array are quite smaller than linked list.
I dont get it. Would you like to explain the design?

You have a buffer of size N. You have indexes for the first element of the queue, where you dequeue form, and the location where to enqueue the last element. You also need to store the size (or at least a boolean for if the queue is not empty).

To enqueue, you first check if the queue is not full. Assuming it isn't, you copy the value into the array at the end index. Then increment end index, and modulo by N to get the new final index. The modulo ensure proper wrap around.

To dequeue, you check if the queue is not empty. Assuming it isn't you just get the value at the start index. Then as with end index, increment it, and modulo by n.

EDIT: or read the wiki link iMalc provided.