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

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

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

Ответ 1

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

Если вы поместите элементы из того же конца добавляемого списка, вы внедрили стек или структуру данных Last-In-First-Out (LIFO):

Если вы поместите элементы с противоположного конца, вы внедрили очередь - хотя обычно терминология - это "enqueue" и "dequeue". Это структура данных First-In-First-Out (FIFO):

Ответ 2

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

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

Ответ 3

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

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

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

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

Что касается того, почему pop вызывается, а не тянуть (против нажимать)... хороший вопрос.

Ответ 4

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

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

Ответ 8

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

Ответ 9

Нажатие просто добавляет элемент в начало (или конец) коллекции. Popping удаляет тот же элемент.

В Java интерфейс списка добавляет (0, элемент) и удаляет (0). Это фактически параллели для push (item) и pop().

Однако push и pop и стеки интересны в своем конкретном поведении, и, следовательно, у многих есть специализированные структуры данных, которые делают толкание и выскакивание особенно эффективными.

Ответ 10

Большая часть того, что вы просите, - это соглашение. Для очередей вы можете нажать или поставить в очередь. Вы увидите и то, и другое. Для стеков вы увидите добавление или толчок. Для этого нет реального жесткого "правила". Если вы работаете на языке, который использует "push" в качестве условного обозначения, используйте "push". Именование имеет значение, но только для удобства использования и здравого смысла. Просто убедитесь, что ваше именование согласовано внутри одного приложения или системы.

Ответ 11

Имена push и pop используются при разговоре о стеках. Стеки являются последними в списке (LIFO). Таким образом, имена указывают, что pop вернет последнее нажатое.

Ответ 12

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

Эта интуиция может быть представлена как абстрактная алгебра, с Push и Pop, представляющими любые вычисления на объекте данных, называемом Stack с участием 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 и т.д.

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

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

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

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

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

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

Жаль, что мы не делаем этого в документальном коде.

Ответ 13

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