History (Abstract Data Type) Part 2 Notes
Posted by JanWan
Last Updated: April 04, 2012

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)


  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)) 



Thanks for the Info. looking forward to the next blog!