wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> N queues finite memory
        
(Message started by: hemanshu on Sep 19^th, 2010, 7:48am)

Title: N queues finite memory
Post by hemanshu on Sep 19^th, 2010, 7:48am

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.

Title: Re: N queues finite memory
Post by towr on Sep 19^th, 2010, 8:06am

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.

Title: Re: N queues finite memory
Post by hemanshu on Sep 19^th, 2010, 9:46am

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

Title: Re: N queues finite memory
Post by towr on Sep 19^th, 2010, 11:34am

on 09/19/10 at 09:46:12, 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.

Title: Re: N queues finite memory
Post by SMQ on Sep 20^th, 2010, 5:05am

on 09/19/10 at 11:34:02, 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