Author |
Topic: N queues finite memory (Read 2483 times) |
|
hemanshu
Newbie
Gender: 
Posts: 14
|
 |
N queues finite memory
« on: Sep 19th, 2010, 7:48am » |
 Quote  Modify
|
Give a good data structure for having n queues ( n not fixed) in a finite memory segment. You can have some data-structure separate for each queue. Try to use at least 90% of the memory space.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: N queues finite memory
« Reply #1 on: Sep 19th, 2010, 8:06am » |
Quote Modify
|
Make a queue or stack for empty spaces in memory, and keep a queue/stack/array for the data-queues. If you need to add an element to a data-queue, take it from the free-space stack, and if you take an element from a data-queue free the memory by putting the node on the free-space stack. Every now and then clean up the array which keeps the start and end of the data-queues.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
hemanshu
Newbie
Gender:
Posts: 14
|
|
Re: N queues finite memory
« Reply #2 on: Sep 19th, 2010, 9:46am » |
Quote Modify
|
@towr : For keeping free space stack is kk.. but for implementing queue if we use array .. we have to define its size first .. if we implement it using linked list .. lot of space goes in storing pointers ..
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: N queues finite memory
« Reply #3 on: Sep 19th, 2010, 11:34am » |
Quote Modify
|
on Sep 19th, 2010, 9:46am, hemanshu wrote:| @towr : For keeping free space stack is kk.. but for implementing queue if we use array |
|
The array is for storing the basic information of the data-queues, where they start and end, because if you store that in a queue or stack you'd have to run through the whole data-structure to access the queues. For the data-queues themselves, I'd use a linked list.
Quote:| if we implement it using linked list .. lot of space goes in storing pointers .. |
|
That's a risk yes. It depends on how large the data is that you store in the queues.
You could also allocate blocks of 10 or 20 consecutive nodes (or other sized blocks), that wastes a bit of free space, but you would be wasting less on pointers. So then typically a queue would consist of a number of blocks, the first and last of which may be partly empty; once you will up the last block, you allocate a new one to continue and make a pointer from the last block to the new one.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: N queues finite memory
« Reply #4 on: Sep 20th, 2010, 5:05am » |
Quote Modify
|
on Sep 19th, 2010, 11:34am, towr wrote:| You could also allocate blocks of 10 or 20 consecutive nodes (or other sized blocks), that wastes a bit of free space, but you would be wasting less on pointers. So then typically a queue would consist of a number of blocks, the first and last of which may be partly empty; once you will up the last block, you allocate a new one to continue and make a pointer from the last block to the new one. |
|
Which is exactly how the standard C++ library lmplements deque, so I'd say it's probably a reasonable tradeoff between flexibility and wasted space.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print