2

Доброго времени суток, пытаюсь реализовать очередь через массив, на сайте MSDN говорится что при добавлении нового элемента емкость должна автоматически увеличиваться, изначальная длина массива у меня равна 0:

public string[] data = new string[0]; 

А в методе добавления элемента, для увеличения емкости массива я использую Array.Resize:

public void Add(string str)
        {
            Array.Resize(ref data, data.Length + 1);

            for (int i = data.Length - 1; i > 0 ; i --)
            {
                data[i] = data[i - 1];
            }

            data[0] = str;
        }

В этом методе я сначала увеличиваю длину массива - Правильно ли я делаю и может быть есть какой-нибудь другой способ ? затем я подвигаю се элементы справа - налево и первым элементом ставлю новый, удалять я буду с другой стороны ? Подскажите пожалуйста, правильно ли я реализовываю(пытаюсь реализовать) очередь через массив? Есть ли какой - нибудь другой способ увеличивать длину массива или так тоже хорошо ? И нужно ли уменьшать длину массива при удалении элемента из очереди ?

4
  • 2
    Для очередей есть готовые реализации - FIFO - System.Collections.Generic.Queue<T> и FILO - System.Collections.Generic.Stack<T>. Они вас не устраивают?
    – Monk
    19 июн 2016 в 16:56
  • @Monk вполне устраивают, просто моему знакомому задание такое при приеме на курсы давали, реализовать массив, который будет вести себя как очередь, вот мне и интересно стало сделать такое.
    – Uladz Kha
    19 июн 2016 в 17:23
  • Ну, если вам не удалось нагуглить лучший способ увеличить размерность массива то наверное этот единственный. А вообще я б на вашем месте глянул как клаcc очереди реализован в .Net (глянуть можно декомпилятором ) и сравнил бы с тем, что получилось у вас.
    – Alexey
    19 июн 2016 в 18:01
  • 3
    Есть не то что другой, а более эффективный, в котором потребуется меньше операций, лучше посмотрите стандартную реализацию, github.com/dotnet/corefx/blob/master/src/System.Collections/src/… 19 июн 2016 в 18:31

1 ответ 1

4

Чтобы не двигать все элементы, имеет смысл рассматривать ваш массив как кольцевой буфер.

Для этого вы должны знать его длину, текущий индекс начала и индекс конца данных. При удалении элемента из начала вы просто увеличиваете индекс начала данных. При добавлении элемента в конец, если индекс конца ещё можно увеличить, не залезая за конец массива, то вы его увеличиваете, иначе «зацикливаете» данные, делая индекс конца нулём. Только в случае, тогда индекс конца начинает «залезать» на начало, понадобиться увеличивать размер несущего массива, и копировать данные.


Как подсказывает @rdorn, если вы увеличиваете несущий массив, имеет смысл увеличивать не на один элемент, а сразу на несколько. Например, на фиксированный процент текущего размера. Или можно придумать более изощрённую стратегию.

5
  • 1
    и при увеличении - делать это с заделом на будущее, а не каждый раз на 1. Причем фактор роста можно сделать динамическим в обратной пропорциональности к размеру имеющегося, т.к. 10% от 100 и 100кк это совсем разные 10%
    – rdorn
    22 июн 2016 в 23:51
  • @rdorn: Точно. Queue<T>, кстати, увеличивает каждый раз вдвое, но не меньше, чем на 4: referencesource.microsoft.com/#System/compmod/system/…
    – VladD
    22 июн 2016 в 23:55
  • кстати в довесок одна из возможных хитрых стратегий может быть такой: у нас есть ограничение на размер массива, достаточно большое, но есть, даже на х64. Возьмем разность верхнего предела и текущего размера, разделим на верхний предел, добавим 1 и получим коэффициент на который нужно умножить текущий размер. При этом без риска на очередном шаге словить OutOfMemoryException. Актуально для быстро растущих больших массивов. На малых массивах или с заведомо медленным ростом можно обойтись фиксированным ростом
    – rdorn
    23 июн 2016 в 0:20
  • Спасибо за Ваш ответ, позже я сделал коэффициент capacity равный двум и после добавления элемента проверял, если последний элемент != null увеличиваю размер массива в два раза. У меня возник вопрос, если Вам не сложно ответить, а как сделать из того что у меня "есть" generic, я читал примеры, нужно унаследовать класс от ienumerble class myQueue<T> : ienumerble , но для чего такое делать и как правильно класс должен выглядеть ?
    – Uladz Kha
    23 июн 2016 в 7:05
  • 1
    @VladimirKhodakovskey: Вам нужно написать что-то вроде class Queue<T> (ну и если хотите, class Queue<T> : IEnumerable<T>), и заменить внутри класса string на T по большому счёту.
    – VladD
    23 июн 2016 в 8:09

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.