OOPS... I missed again, my bad... both enqueue and deque can take reference. (Sincere apologies...) NO separate data structure is needed. And both operations can definitely be done, in O(n). BTW even if you don't take the reference variable in deque, it can be solved. :) :)
Regards, Sandeep Jain On Tue, Jul 5, 2011 at 10:24 AM, Kunal Patil <[email protected]> wrote: > @Sandeep: Without storing explicit pointer to last element, how would you > be able to access last element in a Singly Linked List in O(1) ??? Is there > any parallel data structure that needs to be maintained ?? and if it is > larger than size of 2 explicit pointers to last and first elements then 2 > pointer strategy is obviously better !! > > > On Tue, Jul 5, 2011 at 10:11 AM, Sandeep Jain <[email protected]>wrote: > >> Its the queue in which you want to add a an element. >> Small correction in the enqueue signature. >> >> void enqueue(NODEPTR &q, int data) // made it a reference, I missed it >> >> And the usage would be something like >> NODEPTR myQueue = NULL; >> >> enqueue(myQueue, 10); >> enqueue(myQueue, 20); >> >> cout<<deque(myQueue); >> >> >> >> Regards, >> Sandeep Jain >> >> >> >> >> >> On Tue, Jul 5, 2011 at 8:30 AM, vaibhav agarwal < >> [email protected]> wrote: >> >>> @sandeep what is ptr q in case of enqueue? >>> >>> >>> On Mon, Jul 4, 2011 at 12:53 PM, Sandeep Jain <[email protected]>wrote: >>> >>>> How bout I say, the insertion and deletion functions have the following >>>> prototype? >>>> >>>> void enqueue(NODEPTR q, int data) >>>> int deque(NODEPTR q) >>>> >>>> You are not allowed to maintain two pointers, i.e. no front and no rare >>>> pointers... >>>> >>>> >>>> Regards, >>>> Sandeep Jain >>>> Member of Technical Staff, Adobe Systems, India >>>> >>>> >>>> >>>> >>>> On Mon, Jul 4, 2011 at 10:20 PM, surender sanke <[email protected]>wrote: >>>> >>>>> always maintain front and rear pointers, updating them accordingly >>>>> during insertion and deletion can achieve this in O(1) >>>>> >>>>> surender >>>>> >>>>> >>>>> On Mon, Jul 4, 2011 at 9:59 PM, vaibhav shukla < >>>>> [email protected]> wrote: >>>>> >>>>>> How to implement a QUEUE using a singly link list such that the >>>>>> operations ENQUEUE and DEQUEUE takes O(1) time ? >>>>>> >>>>>> -- >>>>>> best wishes!! >>>>>> Vaibhav Shukla >>>>>> >>>>>> >>>>>> -- >>>>>> You received this message because you are subscribed to the Google >>>>>> Groups "Algorithm Geeks" group. >>>>>> To post to this group, send email to [email protected]. >>>>>> To unsubscribe from this group, send email to >>>>>> [email protected]. >>>>>> For more options, visit this group at >>>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>>> >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Algorithm Geeks" group. >>>>> To post to this group, send email to [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]. >>>>> For more options, visit this group at >>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>> >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To post to this group, send email to [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
