Why is putting something on the stack called "push"?

Question

According to http://dictionary.reference.com

push

verb (used with object)

to press upon or against (a thing) with force in order to move it away.

to move (something) in a specified way by exerting force; shove; drive: to push something aside; to push the door open.

to effect or accomplish by thrusting obstacles aside: to push one's way through the crowd.

to cause to extend or project; thrust.

to press or urge to some action or course: His mother pushed him to get a job.

This IMO fits to FIFO queues. Is there an explanation for this?

Well.. in Israel the analogy was for a gun magazine as you need to PUSH the bullets in.. but I think I like the pez dispencer better. — G.Y, May 14 '12 at 14:44
@GY - LOL - I came here to say exactly that (the Pez thing). BASTARD! Interesting culture there in Israel though... — Edward Strange, May 14 '12 at 15:43
This question was asked and answered on stackoverflow - http://stackoverflow.com/questions/420315/stacks-why-push-and-pop. Push and pop are both discussed. — Bratch, May 16 '12 at 15:46

score 47 · Accepted Answer · answered May 14 '12 at 10:17

47

According to legend, the original stack received its name by analogy to the stacks of dishes in the university cafeteria: you put one on top, and the (spring-loaded) stack of dishes goes down a bit, you take one away and it pops up a bit. Therefore 'pushing' received a connotation of operating downwards, even though you don't actually push down on the plate - you just set it down and gravity does the work. "Pushdown stack" is still a common phrase, and stacks tend to grow downwards in memory (i.e. with decreasing memory addresses), although it is doubtful whether that has anything to do with dish stacks or not.

answered May 14 '12 at 10:17

Kilian Foth

107,706
45
295
310

1

Pushdown may originate from Pushdown Automata. – Oded May 14 '12 at 10:23
11

@Oded I’m pretty sure it’s the other way round. A pushdown automaton is a finite automaton augmented by a pushdown stack. – Konrad Rudolph May 14 '12 at 14:21
And you know some poor fool out there is learning that, because the PC counts "up", lower memory addresses are at the bottom. – Philip May 14 '12 at 14:55
I was under the impression the origin was something to do with those document spikes. You know, a nail held vertically on which you push bits of paper on – Ian May 14 '12 at 15:07

score 45 · Answer 2 · edited May 14 '12 at 15:12

45

Think about a Pez dispenser. That's your mental model for a stack - last in, first out. So adding an item to a stack requires you to push down the existing items to make room.

edited May 14 '12 at 15:12

gnat

21,442
29
112
288

answered May 14 '12 at 10:15

Scott C Wilson

3,908
20
25

3

mmmmmm...Pez!!! – Steven A. Lowe May 14 '12 at 15:26
2

I was going to suggest the model of an ammo magazine, but the Pez dispenser is a much more family-friendly mental picture. +1 and I wish I could upvote more. – KeithS May 14 '12 at 16:24
I'm tempted to -1 for hello kitty, but it wouldn't do the answer and the analogy justice. So +1 from me. – 0xC0000022L May 14 '12 at 16:58
and this is how you explain "Stack" to a kid :) – Chani May 14 '12 at 18:34
StackOverflow would be when you try to fill it with a whole pack of Pez, and the whole thing snaps out of your fingers before you put it in so it spreads all over the place. – awe May 15 '12 at 16:06

Bratch · Answer 3 · 2012-05-16T17:26:59.270

The illustrations using cafeteria plates or trays, pez dispensers, and piles of books all came later. From Wikipedia: (with references)

"The stack was first proposed in 1946, in the computer design of Alan M. Turing (who used the terms "bury" and "unbury") as a means of calling and returning from subroutines." Additional work and patents by others followed in 1957. The current illustrations of stacks we use today may have caused Turing's original terms of bury and unbury to evolve into push and pop. Maybe these terms just sound better.

Finding exactly where or when this happened is the answer to the OP's question. Maybe the answer is buried in one of the Wikipedia references like "Verfahren zur automatischen Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens."

score 3 · Answer 4 · answered May 14 '12 at 10:23

3

FIFO is a Queue - the first one added to the group is the first one served.

LIFO is a Stack - like a bunch of trays. You always take the one from the top of the stack.

The term push is used when adding an item to the LIFO/Stack, because at some cafeterias the stack of trays is on a spring loaded surface. As more items are pushed on the stack, the entire stack sinks lower.

When the top/newest item is removed from the stack, the top one is "popped" off the top of the stack.

answered May 14 '12 at 10:23

mhoran_psprep

2,328
2
16
14

The stack of plates in a cafeteria is often used to illustrate how a stack data structure works, but do you have any evidence that that's where the terminology comes from? – Caleb May 14 '12 at 12:35
@Caleb, TAOCP Volume 1 (p. 237 in the second edition) implies that it does, but does not give a citation. The previous page talks about how the terms "stack" and "queue" are "gradually becoming standard terminology", so this may be the earliest potential reference. – mpdonadio May 15 '12 at 01:12

Why is putting something on the stack called "push"?

4 Answers4