Я знаю, как работают методы push() и pop() в типичной реализации Queue/Linked List, но то, что я хочу знать, это то, что вы на самом деле определяете как push или pop? Когда можно назвать метод push()/pop()? Что делает метод insert()/add() в типичной реализации дерева не push()?
Мое понимание заключается в том, что push() ing означает помещение чего-то в позицию, на который указывает какой-то специальный указатель, и pop() ping-элемент означает, что какой-то объект указывает на некоторый указатель, но он, похоже, не является четко определен. Или вообще имеет дело с именованием?
При обращении к операциям в связанном списке вы можете вставлять элементы в список, чтобы добавить их. Затем вы можете удалить элементы из списка, чтобы удалить их.
Если вы поместите элементы из того же конца добавляемого списка, вы внедрили стек или структуру данных Last-In-First-Out (LIFO):
Если вы поместите элементы с противоположного конца, вы внедрили очередь - хотя обычно терминология - это "enqueue" и "dequeue". Это структура данных First-In-First-Out (FIFO):
Термины push и pop обычно используются для стеки, а не очереди или связанные списки. Стек - это структура данных последнего времени (LIFO); другими словами, первое, что нужно удалить, - это элемент, который недавно был добавлен. Нажатие - это когда вы кладете новый элемент в стек, а поп - когда вы его снимаете.
Многие языки программирования позволят вам писать свой код любым способом, в том числе используя имена push и pop для любых структур данных, даже если это не то, что вы действительно делаете. Однако я бы не рекомендовал его. Намного лучше использовать термины, которые другие используют, чтобы ваш код мог быть прочитан другими программистами. Кроме того, использование неправильной терминологии может затруднить получение работы и затруднит общение с другими программистами, если вы работаете над проектом (работа или с открытым исходным кодом).
Нажатие означает помещение элемента в стек (структура данных), так что он становится элементом самого верхнего стека. Popping означает удаление самого верхнего элемента из стека. (Вы часто слышите третий термин peeking, что означает просмотр/чтение самого верхнего элемента.)
Когда дело доходит до очередей, вы обычно должны использовать термины enqueueing и dequeueing, где первое означает добавление элемента в очередь "назад" и последний означает удаление элемента из "переднего конца" из очереди.
Эти определения предполагают, что стек (если вы его видите в голове) является пространственно вертикальным, а очередь горизонтальна. Другое отличие состоит в том, что операции в стеке всегда происходят в одном и том же конце, тогда как операции в очереди происходят в противоположных концах.
Когда речь заходит о связанных списках и одинарных очередях (deques), используются термины push и pop, например. в С++ STL, где у вас есть операции, такие как push_front, push_back, pop_front и pop_back. Это просто означает, что элементы могут быть добавлены или удалены с обоих концов.
Что касается того, почему pop вызывается, а не тянуть (против нажимать)... хороший вопрос.
Push/Pop первоначально связан с командами стека в asm land. Толкатель помещает значение (регистр) в стек и обновляет указатель стека, в то время как поп извлекает значение из стека и уменьшает указатель. Здесь нет вставки, что означало бы существование какого-либо смещения. Вот почему у вас также есть функции push/pop _front() и push/pop _back(). Они представляют собой статическое местоположение для push/pop для работы.
В С++, по крайней мере, push и pop относятся только к структурам, таким как стеки и очереди, где местоположение, в котором выполняется операция, присуще структуре данных. Для других контейнеров, таких как векторы и списки, у нас есть push_back, push_front, pop_back и т.д. Для контейнеров, где мы действительно не знаем, где элемент будет в конечном итоге, или где мы его будем читать, push и pop не используются в все.
Push и Pop - это обычные имена, данные для операций вставки и удаления элементов из структуры данных стека. Любые операции, которые следуют за шаблоном Last-In-First-Out (LIFO), обычно называются Push и Pop, но их можно назвать любыми, что вам нравится.
Именование push и pop было, вероятно, изобретено только для того, чтобы отличать операции, которые могут выполняться в стеке от тех, которые могут выполняться в списке. Вы можете также назвать их добавить и удалить, но они имеют тенденцию подразумевать, что вы можете добавлять или удалять элемент в любом месте списка, а не просто в начале (или конец, если вы так думаете об этом). Аналогично, существуют enqueue и dequeue, поскольку push и pop подразумевают, что вставки или удаления происходят в одном и том же месте, вместо противоположных концов списка.
Если вы хотите получить техническое определение, вы можете сказать, что push и поп - это операции O (1), которые влияют на один и тот же конец списка в LIFO ( Last In, First Out).
Push и pop первоначально использовались для ссылки на операции стека, но неофициально эти термины часто используются для операций, связанных с добавлением/удалением элемента в конце любой линейной структуры данных, такой как стек, очередь, массив или связанный список.
Нажатие просто добавляет элемент в начало (или конец) коллекции. Popping удаляет тот же элемент.
В Java интерфейс списка добавляет (0, элемент) и удаляет (0). Это фактически параллели для push (item) и pop().
Однако push и pop и стеки интересны в своем конкретном поведении, и, следовательно, у многих есть специализированные структуры данных, которые делают толкание и выскакивание особенно эффективными.
Большая часть того, что вы просите, - это соглашение. Для очередей вы можете нажать или поставить в очередь. Вы увидите и то, и другое. Для стеков вы увидите добавление или толчок. Для этого нет реального жесткого "правила". Если вы работаете на языке, который использует "push" в качестве условного обозначения, используйте "push". Именование имеет значение, но только для удобства использования и здравого смысла. Просто убедитесь, что ваше именование согласовано внутри одного приложения или системы.
Имена push и pop используются при разговоре о стеках. Стеки являются последними в списке (LIFO). Таким образом, имена указывают, что pop вернет последнее нажатое.
Интуитивно мы считаем стеки как те вещи, на которых мы можем выталкивать ценности, чье верхнее значение - это последнее, и что если мы поместим стек, на который мы продвинули значение, у нас есть исходный стек.
Эта интуиция может быть представлена как абстрактная алгебра, с 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;
}
В этом говорится, что если вы можете найти объекты в своей системе,
то сигнатуры различных функций совпадают с сигналами в алгебре, и что, применяя различные функции, они будут вести себя как указывают аксиомы. (Объекты, которые вы выбираете, являются "изоморфными" к алгебре).
Преимущество этой перспективы заключается в том, что она ничего не говорит о реализации различных сущностей, сохраняя при этом суть. Эта алгебра покрывает различные артефакты, связанные с другими ответами; должно быть ясно, что линейная область хранения, используемая в качестве стека, представляет собой стек, что связанным списком, используемым стеком, является стек, что deque, использующий один конец, представляет собой стек, что серия блоков диска, используемых в качестве стека, представляет собой стек,...
Что действительно здорово, так это то, что вы можете переименовать все типы данных и функции внутри алгебры стека, и все же распознать стек, потому что переименование не влияет на изоморфизмы (поскольку постоянное переименование является просто еще одним изоморфизмом, и изоморфизмы составляют изоморфизмы произведений). Все, что соответствует эта спецификация представляет собой стек!
Тот факт, что имена функций в реализации могут быть любыми и но все же совпадают, и что мы можем переименовать имена функций абстрактной алгебры на что угодно и по-прежнему совпадают, позволяет нам, по соглашению, дать абстат функции алгебры именуют те, которые мы считаем репрезентативными. "От себя" и "поп" выбираются по соглашению.
Итак, я бы сказал, вы можете назвать свое имя своими функциями реализации чего угодно но назовем их Push и Pop, если их действия реализуют эту алгебру.
Таким образом, можно определить стек по формальной спецификации. Вы можете определить любую другую структуру данных таким образом тоже.
Жаль, что мы не делаем этого в документальном коде.
Основная операция стека - push и pop. Термин push - это использование для размещения некоторого элемента данных в стеке, и pop используется для удаления некоторого элемента данных из стека.