Удалить последний элемент в очереди

Question

Извините, если мой вопрос не относится к этому сайту.

Мне нужно удалить последний элемент очереди.Единственные операции, которые я могу использовать, это Peek () - получить первый элемент, не удаляя его, Enqueue (элемент) - вставить элемент в конец очереди, Dequeue () - удалить первый элемент, а IsEmpty () - true или falseпуста ли очередь.И я не могу использовать какие-либо массивы или очереди, чтобы помочь мне, и количество элементов не доступно.

Теперь, я думал о некоторых решениях, но каждый раз я застреваю, так как я не знаю, каксказать, является ли текущий элемент последним.

Заранее спасибо.И еще раз, извините, если это не подходящее место для вопросов такого типа.

Answer 1

Решение Джастина Била более прямолинейно.Но я думаю, что это можно сделать на месте, не создавая очередную очередь.

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;
}

Answer 2

каждый раз, когда я застреваю, так как не знаю, как определить, является ли текущий элемент последним.

Хорошо. Поскольку вы не знаете, что «текущий» элемент является последним, вы do знаете, что «предыдущий» элемент был последним.

Итак, сохранив предыдущий элемент, вы сможете справиться с этим.

Answer 3

Примерно так будет работать:

public Queue removeLast (Queue queue1) {

Queue queue2 = new Queue();

while(!queue1.isEmpty()){
  Object o = queue1.dequeue();
  if(!queue1.isEmpty()){
    queue2.enqueue(o);
  }
}
return queue2;

}

Answer 4

У меня было такое же требование, поэтому я создал метод расширения, который другие могут использовать, если их гугл достигнет здесь.

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());
    }
}

Answer 5

Я столкнулся с той же проблемой пару дней назад, когда выполнял аналогичное требование для своего задания. Я полагаю, что самый простой способ решения этой проблемы - это циклически проходить по очереди и помещать элемент front в конец очереди и «выталкивать» его, но когда вы достигнете последнего элемента в очереди, просто «вытолкните» его и не нажимайте толкни его.

Answer 6

Я прошел через решение, предоставленное Тринидадом, которое до сих пор является самым популярным ответом. Я полагаю, что это решение прекрасно работает, только если первый элемент / объект в очереди является уникальным. Если обнаружен какой-либо дубликат первого элемента / объекта, он не может указать правильный элемент в качестве последнего элемента.