Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

According to http://dictionary.reference.com

push

verb (used with object)

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

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

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

  4. to cause to extend or project; thrust.

  5. 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?

share|improve this question
2  
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... –  Crazy Eddie May 14 '12 at 15:43
    
I guesss if only for today I'm FGITW! –  Scott Wilson May 15 '12 at 0:31
1  
This question was asked and answered on stackoverflow - stackoverflow.com/questions/420315/stacks-why-push-and-pop. Push and pop are both discussed. –  Bratch May 16 '12 at 15:46
    
Needs "history" tag. –  Bratch May 21 '12 at 20:13
add comment

4 Answers

up vote 47 down vote accepted

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.

share|improve this answer
1  
Pushdown may originate from Pushdown Automata. –  Oded May 14 '12 at 10:23
10  
@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
add comment

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.

http://i.stack.imgur.com/VJkYi.jpg

share|improve this answer
2  
mmmmmm...Pez!!! –  Steven A. Lowe May 14 '12 at 15:26
14  
+1 for Hello Kitty –  Izkata May 14 '12 at 16:13
1  
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 :) –  Ritwik G May 14 '12 at 18:34
show 1 more comment

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.

share|improve this answer
    
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. –  MPD May 15 '12 at 1:12
add comment

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."

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.