CSE 373 Assignment 1: Stacks -- Formal Description |
|
| Name: Steven Tanimoto
University of Washington Student Number: XXXXXXXXX |
|
|
My assigned question
(Question number: 941) |
What formal or mathematical description best specifies the way the
following kind of data structures or algorithms work? (Use mathematical
concepts such as sets, relations, and mathematical functions to describe
what information is represented and/or how it is manipulated by the algorithm
or operations associated with the data structure.)
Your data structure or algorithm: Stacks Also, give a short informal description of how the data structure or algorithm works. |
FORMAL DESCRIPTION:Data:a sequence of values, each from an implicit domain (set) of possible values.< v , v , v , ..., v > 0 1 2 N-1Note: order of values is important as a sequence is not simply a set. Also, there may be multiple occurrences of any or all of the values in the sequence. Operations:PUSHPUSH can be regarded as a (mathematical) function that takes a stack and a value and produces a new stack.
PUSH: Stacks X Values -> Stacks
PUSH(< v , v , v , ..., v >, v ) |-> < v , v , v , ..., v >
0 1 2 N-1 N 0 1 2 N
POPPOP can be considered as a (mathematical) function that takes a nonempty stack and returns a pair consisting of a (new) stack and a value.
POP: Stacks -> Stacks X Values
POP(< v , v , v , ..., v >) |-> (< v , v , v , ..., v >, v )
0 1 2 N 0 1 2 N-1 N
ISEMPTYThis is a (mathematical) function that takes a stack and returns true iff there are no elements in the stack.
ISEMPTY: Stacks -> { true, false }
{ true, if s = <>
ISEMPTY(s) = {
{ false, otherwise
TOPThis is a function that takes a nonempty stack and returns the value of the last element.
TOP(< v , v , v , ..., v >) |-> v
0 1 2 N N
|
Informal DescriptionInformally, a stack is a list together with two required operations, PUSH and POP that permit adding (PUSH) values or removing (POP) values at only one end (the "top" of the stack). Two other operations, ISEMPTY and TOP are optional. ISEMPTY is a predicate that's true if its argument is an empty stack. TOP takes a stack and returns the last element without altering the stack (unlike POP).The operations are often implemented as methods of a class, so that it is not necessary to list the input stack as an argument to the method, and neither is it necessary to return the updated stack (in the case of PUSH or POP) as a value. |
References:
|