Наиболее эффективный способ реализации данного стека

Question

Я имею в виду спецификацию стека, которая ---> * Может смотреть на объект, который имеет самое высокое (или самое низкое или около того) значение. * Каждый объект в стеке будет сопоставимым.

Я бы хотел выполнить следующие операции как можно быстрее

1. Пустой толчок (E e);

2. void pop (E e);

3. E peekMidElement (); [Размер () / 2) +1] 1015 *

4. E peekHighestElement ();

5. E peekLowestElement ();

6. int size ();

Эффективность должна быть в центре. Какой будет рекомендуемый путь? Идеи приветствуются.

РЕДАКТИРОВАТЬ: Все методы, которые будут вызываться так часто. Кроме того, имеет значение эффективность времени.

Answer 1

Одним из способов может быть реализация стека с использованием массива.Однако это накладывает ограничение на количество элементов в стеке (т. Е. Максимальный размер массива ограничен).Также вам может понадобиться выделить место для массива (вы можете использовать магию realloc для повторного увеличения размера массива, если он увеличивается больше)

Преимущество реализации массива в том, что ... вы будетедолжны отслеживать одну переменную, которая будет вершиной стека.А промежуточная точка - это просто индекс в массиве.

Надеюсь, это поможет

Push: верхняя переменная указывает индекс в массиве, где находится верхний элемент ... при выполнении push... просто сохраните значение в следующем элементе после top (конечно, после выполнения проверки пределов) .. и затем вы можете увеличить значение top

Pop: декремент top ... вернуть значение в(top + 1)

PeekMiddle: всегда будет массив [top / 2]

PeekHighest: всегда будет массив [top]

PeekMiddle: будетвсегда быть массивом [0]

Размер: возвращаемая вершина

Все вышеперечисленные операции являются O (1)

Answer 2

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

1. Нажмите на правый конец массива. Если вы превышаете емкость массива, вы можете выделить новый массив, скопировать все элементы и удалить предыдущее распределение. Об этом автоматически заботятся некоторые контейнерные классы на основе массива в большинстве языков. Однако есть способы избежать большей части этого копирования при расширении емкости вашего стека, что может привести к потере эффективности при выполнении какой-либо другой операции.

2. Если вы поддерживаете индекс для отметки следующей вставки (то есть push (E e)), pop () может быть реализован так же просто, как «-;».

3. peekMiddle () будет просто элементом (size / 2) -го индекса. Я надеюсь, что вы не ищете среднее значение вместо этого.

4. Для peekLowest () простое решение состояло бы в том, чтобы поддерживать стек минимумов, то есть когда вы помещаете значение в стек, если это новый минимум, также помещайте его в стек минимумов. Таким образом, самое верхнее значение в вашем стеке минимумов будет ответом на peekLowest (). Конечно, когда вы извлекаете значение из исходного стека, если оно является минимальным значением (как задано peekLowest ()), извлекайте его также из стека минимумов. Аналогичный подход можно использовать для peekHighest ().

В этой простой реализации вы сможете получить время выполнения O (1) для всех операций. Для толчка (E e) O (1) - амортизированное время работы.

Answer 3

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

С другой стороны, если вы не знаете верхнюю границу размера стека или если размер стека обычно будет небольшим по сравнению с верхней границей, используйте список с двойной связью, как описано ниже. Опять же, все шесть операций являются O (1). Хранение на элемент является оптимальным, если стек работает около минимального размера - у вас не будет большого пространства неиспользуемого массива. Обратите внимание, что выделение памяти, показанное ниже как «новые» и «свободные», может состоять из вызовов malloc () и free () или может быть некоторым распространенным методом ограничения накладных расходов с использованием пула доступных узлов.

Пусть H указывает на начало списка, T на хвост и M на середину. (M может поддерживаться во времени O (1) на изменение, как показано ниже.) Инициализируйте размер списка s = 0 и средний счет m = 0.

Для ваших операций 1-6:

1. Пустой толчок (E e):
   Создайте новый узел X со значением e; ++ s; если (s == 1) установить H = T = M = X и установить ссылки, иначе {приложить X в H; установить H = X; если m <(s / 2 + 1), то {++ m и установите M = M.next}}. </p>

2. void pop (E e): если s <1, вернуть ноль или ошибку; else {получить значение e = He для возврата, установить H = H.next, отсоединить и освободить H.prev, --s, если (s == 0) H = T = M = null, если m> (s / 2 +1) затем {--m и установить M = M.prev}}.

3. E peekMidElement (); [size () / 2) +1]: если M, вернуть M.e, иначе null

4. E peekHighestElement (): если H, вернуть H.e (или T.e?), Иначе null

5. E peekLowestElement (): если T, вернуть T.e (или H.e?), Иначе null

6. int size (): Return s

Я не знаю, какой конец стека "Высокий"; Вы видите это как взросление или падение? В любом случае, просто исправьте ops 4 и 5, как хотите, и измените имена на peekHeadElement или peekFirstElement и т. Д.

Answer 4

«Эффективность» слишком общая, особенно перед лицом 6 методов?КПД процессора?След памяти?Каждая функция вызывается одинаковое количество раз?Насколько велик стек в среднем?

В целом, я бы сказал, что односвязный список будет хорошей идеей, если предположить (как это кажется правдоподобным), что size и peekMidElement aren 'т часто называют.