How to remove a middle element from queue

algorithmsdata structuresqueue

I had a question, about how to remove an element from middle of the queue , without disturbing the order of other elements.

E.g.

Queue before operation:- <| a b c d e |<

Queue after operation:- <| a b d e|<

Note:- I know the generic way of removing a,b and inserting on queue again, followd by d and e.
But I Need a more faster and efficient way.

Best Answer

Queues are generally considered to be an abstract data type that only has enqueue and dequeue operations. So in the general case, we can't use any other functions.

Let's look at the case of a FIFO queue that only supports these two operations and additionally has a size property. Getting and removing the middle element is trivial by also removing all earlier elements:

val q: Queue[Item] = ...;
val half_size: Int = q.size / 2;

var result: Item = null;
while (q.size > half_size) {
    result = q.dequeue();
}

But replaying the removed items in the correct order requires us to remove all elements, since we cannot push items back onto the end! We have to do something like this:

val q: Queue[Item] = ...;
val temp: Queue[Item] = new Queue();
val half_size: Int = q.size / 2;

var result: Item = null;
while (q.size > 0) {
    val item = q.dequeue();
    if (q.size == half_size) {
        result = item;
    } else {
        temp.enqueue(item);
    }
}

while (temp.size > 0) {
    q.enqueue(temp.dequeue());
}

Of course, this only works if the input queue is not changed while this algorithm is executed.

For LIFO queues (i.e., stacks), we only have to remove half of the elements as we can replay the items in the correct order. For a stack, we usually call enqueue push and dequeue pop.

val q: Stack[Item] = ...;
val temp: Stack[Item] = new Stack();
val half_size: Int = q.size / 2;

var result: Item = null;
while (q.size > half_size) {
    result = q.pop();
    temp.push(result);
}

while (temp.size > 0) {
    q.push(temp.pop());
}

Some implementations of queues are actually fully-featured linked lists (e.g. in Java, the java.util.LinkedList fulfils the java.util.Queue interface). If we have access to such implementation details of a queue, we can splice out the element more easily. So if we have a LinkedList rather than a Queue, we can simply list.remove(indexOfTheMiddleElement). Depending on what language you are using, you may be able to take some shortcuts.

Related Topic