Remove the last element in a queue

Question

I need to remove the last element of a queue. The only operations I may use are

• Peek() - get the first element without removing it
• Enqueue(element) - Insert an element to the back of the queue
• Dequeue() - Remove the first element
• IsEmpty() - true or false whether the queue is empty.

And I can't use arrays or queues, and the number of elements is not available.

I thought of some solutions, but each time I get stuck, since I don't know how to tell if the current element is the last element.

Solution 1

Justin Beal's solution is the more straight forward. But I think it can be done in place, without creating another queue.

object RemoveLast(Queue q) {
    object first = q.Peek();
    object current = null;
    while (true) {
        current = q.Dequeue();
        if (q.Peek() == first) {
            break;
        }
        q.Enqueue(current);
    }
    return current;
}

Solution 2

each time I get stuck since I don't know how to tell if the current element is the last element.

Good. Since you don't know of the "current" element is last, you do know of the "previous" element was last.

So, by saving the previous element, you should be able to handle this.

Solution 3

I had the same requirement so have created an extension method that others may use if their google reached here.

using System.Collections.Generic;
using System.Linq;

/// <summary>
/// Extensions for <see cref="System.Collections.Generic.Queue{T}"/>.
/// </summary>
public static class QueueExtensionsStatic
{
    /// <summary>
    /// Removes the last item from the <see cref="System.Collections.Generic.Queue{T}"/>.
    /// </summary>
    /// <typeparam name="T">Type of object in <see cref="System.Collections.Generic.Queue{T}"/>.</typeparam>
    /// <param name="q">Instance of <see cref="System.Collections.Generic.Queue{T}"/> to remove item from.</param>
    /// <returns>Item removed from the <see cref="System.Collections.Generic.Queue{T}"/>.</returns>
    public static T Pop<T>(this Queue<T> q)
    {
        for (var i = 1; i < q.Count; i++)
            q.Enqueue(q.Dequeue());

        return q.Dequeue();
    }

    /// <summary>
    /// Removes the last <see cref="quantity"/> item(s) from the <see cref="System.Collections.Generic.Queue{T}"/>.
    /// </summary>
    /// <typeparam name="T">Type of object in <see cref="System.Collections.Generic.Queue{T}"/>.</typeparam>
    /// <param name="q">Instance of <see cref="System.Collections.Generic.Queue{T}"/> to remove item from.</param>
    /// <param name="quantity">Number of items to pop off the end of the <see cref="System.Collections.Generic.Queue{T}"/>.</param>
    /// <returns>Item removed from the <see cref="System.Collections.Generic.Queue{T}"/>.</returns>
    public static IEnumerable<T> Pop<T>(this Queue<T> q, int quantity)
    {
        for (var i = quantity; i < q.Count; i++)
            q.Enqueue(q.Dequeue());

        var poppedItems = new List<T>(quantity);
        for (int i = 0; i < quantity; i++)
            poppedItems.Add(q.Dequeue());

        return poppedItems;
    }

    /// <summary>
    /// Adds an item(<see cref="T"/>) to the start of the <see cref="System.Collections.Generic.Queue{T}"/>.
    /// </summary>
    /// <typeparam name="T">Type of object in <see cref="System.Collections.Generic.Queue{T}"/>.</typeparam>
    /// <param name="q">Instance of <see cref="System.Collections.Generic.Queue{T}"/> to remove item from.</param>
    public static void Push<T>(this Queue<T> q, T item)
    {
        q.Enqueue(item);
        for (var i = 1; i < q.Count; i++)
            q.Enqueue(q.Dequeue());
    }

    /// <summary>
    /// Adds items(<see cref="T"/>) to the start of the <see cref="System.Collections.Generic.Queue{T}"/>.
    /// </summary>
    /// <typeparam name="T">Type of object in <see cref="System.Collections.Generic.Queue{T}"/>.</typeparam>
    /// <param name="q">Instance of <see cref="System.Collections.Generic.Queue{T}"/> to remove item from.</param>
    /// <param name="items">List of items(<see cref="T"/>) to add to the <see cref="System.Collections.Generic.Queue{T}"/>.</param>
    public static void Push<T>(this Queue<T> q, IEnumerable<T> items)
    {
        if (items == null || !items.Any()) return;

        foreach (var item in items)
            q.Enqueue(item);

        for (var i = items.Count(); i < q.Count; i++)
            q.Enqueue(q.Dequeue());
    }
}

Solution 4

I faced the same problem a couple days ago while implementing a similar requirement for my assignment. The simplest method to this problem i believe is looping through the queue and pushing the 'front' element to the back of the queue and 'pop' it , but when you reach the last element in the queue just 'pop' it and don't 'push' it.

View more solutions

Comments

[gli00001]

when q has only 1 element, stuck in loop

[gli00001]

Trinidad solution works fine when queue has more than 1 element,

[gli00001]

int size = q.size(); while (size-->0) { int current = q.poll(); if (size==0) { break; } q.offer(current); }

[Trinidad]

@gli00001 It will actually throw on Peek() because the queue is empty. So the break condition should be something like (q.Count == 0 || q.Peek() == first)

[gli00001]

in java, it does not throw, regardless of language specific implementation for peek(), how about: int size = q.size(); while (size-->0) { int current = q.poll(); if (size==0) { break; } q.offer(current); }

[Trinidad]

@gli00001 This was intended for C# where it throws when empty but yep, counting the items look good for me, too, as the idea (as you probably realize and for the benefit of other readers) is to remove and add back all items except for the last one.