World's most popular travel blog for travel bloggers.

Which of these simple data structures is most efficient when implementing a Dequeue?

, , No Comments
Problem Detail: 

A deque is a double ended queue of course. So if I can either use 2 stacks, or 2 queues, or 1 stack and 1 queue, which two would I use to have the fastest implementation? Can we derive the complexity for InsertLeft, InsertRight, and RemoveLeft, and RemoveRight?

I was thinking of using 2 stacks. Call 1 stack 'left' and the other 'right'. All operations are now order O(1) because if InsertLeft inserts items at stack called 'left' and InsertRight inserts in stack called 'right'. Both stacks maintain the front and the end of the sequence respectively. Am I correct?

Asked By : learnerX
Answered By : gardenhead

We need to clearly separate interface interfaces (abstract data types) from implementation. You talk about implementing a deque, an ADT, in terms of a stack or queue, but those are themselves ADTs. We need to be talking about concrete implementations.

So here's the answer (drumroll please): use a doubly-linked list. All the operations you mentioned are now $O(1)$.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback