Какие реальные применения объекта «Стек» (.Net) вы использовали - PullRequest
10 голосов
/ 13 января 2010

Мы все читали или слышали о классе стека, но многие из нас, вероятно, никогда не находили причину использовать объект LIFO. Мне любопытно услышать о реальных решениях, которые использовали этот объект и почему.

http://msdn.microsoft.com/en-us/library/system.collections.stack.aspx

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

У кого-нибудь еще есть примеры?

Ответы [ 10 ]

17 голосов
/ 13 января 2010

Я использовал их для отслеживания действий отмены и повтора.

Я использую интерфейс примерно так:

interface ICommand
{
    void Execute();
    void Undo();
    string Description { get; }
}

Отменить и повторить оба типа Stack<ICommand>. Затем я создаю конкретный класс для данного действия. В конструкторе класса я передаю любую информацию, которую мне нужно сохранить. Execute выполняет действие изначально, а также повторяет его; Undo отменяет это, очевидно. Это работает так:

  • Отмена действия: вытолкните стек отмены и добавьте его в стек восстановления.
  • Повторить отмененное действие: вытолкните стек возвратов и снова добавьте его в стек отмены.
  • Выполните новое действие: добавьте в стек отмены и очистите стек возвратов (поскольку состояние больше не соответствует).

Я обнаружил, что вы должны позаботиться о том, чтобы действительно отменить то, что было сделано. Например, скажем, у вас есть пользовательский интерфейс с двумя списками, и у каждого есть пять элементов. Ваше действие может состоять в том, чтобы нажать кнопку, чтобы переместить все в левом списке в правый список (теперь у него десять, а в левом списке ноль).

Действие отмены не , чтобы переместить все назад; действие отмены состоит в том, чтобы отодвинуть только те пять, которые вы на самом деле переместили, и оставить остальных.

7 голосов
/ 13 января 2010

Стеки используются всякий раз, когда хранимая процедура / подпрограмма вызывается для хранения локальных переменных и адреса возврата.

Стеки используются для оценки выражений (например, в калькуляторе или в вашем компиляторе), сначала выражение преобразуется в RPN , затем для оценки используется простая машина стеков. Это работает следующим образом, когда вы видите операнд, помещающий его в стек. Когда вы видите операторы, поп-операнды и оценки.

example

5 6 + 3 *

steps-
 see 5 push 5
 see 6 push 6
 see + pop 2 times and apply + get 11 push 11
 see 3 push 3
 see * pop 2 times and apply get 33 push 33

result is on the top of the stack.   
5 голосов
/ 13 января 2010

Если у вас есть рекурсивный алгоритм, вы, как правило, можете переписать их, используя стек. (поскольку рекурсивные алгоритмы неявно уже используют стек)

3 голосов
/ 13 января 2010

Вы можете проверять строковые входы, которые требуют сбалансированных токенов. Подумайте ЛИСП:

(+ (- 3 2) (+ (+ 4 5) 11))

Когда вы нажмете на открывающую пару:

stack.Push("(")

Затем, когда вы нажмете на закрывающую скобку:

stack.Pop()

Если в вашем стеке остались жетоны, когда вы закончите, он не сбалансирован.

Вы можете придумать и проверить правильность вложенности во входных данных, таких как HTML. В очень надуманном примере:

//see opening body
stack.Push("body")

//see opening div
stack.Push("div")

//see opening p
stack.Push("p")

///see closing div
if(!stack.Pop().Equal("div")){
    //not balanced
}
1 голос
/ 13 января 2010

В одном реальном использовании класс генератора postscript имеет состояние «current_font», используемое в качестве шрифта для любых операций, которые рисуют текст. Иногда функции необходимо временно установить шрифт, но затем вернуть его к тому, что было. Мы можем просто использовать временную переменную для сохранения и восстановления шрифта:

def draw_body
  old_font = ps.get_font
  ps.set_font('Helvetica 10')
  draw_top_section
  draw_bottom_section
  ps.set_font(old_font)
end

Но в третий раз, когда вы это сделаете, вы захотите перестать повторяться. Итак, давайте позволим объекту ps сохранить и восстановить шрифт для нас:

class PS

  def save_font
    old_font = get_font
  end

  def restore_font
    set_font(old_font)
  end

end

Теперь абонент становится:

def draw_body
  ps.save_font
  ps.set_font('Helvetica 10')
  draw_top_section
  draw_bottom_section
  ps.restore_font
end

Это прекрасно работает, пока мы не используем тот же шаблон внутри одной из подпрограмм, вызываемых draw_page:

def draw_top_section
  ps.save_font
  ps.set_font('Helvetica-bold 14')
  # draw the title
  ps.restore_font
  # draw the paragraph
end

Когда draw_top_section вызывает "save_font", он перекрывает шрифт, который был сохранен draw_page. Пришло время использовать стек:

def PS

  def push_font
    font_stack.push(get_font)
  end

  def pop_font
    set_font(font_stack.pop)
  end

end

А в звонящих:

def draw_top_section
  ps.push_font
  ps.set_font('Helvetica-bold 14')
  # draw the title
  ps.pop_font
  # draw the body
end

Возможны дальнейшие усовершенствования, такие как автоматическое сохранение и восстановление шрифта в классе PS, но не обязательно заходить в них, чтобы увидеть значение стека.

1 голос
/ 13 января 2010

Я использовал стеки для обработки изображений, где «язык обработки» должен быть указан в URL. Основанная на стеке форма позволяет вам представлять дерево операций в простой для анализа, легкой для понимания форме.

См:

http://www.hackification.com/2008/10/29/stack-based-processing-part-1/

и

http://www.hackification.com/2008/10/29/stack-based-processing-part-2/

0 голосов
/ 29 июня 2016

В классе компьютерной графики (не .NET) мы использовали Stack для отслеживания объектов, которые были нарисованы на экране. Это позволило перерисовывать все объекты на экране для каждого обновления, а также отслеживать порядок или «z-слой» каждого объекта, чтобы при перемещении они могли перекрывать другие объекты.

0 голосов
/ 13 января 2010

Чтобы дать конкретный пример, чтобы осветить то, что другие люди комментируют: для реализации интерпретатора Z-machine нужно использовать три разных стека. Стек вызовов и пара различных типов стеков объектов. (Конкретные требования можно найти здесь . ) Обратите внимание, что, как и во всех этих примерах, хотя использование стека не является строго обязательным , это очевидный выбор.

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

0 голосов
/ 13 января 2010

Вот реализация глубокого сравнения, где стек используется для отслеживания пути к текущему сравниваемому объекту.

C # реализация глубокого / рекурсивного сравнения объектов в .net 3.5

Я также использовал его в похожих кодах, работающих с генерацией операторов xpath для определенных узлов xml.

0 голосов
/ 13 января 2010

Я нахожу стеки весьма полезными в многопоточных приложениях для отслеживания статусов в обратном порядке времени ...

Каждый поток помещает сообщение о состоянии в синхронизированный общий стек, и у вас есть своего рода «хлебная крошка»"из того, что произошло.

Не совсем .NET, но ... это мое мнение =)

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...