Programming and Data Structures · Stacks and Queues · 2 marks · Multiple choice
Along with Enqueue/Dequeue, a queue supports MultiDequeue(Q), which sets m=k and repeatedly Dequeues while Q is nonempty and m>0, decrementing m. For an initially empty queue, find worst-case total time for any sequence of n such operations.
Each removed item must have been enqueued earlier, so across the whole sequence at most n individual removals occur, regardless of k. Each operation adds only constant overhead apart from those removals. Thus total time is O(n), and n enqueues attain Ω(n), giving Θ(n), A.