1

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
  • 1
    There are a lot of method, dependig by your algorithms. – Francesco Irrera Jan 20 '15 at 10:48
  • 5
    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
3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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