free() problem

Here is the scene:
I want to implement queue using array in C.

First, I allocating a memory block (e.g. 4)

Code:

---

[ ][ ][ ][ ] <-- this is the array

---

Then I call unshift function that will append the data similar to the push function in

stack.

Code:

---

unshift(2)
[2][ ][ ][ ]

unshift(3)
[2][3][ ][ ]

unshift(7)
[2][3][7][ ]

unshift(1)
[2][3][7][1]

---

Ok, after that, I call the shift function that will return the first offset in the array

increased by one.

Code:

---

[2][3][7][1] <-- initial array

print shift --> output: 2
[ ][3][7][1]

print shift --> output: 3
[ ][ ][7][1]

print shift --> output: 7
[ ][ ][ ][1]

---

Of course, there is a slow version of the shift function that will return the first offset in the array then do a real shifting (using loop).

Code:

---

[2][3][7][1] <-- initial array

print shift --> output: 2
[3][7][1][ ]

print shift --> output: 3
[7][1][ ][ ]

print shift --> output: 7
[1][ ][ ][ ]

---

Nah, the problem is:

I think I would prefer the first shift function because the speed.

1. But from the algorithm above, is there a way to free certain block of memory?

Code:

---

print shift --> output: 3
[ ][ ][ ][1]

---

For example, I want to free the memory block index from 0 to 2.

2. How about linked-listed queue? Is there a guarantee for the speed if we are using it to implementing queue?

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).

So... *thinking*

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

Why would you want to implement a queue with an array? These generic collections (stack, queue, linked list, binary trees, ...) are useful, also because their size is dynamic.

Quote:

---

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.

Quote:

---

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

---

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

Quote:

---

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...

Quote:

---

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

Quote:

---

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)

eXeCuTeR: Would you like to give me some advice how to get element by index using linked list??

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.

anon! Thank you! You opened my eyes! :D :D :D

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

Quote:

---

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.

I'm a little bit stupid here King Mir, sorry. I still don't get it. -_-"?

Quote:

---

Originally Posted by audinue

I'm a little bit stupid here King Mir, sorry. I still don't get it. -_-"?

---

It would help if you specified the part you didn't understand.

You can also try google. to find more explanations and even java applets demonstrating circular queues.

Quote:

---

Originally Posted by audinue

eXeCuTeR: Would you like to give me some advice how to get element by index using linked list??

---

Well, this is an option:
(there's no checking whether index is bigger than the number of elements of the linked list, you can make one easily though)

Code:

---

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


node *getElementByIndex(node *myList, int index)
{
 node *pos = myList; // pointing to the first element
 while(index >= 0)
 {
  pos = pos->next;
  --index;
 }
 return pos;
}

---

King Mir: It is ok if we using circular buffer. But how to solve when the array is full? *confuse*

Quote:

---

Originally Posted by audinue

King Mir: It is ok if we using circular buffer. But how to solve when the array is full? *confuse*

---

You have to create a new bigger array. Then you copy each element over. This is most easily done by dequeuing one element at a time, and queuing it in the bigger buffer queue. Or you can just copy the everything from the first element to the end of the buffer first, then every thing from the start of the buffer to the last index, not including the last index itself.

Pictorially you want to do this:
Old buffer
---|-- < start index
---|-- < one past the end index.
DEFABC

New buffer:
|----------- < start index
------|----- < one past the end index.
ABCDEFXXXXXX

A little bit more complicated I think, but it's OK...

Thank you very much King Mir :)