The Gateway to Computer Science Excellence
+37 votes
8.1k views

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT ($n$ refers to the number of items in the queue) ?

  1. Both operations can be performed in $O(1)$ time.
  2. At most one operation can be performed in $O(1)$ time but the worst case time for the operation will be $\Omega (n)$.
  3. The worst case time complexity for both operations will be $\Omega (n)$.
  4. Worst case time complexity for both operations will be $\Omega (\log n)$
in DS by Loyal
edited by | 8.1k views
+8
A is the correct and becoz it is given efficient implementation is done so in case of circular queue they Can be implemented o(1) time
0
don't u people think B is the correct answer as it is mentioned specifically array, not circular array and efficiently means for every dequeue, elements have to be shifted one position to their leftside.
+1
Although, Circular queue implementation is memory efficient but as far as this question is concerned, answer is A in either case!
+1
Am I the only one who is not able to understand why everyone is using a circular linked list for implementation when array is mentioned.

Please let me know if I missed something.
+1

Circular array/LL is generally used for queues.

Even if you use simple arrays, you'd still get $O(1)$ for both the queue operations. Because to enqueue, we need to increment the rear and insert. To dequeue, we need to delete the front, then increment it. Both are constant-time operations.

It can be easily visualised that in a non-circular array, the initial indices of the array will be wasted as and when we dequeue. That's not space efficient.

In any case, Be it Linked Lists or Arrays, we'd get $O(1)$ time for both the operations (given that we have a head and tail pointer)

0

@ how is space wasted when dequeue is performed in non-circular array? We can make the value in front node as NULL, then make head point to the second node. So no space would be wasted.

The reason why circular linked list is preferred over singly linked list is that we need two pointers (for front and rear) in singly linked list, but circular linked list needs only one pointer (which acts like rear).

Linked List [check Circularly linked vs. linearly linked part]

3 Answers

+20 votes

The answer must be A).

 

by Active
+1
I feel answer is simple as we can add and remove an element from an array in O(1) time by using appropriate index number. To implement queue we can maintain a negative counter K which will decrease everytime we enqueue an element. And to dequeue we can use absolute value of n-k where n is number of elements in an array.
0

@Srinath Jayachandran

In your implementation, if we use normal array then,

here for dequeue, it well take o(1) time and for enqueue, it will take o(n) time.

But if we use circular array instead of normal array, the time taken in both the case will be o(1).

Am I right ?? 

0
is he right?
+3 votes
how can you take circular queue, in ques it is not given to implement queue efficiently.in ques given is that ENQUEUE and DEQUEUE operations are performed efficiently.

to implement any data structure array is best but size is fixed.bcoz enqueue and dequeue both take O(1) in worst case.

so ans should be A.
by Active
0
@rajoramanoj  

to perform enqueue and dequeue efficiently means  (here) .... implementation  of queue using an array  efficiently.but to implement  circular  queue at least 1 pointer is needed  . and how will we implement pointer here. . that is the question  .. so if u have some idea then pls do share
+2
if it is given in the ques to implement queue efficiently then we go with circular queue bcoz in linear queue eventhough space is available we can not store one more element further bcoz rear reached rightmost place and it cannot go back.

ans will remains same
0
we are not using pointer here, we are using mod function. suppose the size of array is 5, front is at index 0, and rear is at index 4. suppose after doing a deletion, front will shift to( present.index +1)mod(5) positon. similarly when we do insertion, rear will do same operation (present.index + 1)mod5, which will be equal to zero index.
+2 votes
Answer is A please refer this link I think it is best explanation I have found so far

https://www.sqa.org.uk/e-learning/ArrayDS02CD/page_14.htm
by Active
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,217 questions
59,907 answers
201,098 comments
118,144 users