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.
Abstract
definition
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:
Function signatures:
init: -> Stack
push: N x Stack
-> Stack
top: Stack ->
(N U ERROR)
remove: Stack ->
Stack
isempty: Stack
-> Boolean
(where N indicates an element (natural
numbers in this case), and U indicates set union)
Semantics:
top(init()) =
ERROR
top(push(i,s)) =
i
remove(init()) =
init()
remove(push(i,
s)) = s
isempty(init()) =
true
isempty(push(i, s)) = false
Inessential
Operations
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.
Notes
continue in the next blog:
Software
Stacks(Abstract
Data Type (ADT))
J.W. PRODUCTION