Как определяются push () ing и pop () ping?

Question

Я знаю, как работают методы push () и pop () в типичной реализации очереди / связанного списка, но я хочу знать, что вы на самом деле определяете как push или pop? Когда вы можете назвать метод push () / pop ()? Что делает метод insert () / add () в типичной реализации Tree не push ()?

Насколько я понимаю, push () ing означает размещение чего-либо в позиции, на которую указывает специальный указатель, а pop () ping элемента означает удаление некоторого объекта, на который указывает указатель, но это не так. четко определены. Или имя имеет значение вообще?

Answer 1

Обращаясь к операциям в связанном списке, вы можете добавить элементы в список, чтобы добавить их. Затем вы можете удалить элементы из списка, чтобы удалить их.

Если вы извлекаете элементы из того же конца списка, в котором вы их добавили, вы реализовали стек или структуру данных «последний пришел-первый-вышел» (LIFO):

Если вы выталкиваете элементы с противоположного конца, то вы реализуете очередь - хотя обычно это термины «ставить в очередь» и «убирать из очереди». Это структура данных «первым пришел - первым обслужен» (FIFO):

Answer 2

Термины push и pop обычно используются для стеков , а не очередей или связанных списков . Стек - это структура данных «последний пришел - первым вышел» (LIFO); другими словами, первое, что нужно удалить, это элемент, который был добавлен последним. Пуш - это когда вы кладете новый предмет в стек, а поп - когда вы его снимаете.

Многие языки программирования позволят вам писать свой код любым удобным вам способом, включая использование имен push и pop для любой структуры данных, даже если это не то, что вы действительно делаете. Тем не менее, я бы не рекомендовал это. Гораздо лучше использовать термины, которые используют другие, чтобы ваш код мог быть прочитан другими программистами. Кроме того, использование неправильной терминологии может затруднить получение работы и затруднит общение с другими программистами, если вы работаете над проектом (работа или открытый исходный код).

Answer 3

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

Когда дело доходит до очередей , вы, как правило, должны вместо этого использовать термины постановка в очередь и снятие очереди , где первое означает добавление элемента в конец очереди end ", а последний означает удаление элемента из" front end "из очереди.

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

Когда дело доходит до связанных списков и двусторонних очередей (запросов) , также используются термины push и pop например, в ST ++ C ++, где у вас есть такие операции, как push_front, push_back, pop_front и pop_back. Это просто означает, что элементы могут быть добавлены или удалены на обоих концах.

---

Почему pop называется так, а не pull (против push ) ... хороший вопрос.

Answer 4

Push и pop изначально использовались для обозначения операций стека, но неофициально эти термины часто используются для операций, которые включают добавление / удаление элемента в конце любой линейной структуры данных, такой как стек, очередь, массив или связанный список.

Answer 5

Имена push и pop , вероятно, были изобретены просто для того, чтобы отличить операции, которые могут быть выполнены в стеке, от операций, которые можно выполнять в списке. Вы также можете назвать их add и remove , но это, как правило, подразумевает, что вы можете добавить или удалить элемент в любом месте списка, а не просто в начале (или в конце, если ты так думаешь). Аналогично, enqueue и dequeue существуют, потому что push и pop подразумевают, что вставки или удаления происходят в одном и том же месте, а не в противоположном Концы списка.

Если вам нужно техническое определение, вы, вероятно, можете сказать, что push и pop являются операциями O (1), которые влияют на один и тот же конец списка в LIFO (Last In , First Out) образом.

Answer 6

Push и Pop - это просто условные имена, назначаемые операциям вставки и удаления элементов из структуры данных стека. Любые операции, которые следуют шаблону «последний пришел - первым вышел» (LIFO), обычно называются Push and Pop, но они могут называться как угодно.

Answer 7

По крайней мере, в C ++ push и pop относятся только к структурам, таким как стеки и очереди, где расположение, в котором выполняется операция, присуще структуре данных. Для других контейнеров, таких как векторы и списки, у нас есть push_back, push_front, pop_back и т. Д. Для контейнеров, где мы на самом деле не знаем, где будет находиться элемент или откуда мы будем его читать, push и pop не используются в все.

Answer 8

Push / Pop изначально относились к командам стека в asm land. Нажатие помещает значение (регистр) в стек и обновляет указатель стека, в то время как поп-функция берет значение из стека и уменьшает указатель. Здесь нет вставки, которая означала бы существование какого-либо смещения. Вот почему у вас также есть функции push / pop _front () и push / pop _back (). Они представляют собой статическое местоположение для push / pop для работы.

Answer 9

Основной операцией стека является push и pop. Термин push используется для помещения некоторого элемента данных в стек, а pop - для удаления некоторого элемента данных из стека.

Answer 10

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

Эта интуиция может быть представлена ​​как абстрактная алгебра , где Push и Pop представляют любые вычисления в объекте данных, называемом стеком, включающим ELements:

algrebra Stack
  {
    data Stack;
    data Element;
    Empty() -> Stack;
    Push(Stack,Element) -> Stack;
    Pop(Stack) -> Stack;
    Top(Stack) -> Element;
    axiom Top(Push(s,e))==e;
    axiom Pop(Push(s,e))==s;
    axiom Pop(Empty())==undefined;
 }

Что этоговорит, что если вы можете найти сущности в вашей системе,

• некоторые из которых вы утверждаете, являются типами стеков
• некоторые из которых вы утверждаете, что элементы,
• некоторыеэто функции, которые вы называете Push,
• некоторые функции, которые вы называете Pop, Top, Empty и т. д.

тогда сигнатуры различных функций совпадают с сигнатурами валгебра, и что если вы применяете различные функции, они будут вести себя так, как указывают аксиомы.(Выбранные вами объекты «изоморфны» алгебре).

Преимущество этой точки зрения состоит в том, что она говорит ничего о реализации различных сущностей, в то же время сохраняя сущность.Эта алгебра охватывает различные артефакты, описанные в других ответах;должно быть ясно, что линейная область хранения, используемая в качестве стека, является стеком, что связанный список, использующий стек, является стеком, что дека, используемая одним концом, является стеком, что серия дисковых блоков, используемых в качестве стека, является стеком, ...

Что действительно круто, так это то, что вы можете переименовывать все типы данных и функции внутри алгебры стека, и при этом все равно распознавать стек, потому что переименование не влияет на изоморфизмы (потому что согласованное переименование - это просто еще одноизоморфизм, и изоморфизмы составляют произведение изоморфизмов).Все, что соответствует этой спецификации , является стеком!

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

Так что я бы сказал, что вы можете называть свое имя своими функциями реализации как угодно, но называйте их Push и Pop, если их действия понимают это.алгебра.

Итак, можно определить стек по формальной спецификации.Таким же образом вы можете определить любую другую структуру данных.

Жаль, что мы не делаем больше этого при документировании реального кода.