History (Abstract Data Type)
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.
In 1957, the Germans Klaus Samelson and Friedrich L. Bauer patented the idea. The same concept was
developed, independently, by the Australian Charles Leonard
Hamblin in the first half of 1957.
A stack is a basic computer science data structure and can be defined in an abstract,
implementation-free manner, or it can be generally defined as, Stack is a
linear list of items in which all additions and deletion are restricted to one
end that is Top.
This is a VDM (Vienna Development
Method) description of a stack:
init: -> Stack
push: N x Stack
top: Stack ->
(N U ERROR)
remove: Stack ->
(where N indicates an element (natural
numbers in this case), and U indicates set union)
s)) = s
isempty(push(i, s)) = false
In many implementations, a stack has
more operations than "push" and "pop". An example is
"top of stack", or "peek", which obverses the top-most
element without removing it from the stack. Since this can be done with a
"pop" and a "push" with the same data, it is not essential.
An underflow condition can occur in the "stack top" operation if the
stack is empty, the same as "pop". Often implementations have a
function which just returns whether the stack is empty.
continue in the next blog:
Data Type (ADT))