0
$\begingroup$

I have this problem I'm trying to solve: Implement a queue with a constant number of stacks so that each queue operation takes a constant (worst-case) number of stack operations.

I don't want assistance with the answer, but i do need help understanding the last part of requirements - "so that each queue operation takes a constant (worst-case) number of stack operations".

Does this mean that, given such a queue with n elements and another with n+1 elements, the number of stack operations will be the same, when enqueueing or dequeueing either one? What does "worst-case" mean when dealing with a queue?

Also, with a question like this, is it implied that queues are the only data-structures needed and one would not need to introduce any additional data structures to reach a solution?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I believe the question is asking you to implement the queue so that every time you perform a queue operation (enqueue or dequeue) your implementation does O(1) total operations on the stacks used to implement this. For example, an implementation that performed at most 137 total pushes and pops per time that the client calls enqueue or dequeue would satisfy this requirement, but an implementation that requires, say, $n$ stack operations per enqueue would not meet this requirement.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for responding. With the 137 total push-pop implementation in your example, would that be a maximum of 137 regardless of how many items are in the stack at the time? $\endgroup$
    – Julian A.
    Commented Mar 5, 2016 at 22:06
  • 1
    $\begingroup$ Yes, that's exactly right. $\endgroup$
    – templatetypedef
    Commented Mar 5, 2016 at 23:44
  • $\begingroup$ Cool. Thanks! If you answer the last question in the post (I added it as a later edit), I'll mark your response as the accepted answer. $\endgroup$
    – Julian A.
    Commented Mar 6, 2016 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.