Update; The first ever software programmable* electronic computer, built in 1943, in North London was Colossus which, in addition to being intended to support stacks, included also the first implementation of the shift register.

(*The Bell Labs (1930) and ABC (1937) predecessors were not software programmable. The ABC inventors abandoned it (at Iowa State University) in 1939 to join in on the joint British-American wartime efforts - a chain of developments eventually leading to the crucial Colossus Mk. II. - a serious turning point in WWII intelligence history)

More update: On the other side, the German's had an electro-mechanical programmable computer (Z3) since 1941, based on von Neumann's theories but a request to fund an electronic successor was rejected as being "strategically unimportant" - hmmm I suppose technically they were right, given that the work of Colossus, which clearly remained secret, was of immediate tactical importance rather than strategic ;)

More more update: not to be confused with Enigma, which was decoded electromechanically, the decoding of "Geheimschreiber" by Colossus effectively blew the cover off high-ranking German military communications giving allied forces a free ride, bringing the war to a swift end. Colossus remained protected in Britain under the Official Secrets Act until the early 1970's, 25 years after IBM had got their hands on it from the CIA. This piece of crass bureaucracy cost the British economy an estimated $1x10E14 in lost opportunity over the years - erm can we have our money back please Mr. Blair?

I always thought that push and pop applied to a "cafeteria plates" metaphor, not trays. ;) Wikipedia seems to support this assertion.

As the wikipedia article states, the cafeteria plates metaphor works because it conveys the notion of LIFO, as well as the notion that all but the top-most item are hidden from view in a traditional stack implementation as they are in a stack of cafeteria plates.

If you don't like the plates metaphor; how about those vending machines with spiral dispenser? The last item loaded is the first one to pop off as the spiral turns to dispense the item. Or how about facial tissue; the top one is always the one that pops out next as you pull on it. Of course for that metaphor to really work you would have to assure that the box of tissue was loaded from the top. ;)

Shift and unshift are perhaps a little more difficult. Since they occur at the zero end of a queue, the notion is that the entire queue has to shuffle up one for someone else to be placed in the zero position. And when one is taken from the zero position, everyone shifts down one spot. Think of a line of people. If the person at the front of the line passes through the threshold everyone else has to shift forward so that someone else can wait at the front of the line.

Maybe I've just eaten in too many caffeterias in my life (I was a military brat, so that's quite possible), but from what I remember of caffeterias, some of them had the spring-loaded stacks for trays, not the plates.

IF you're not in a self-service buffet, but an old style caffeteria -- you'd collect the tray and utensils yourself, but as you went down the line, you'd request specific items from the caffeteria workers. They'd put it on a plate, and hand you the plate of food. So the general public only saw the use of stacks on the trays, not necessarily the plates.

These days, it's much rarer for the general public to see a caffeteria, and when you do, they've typically forgone the spring-loaded stack in exchange just a pile of trays. We do occassionally see stacks in use at self-service buffets. (some hotel restaurants, all-you-can-eat type places, etc), but it's more common in older establishments. Newer places just have a few piles of plates rather than the elegant spring-loaded stacks).

...

So, anyway ... I'd hardly qualify wikipedia as authoritative in these sorts of things ... and the spring-loadedness, or even what is in the stack is less important than the fact that you can only easily get to the items in the reverse order they were placed on the stack.

update: bah ... immediately after posting this, I realized that the spring-loadedness is necessary so that 'push' and 'pop' make sense in a polysemous way -- I still don't think _what_ is in the stack is necessarily significant.

update2: I was in an IHOP yesterday, and saw a spring loaded stack, but it was for bowls. (so neither plates or trays)

It's true that you don't see the spring-loaded tray or plate stacks as much, but it's an analogy that has stuck with us. We have a similar situation with "radio buttons" in graphical interfaces. The name is losing its meaning relative to actual radios over time, but the name is still here in a particular input type.

As far as the contents of the stack: all analogies break down sooner or later. The stack of plates is just a starting point. This is Perl, so that stack could contain plates, trays, scalars, turkeys, or small cars.

The "cafeteria with spring-loaded trays" model is exactly right for stacks (LIFOs - Last in, First out) which are what push and pop apply to. And yes, you absolutely would both push and "pop" trays - push to add em in the first place,and pop to get one to use.

Perl extends the concept to include access to the "bottom" of the "stack" which allows a few more operational models. In particular the combination of push and shift (or unshift and pop) provide a queue (FIFO - First in, First out). Shift parallels an operation common in handling arguments in some OS batch/scripting languages. Unshift is a neat complement to shift for "putting back" an argument after taking a peek at it. At times there is an advantage to using a queue where you can add and remove elements to/from either end - can't think of an example right now in the software world, but it often happens in supermarket checkout queues!

Nomenclature adjusted for northern hemisphere usage. In the southern hemisphere stacks are the other way up. Queues can be either way and may be affected by the Coriolis effect.

Nomenclature adjusted for northern hemisphere usage.

For sure. I mean... if the world were flat, all the Australians would fall off!

I would say 'shift' comes from shell scripting, where you 'shift' the arguments off of the list passed to the script. This is a fairly natural usage, and might also derive from assembly language, where a basic operation is to shift all the bits in a register one place left or right.

'unshift' is probably originates with perl and would have been named by analogy with 'shift' I think.

push and pop come from stack terminology, while shift comes from queues (to be combined with push).

unshift is, like somebody else said, just the opposite of shift, like unget is the opposite of get. Not exactly proper English, but clear enough for the insiders — us.

But technically, there's no reason why the array ends could not have been swapped. You get a just as fine stack if you just use unshift/shift as primitives instead of the usual push/pop, and, for queues, unshift/pop, instead of push/shift.

Since no one's mentioned the Pez dispenser here, I will. It's a toy that lets you 'push' candies into a stack, and then 'pop' them out.

Amd, as has already been mentioned, 'shift' comes from the assembler operation of the same name, and 'unshift' follows from that.

I just got an awful image in my head: a Larry Wall pez dispenser.

Shift is from the builtin command of same name in unix shells. It shifted a command-line argument from the beginning, so that if you used it in a loop, you could loop through command-line arguments in normal order. Even the DOS command.com has copied that command with the same name.

Update: I see jbert has already said this in his reply.

Stacks as implemented in computer hardware work in various ways. I've seen them grow by increasing addresses, and by decreasing addresses (big-endian/little-endian). Since they rarely diverge from the host hardware, it makes little difference. As far as things go, devices like "stacks", "queues", and "lists" are pretty general, and typically the subject of a first course in programming. What to call the "operators" on these devices is what one might call a "local option". They do vary, but there are a few common names.

I dug out an article by Frederick L Bauer who invented the stack, and even tried to read his original paper, written in 1950. He talked there about 'pushdown' data storage and it was known as the Kellerprinzip or cellar principle. So I reckon that's where 'push' comes from.

I was not surprised to find that Bauer's work was based on original papers by a certain Alan Turing, written in 1934. He is most famous for his work with breaking the Enigma code in the second world war. But go look him up in your resource of choice, and you will find his ideas in many other areas, including AI and neural networks.