Stacks entered the computer science literature in 1946, when Alan Turing used the terms "bury" and "unbury" as a means of calling and returning from subroutines.
[4][5] Klaus Samelson and Friedrich L. Bauer of Technical University Munich proposed the idea of a stack called Operationskeller ("operational cellar") in 1955[6][7] and filed a patent in 1957.
[8][9][10][11] In March 1988, by which time Samelson was deceased, Bauer received the IEEE Computer Pioneer Award for the invention of the stack principle.
[12][7] Similar concepts were independently developed by Charles Leonard Hamblin in the first half of 1954[13][7] and by Wilhelm Kämmerer [de] with his automatisches Gedächtnis ("automatic memory") in 1958.
[18] Since this can be broken down into a "pop" followed by a "push" to return the same data to the stack, it is not considered an essential operation.
[19] In either case, what identifies the data structure as a stack is not the implementation but the interface: the user is only allowed to pop or push items onto the array or linked list, with few other helper operations.
The program must keep track of the size (length) of the stack, using a variable top that records the number of items pushed so far, therefore pointing to the place in the array where the next element is to be inserted (assuming a zero-based index convention).
Some languages, notably those in the Forth family (including PostScript), are designed around language-defined stacks that are directly visible to and manipulated by the programmer.
The following is an example of manipulating a stack in Common Lisp (">" is the Lisp interpreter's prompt; lines not starting with ">" are the interpreter's responses to expressions): Several of the C++ Standard Library container types have push_back and pop_back operations with LIFO semantics; additionally, the stack template class adapts existing containers to provide a restricted API with only push/pop operations.
Having the top-of-stack as an implicit argument allows for a small machine code footprint with a good usage of bus bandwidth and code caches, but it also prevents some types of optimizations possible on processors permitting random access to the register file for all (two or three) operands.
Sun SPARC, AMD Am29000, and Intel i960 are all examples of architectures that use register windows within a register-stack as another strategy to avoid the use of slow main memory for function arguments and return values.
Expressions can be represented in prefix, postfix or infix notations and conversion from one form to another may be accomplished using a stack.
The prototypical example of a backtracking algorithm is depth-first search, which finds all vertices of a graph that can be reached from a specified starting vertex.
Other applications of backtracking involve searching through spaces that represent potential solutions to an optimization problem.
The functions follow a runtime protocol between caller and callee to save arguments and return value on the stack.
This type of stack is used implicitly by the compiler to support CALL and RETURN statements (or their equivalents) and is not manipulated directly by the programmer.
These include: Some computing environments use stacks in ways that may make them vulnerable to security breaches and attacks.
This means that the program moves data into and out of the same stack that contains critical return addresses for the procedure calls.
Such a program may copy the data in its entirety to a location on the stack, and in doing so, it may change the return addresses for procedures that have called it.
An attacker can experiment to find a specific type of data that can be provided to such a program such that the return address of the current procedure is reset to point to an area within the stack itself (and within the data provided by the attacker), which in turn contains instructions that carry out unauthorized operations.
This type of attack is a variation on the buffer overflow attack and is an extremely frequent source of security breaches in software, mainly because some of the most popular compilers use a shared stack for both data and procedure calls, and do not verify the length of data items.