Data structures and algorithms
You implement a queue with two stacks: push onto the inbox, and pop from the…
AppliedMultiple choice
You implement a queue with two stacks: push onto the inbox, and pop from the outbox, refilling it from the inbox when it is empty. What is the cost of each dequeue?
- A every time, because elements are moved between stacks
- BAmortised , worst case
- C, as for a balanced tree
- D in the worst case for every operation
The worked solution is in Premium
The answer, the full working and the one idea to take away – for this and all 1,322 questions in the bank. Answer it in practice and your working is marked, with a known mistake named when you make one.
Report an issue with this question
Learn the method
Of the kind reported at
More data structures and algorithms questions
- You insert 1,000 keys into a hash table with 1,000 buckets using a uniform hash.Applied · Premium
- When does a hash map lookup degrade to linear time?Applied · Premium
- You need the 100 largest values from a stream of 10⁹ numbers you cannot store.Foundation · Free solution
- What does the recurrence T(n) = 2T(n/2)+O(n) solve to?Applied · Free solution
- What does the recurrence T(n) = 4T(n/2)+Θ(n²) solve to?Applied · Premium
- A dynamic array starts with capacity 1 and doubles when full, copying all elements.Applied · Premium