I think it's earlier than some people think. PUSH and POP are assembler (2GL) (stack) instructions dating back to the early 1950's but these are just tokens for actual hardware instructions (1GL). Shell argument shifting (from which Perl derives its shift) may be 1970's in origin, but that in turn is an analogy on bit shifting which goes back at least twenty years before that. i.e. all three are really 55+ years old. As for the cafeteria tray, although cafeteria the term came to English via American Spanish in the 19th Century, the electronic computer was invented in England in the 1940s. At that time anybody involved in the early computing wouldn't be eating in a "cafeteria" (though at the time, certainly in a mess), so it isn't likely that the term "stack" and its operators could have been inspired by cafeteria trays, though it could very possibly come from a spring-loaded plate stacking device which did exist in messes in the 1940s.

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?