Member Avatar for somjit{}

in an assingment, i have to implement a deque ( double ended queue ). the underlying datastructure is allowed to be arrays or linkedlist. only that im not allowed to use any prebuilt java api that does the above. (like the java.util.LinkedList api)

implementing the above using doubly linked list seems straighforward , but i was also looking for how it can be done using arrays. I did a rough sketch on my own, but was facing a bit of hurdle in the resizing methods.
on google-ing for some solution, i came across here where they were saying :

If you "float" both ends of the array, you can have constant-time inserts and deletes, except for when you need to resize the array when it fills up.

i remember that i did learn about "float"-ing an array.. but i cant recollect it, neither did i find anything substantial when i searched for it on the web.
I want to use arrays because i liked the concept of amortized running time , so wanted to try my hand at it...

any help regarding what "float" ing both ends of an array means? also any guide into an efficient way to solve the assingment will be really helpful :)

regards
somjit.

Edited by somjit{}
  • 2 Contributors
  • 2 Replies
  • 189 Views
  • 2 Hours Discussion Span
  • Latest Post Latest Post by somjit{}
Member Avatar for bguild

Floating the ends of the array surely means nothing more than allowing the start and end of your queue to move within the array. Just use a field to store the index of the head of the queue and another to store the index of the end of the queue, and together those are your floating ends.

When an item is removed from the head of the queue, increment your head index to the next item in line. When an item is added to the end of the queue, you increment your end index to point to the new item. When end gets to the true end of the array, you wrap it around to the beginning where there may be available space thanks to the moving head. Do the same for head and you can keep going around the array forever, unless your queue becomes too big for your array and end comes to meet head.

When the end and the head come together, you can simply create a bigger array and copy your queue into it, reseting end and head to appropriate index values in the new array.

Member Avatar for somjit{}

thanks a lot :) those were very clear and helpful answers :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.