# How to remove a middle element from queue?

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.

• You can use an index that contain the position of each element, and after if you want delete an element you use his position v(i). – Francesco Irrera Jan 20 '15 at 10:46
• There are a lot of method, dependig by your algorithms. – Francesco Irrera Jan 20 '15 at 10:48
• If you need to perform operations on elements in the middle, you need a List, not a Queue. It's conceptually wrong to do otherwise. – Neil Jan 20 '15 at 11:39

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.