GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
124 views

A queue is a particular kind of abstract data type. Enqueue and Dequeue makes the queue FIFO data structure. There are several efficient implementations of FIFO queues. An efficient implementation is one which can perform the operations of enququeing and dequeueing in O(1) time. The best choice is :

a] DLL                                    c] SLL

b] Dynamic Array                    d] any one of these

asked in Programming by Boss (6.5k points)  
edited by | 124 views

2 Answers

+4 votes
Best answer
The properties which are required are as follows :

a) Since queue length is not fixed , hence we can use either of the three mentioned data structures for our purpose

b) Also it is required that enqueue and dequeue operations are to be done in O(1) time.This can also be done for all.For linked list , we can maintain two pointers  one pointing to front element from where dequeue will take place and the other pointing to rear element for enqueue operation.Hence just by making a few change of pointers , we are able to enqueue an dequeue using single and double linked list.Also can be done using dynamic array by maintaining index of front and rear elements of the queue.

 

Hence D) should be the correct option.
answered by Veteran (65.1k points)  
edited by
+2 votes

Any one can be used if use two or more pointer in case od single and double pointer..Dynamic array take constant time to detele and insert .

 

answered by Veteran (44.8k points)  
edited by
Plz check my answer.
Got it habib..
i forget to take two pointer.

Related questions



Top Users Mar 2017
  1. rude

    4018 Points

  2. sh!va

    2994 Points

  3. Rahul Jain25

    2804 Points

  4. Kapil

    2606 Points

  5. Debashish Deka

    2092 Points

  6. 2018

    1414 Points

  7. Vignesh Sekar

    1318 Points

  8. Bikram

    1218 Points

  9. Akriti sood

    1166 Points

  10. Sanjay Sharma

    1004 Points

Monthly Topper: Rs. 500 gift card

21,439 questions
26,753 answers
60,919 comments
22,929 users