Part 2 Flashcards
What is an abstract data type?
A type that can be specified without using any programming language
What are the elements of an abstract data type?
The name of the type
The name of the primitive operations, their arguments and result types
The semantic of the operations; a description of how they behave
Why are ADTs beneficial?
They allow an application program to use the type without knowing how it is implemented.
To guarantee that an ADT will work correctly, the objects of the ADT must only be accessed using the _____________
Primitive operations
What are the primitive operations of a stack?
push
pop
top
isempty
createstack
How are data items in a stack accessed?
From the top only
What does the push operation do to a stack?
Adds an item to the top of the stack
What does the pop operation do to a stack?
Removes the top item
What does the top operation do to a stack?
Returns the top item of the stack (aka peek)
What does the isempty operation do to a stack?
Deduces whether the stack contains any items or not
What does the createstack operation do to a stack?
Creates a new stack object with no items
What are the 4 stack axioms?
isempty(createstack()) = true
isempty(push(n, s)) = false
top(push(n, s)) = n
pop(push(n, s)) = s
Where s is the stack before the operation is applied, and n is the item being applied to the stack
The stack axiom
isempty(createstack())
has the value
true
The stack axiom
isempty(push(n, s))
has the value
false
The stack axiom
top(push(n, s))
has the value
n
The stack axiom
pop(push(n, s))
has the value
s
How does one prevent having to frequently shift elements in an array-based stack?
Use a large array with a cursor that indicates the start position of the stack
What is the advantage of using an ArrayList implementation of a stack?
Don’t have to manually keep track of cursors etc.
Arraylist handles it all for us
What is the disadvantage of using an arraylist implementation of stack, compared with an array implementation?
Possibly less efficient than keeping track of the cursor ourselves.
What is the advantage of using a linked-list stack?
Don’t have to worry about array sizes
What is the disadvantage of using a linked list to store a stack?
Greater memory consumption than array
What is a queue?
Structure where items are added at the back and removed from the front
What are the primitive operations of the queue?
add
removefront
front
isempty
What does the add operation do in a queue?
adds an item to the back of the queue
What does the removefront operation do in a queue?
remove the front item
what does the front operation do in a queue?
returns the front item without removing it
What are the axioms for the Queue adt?
isempty(createqueue()) = true
isempty(add(n, q)) = false
front(add(n, q)) = n, if q is empty
front(add(n, q)) = front(q), if q is not empty
removefront(add(n, q)) = q, if q is empty
removefront(add(n, q)) = add(n, removefront(q)), if q is not empty
The queue axiom
isempty(createqueue())
has the value
true
The queue axiom
isempty(add(n, q))
has the value
false
The queue axiom
front(add(n, q))
has the value
n, if q is empty
The queue axiom
front(add(n, q))
has the value
front(q), if q is not empty
The queue axiom
removefront(add(n, q))
has the value
q, if q is empty
The queue axiom
removefront(add(n, q))
has value
add(n, removefront(q)), if q is not empty
Using an array implementation of queues will require ___ cursors
Two
With a linkedlist implementation of a queue, a reference to _________ will need to be stored in addition to the reference to the ____________
back item
front item
