Stack ADT

A stack is a linked list in which insertion and deletion are restricted to one end, usually the front. (There are in principle two types of stack, the front stack and the rear stack.) A railway siding is a good analogy.

Stacks are sometimes referred to by other names: push-down list, nesting store, first-in, last-out (FILO) list, and last-in, first-out(LIFO) list. The stack is a commonly used mechanism in programming languages.

Stack Primitives

We rename the addfirst and deletefirst primitives as push and pop:

push(exstack)

A new empty node is added at the front of the stack. Note that no access variable is specified, we assume the component top in the stack name which always gives access to the first node.

SP-push

pop(exstack)

The front node is deleted from the stack.  This should not be done on an empty stack.

SP-pop

The other primitives for stacks are very similar to the corresponding linked list primitives:

accessfirst(exstack, exav) 

accessnext(exstack, exav)  

createstack(exstack)

 destroystack(exstack)

accessfirst and accessnext are seldom used.

exstack is a variable of type stackname.  The precise details will be dependent on the implementation.  In place of the validaccess function can use an emptystack test.

Next: Queue ADT