Aspire's Library
A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
A double-ended queue (deque) supports adding and removing items from both ends of the queue. The operations supported by deque are AddFront, AddRear, RemoveFront and RemoveRear. You are given only stacks to implement this data structure. You can implement only push and pop operations. What is the time complexity of performing AddFront() and AddRear() assuming $m$ is the size of the stack and $n$ is the number of elements?
Solution
Using stack operations, insertion at front can be done directly by push operation.So, AddFront takes:
$O(1)$
But insertion at rear needs moving elements because stack allows insertion only at top.
So, AddRear may require shifting $n$ elements.
Therefore, AddRear takes:
$O(n)$
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Ask Your Question or Put Your Review.
