How is push()ing and pop()ping defined?

Question

I know how the push() and pop() methods in a typical implementation of a Queue/Linked List work but what I do want to know is what you actually define as a push or a pop? When can you name a method push()/pop()? What makes the insert()/add() method in a typical Tree implementation not a push()?

My understanding is that push()ing means putting something to a position some special pointer is pointing to, and pop()ping an element means putting some object away some pointer is pointing to, but it doesn't seem to be clearly defined. Or does the naming matter at all?

Answer 1

Push/Pop originally related to stack commands in asm land. A push places a value (register) on the stack and updated the stack pointer whilst a pop takes the value from the stack and reduced the pointer. There is no insert here which would mean the existance of an offset of some sort. This is why you also have push/pop _front() and push/pop _back() functions. They represent a static location for the push/pop to operate from.

Answer 2

Pushing means putting an item onto a stack (data structure), so that it becomes the stack's top-most item. Popping means removing the top-most item from a stack. (You often hear a third term, peeking, which means looking at/reading the top-most item.)

When it comes to queues, you should generally use the terms enqueueing and dequeueing instead, where the former means appending an item to a queue's "back end" and the latter means removing the item at the "front end" from the queue.

These definitions suggest that a stack (if you picture it in your head) is spatially vertical, while a queue is horizontal. Another difference is that operations on a stack always happen at the same end, while operations on a queue happen at opposite ends.

When it comes to linked lists and double-ended queues (deques), the terms push and pop are also used, e.g. in C++'s STL, where you have operations such as push_front, push_back, pop_front, and pop_back. These simply imply that items can be appended or removed at both ends.

---

As to why pop is called that, and not pull (vs. push)... good question.

Answer 3

Pushing is simply adding an item to the beginning (or end) of a collection. Popping is removing that same item.

In Java, the List interface has add(0, item) and remove(0). Those are effectively parallels to push(item) and pop().

However, push and pop and stacks are interesting in their specific behaviour, and thus many have specialised datastructures that make pushing and popping particularly efficient.

Answer 4

Most of what you're asking is convention. For queues, you can push or enqueue. You'll see both. For stacks, you'll see add or push. There's no real hard and fast 'rule' for it. If you're working in a language that uses 'push' as convention, use 'push'. The naming matters, but only for usability and common sense. Just make sure your naming is consistent within a single application or system.

Answer 5

In C++ at least, push and pop only refer to structures like stacks and queues, where the location the operation takes place is inherent in the data structure. For other containers, like vectors and lists, we have push_back, push_front, pop_back etc. For the containers where we don't really know where an item will end up, or where we will read it from, push and pop are not used at all.

Answer 6

Push and Pop are just the conventional names given to the operations of inserting and removing items from a stack data structure. Any operations that follow the Last-In-First-Out pattern (LIFO) are typically called Push and Pop, but they can be called anything you like.

Answer 7

The naming of push and pop was probably invented just to differentiate the operations that can be performed on a stack from those that can be performed on a list. You may as well call them add and remove, but those tend to imply that you can add or remove the element anywhere on the list, instead of simply at the beginning (or end, if you think of it that way). Similarly, enqueue and dequeue exist because push and pop imply that the insertions or removals happen at the same location, instead of at opposite ends of the list.

If you want a technical definition, you could probably say that push and pop are O(1) operations that affect the same end of a list in a LIFO (Last In, First Out) manner.

Answer 8

The names push and pop are used when talking about stacks. Stacks are last-in-first-out (LIFO). Thus the names indicate that pop will return the last thing pushed.

Answer 9

Generally, push and pop refer to operations on a linked list. You can push items on to the list to add them. You can then pop items off of a list to remove them.

If you pop items from the same end of the list that you add them, you have implemented a stack, or a Last-In-First-Out (LIFO) data structure:

If you pop items from the opposite end, then you have implemented a queue - although usually the terminology is "enqueue" and "dequeue". This is a First-In-First-Out (FIFO) data structure:

Answer 10

The terms push and pop are usually used for stacks, not queues or linked lists. A stack is a last-in-first-out (LIFO) data structure; in other words the first thing to be removed is the item most recently added. A push is when you put a new item onto the stack, and a pop is when you take it off.

Programming languages will allow you to write your code anyway you want, including using the names push and pop for any and all data structures, even when that's not what you're really doing. However, I wouldn't recommend it. It's far better to use the terms others use so that your code can be read by other programmers. Also, using the wrong terminology may make it difficult to get a job, and will make it difficult to communicate with other programmers if you're working on a project (job or open source).

Answer 11

Push and pop were originally used to refer to stack operations, but informally these terms are often used for operations that involve adding/removing an element at the end of any linear data structure such as a stack, queue, array, or linked list.

Answer 12

Intuitively, we think of stacks as being those things on which we can push values, whose top value is the thing last pushed, and that if we pop a stack onto which we've pushed value, we have the original stack.

This intuition can be cast as an abstract algebra, with Push and Pop representing any computations on a data object called a Stack involving 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;
 }

What this says is that if you can find entities in your system,

• some of which you claim are Stack types
• some of which you claim are Elements,
• some which are functions that you claim are Push,
• some which are functions that you claim are Pop, Top, Empty, etc.

then the signatures of the various functions match those in the algebra, and that if you apply the various functions, they will behave as the axioms specify. (The entities you select are "isomorphic" to the algebra).

The advantage of this perspective is that it says nothing about the implementation of the various entities, while still capturing the essence. This algebra covers the various artifacts dicussed in other answers; it should be clear that a linear storage area used as a stack is a stack, that a linked list used a stack is stack, that a deque used one end is a stack, that a series of disk blocks used as a stack is a stack,...

What's really cool is that you can rename all the data types and the functions inside the stack algebra, and yet still recognize a stack because renaming has no effect on isomorphisms (because consistent renaming is just another isomorphism, and isomorphisms compose to product isomorphisms). Anything that matches this specification is a stack!

The fact that the function names in the implementation can be anything and yet still match, and that we can rename the abstract algebra function names to anything, and still match, allows us, by convention, to give the abstact algebra functions names the ones we consider to be representative. "Push" and "pop" are the ones chosen by convention.

So I'd say, you can call your name your implementation functions anything you like, but call them Push and Pop, if their actions realize this algebra.

So, one can define a Stack by a formal spec. You can define any other data structure this way, too.

Too bad we don't do more of this in documenting real code.