Computing Atlas

How Computing Was Built
Sign In
Text size
100%
Theme

Switch Atlas

Concept

Stack

Also Known As LIFO Stack
Data Structure

A stack is an abstract data type representing a collection of elements with two principal operations, push, which adds an element, and pop, which removes the most recently added element, following last in first out ordering. Access to elements below the top requires removing the ones above them first. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/

Facts
Disputed
Origin Year
1955 1
Klaus Samelson and Friedrich L. Bauer of the Technical University of Munich proposed the concept, calling it Operationskeller, in 1955 and filed a patent in 1957, but Charles Leonard Hamblin independently described a similar idea in 1954, and Wilhelm Kammerer developed related ideas in 1958; there is no single settled inventor or date.
Core Principle
Strict last in first out ordering, with additions and removals confined to one end, the top, enabling efficient function call management and expression evaluation. 1
Connections

Associated With

Depth-First Search, Algorithms
Source Wikipedia: Depth-First Search

In Field

Algorithms and Complexity Theory, Fields
Source Wikipedia: Stack (Abstract Data Type)
Sources
1. Wikipedia: Stack (Abstract Data Type)
Wikimedia Foundation
  • Introduction section
    Push, which adds an element to the collection, and Pop, which removes the most recently added element.
  • History section
    Subroutines and a two-level stack had already been implemented in Konrad Zuse's Z4 in 1945.
  • In Field: Algorithms and Complexity Theory
View the Source
Wikipedia: Depth-First Search
Wikimedia FoundationAssociated With: Depth-First Search, Opening paragraph, on stack-based traversalView the Source
Frequently Asked Questions

Did any computer use a stack before the concept was formally described in 1955?

Yes. Konrad Zuse's Z4 computer used a two-level stack in 1945, a decade before the formal 1955 definition.

Yes. Subroutines and a two-level stack were already implemented in Konrad Zuse's Z4 computer in 1945, roughly ten years before Klaus Samelson formally described the operational cellar, the stack concept, in 1955.
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.