GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
118 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 | 118 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 (64.8k 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.4k points)  
edited by
Plz check my answer.
Got it habib..
i forget to take two pointer.

Related questions

Top Users Feb 2017
  1. Arjun

    4898 Points

  2. Bikram

    4102 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. sriv_shubham

    2288 Points

  6. Smriti012

    2222 Points

  7. Arnabi

    1946 Points

  8. Debashish Deka

    1920 Points

  9. mcjoshi

    1614 Points

  10. sh!va

    1462 Points

Monthly Topper: Rs. 500 gift card

20,793 questions
25,951 answers
59,557 comments
21,976 users