How much work did the push function do?
Example: does the stack do more or less work with 500 things in it versus having 10 things in it? No,
If the stack had 256 things in it, does a lot more (256 times), as it needs to copy all those things into a
new array one by one.
Does constant amount of work unless it's full (in which case is linear)
Pop function does constant amount of work (just decrements top and returns something)
Worth thinking about for every datastructure you create
Programs typically call >1 function. Main, which calls other functions. Functions need space in call
stack for variables and line number
Most languages use call stack to implement function calling
Method called, line number and other data pushed onto cs
When it terminates, it is popped off
Eclipse will actually show you call stack
Space is allocated sequentially
Then deallocated and can be reused
Functions returned values that were assigned to variables in other functions, but does not change the
amount of memory allocated to them
ADT operations should be performed efficiently. Definition of efficiency changes based onADT. Some
just require to do more work. Example - inserting something into a sorted list.
Next week's lab is compulsory, will demonstrate how inefficient our insert is for SortedList.
Order of items in stack is not based on values of items, is based on order in which they were inserted.
Can design other modules that use push and pop without knowing how they or the stack are
implemented - encapsulation.
Can implement stacks in other ways, such as with Linked Lists. Must implement all the stack
operations. Want in constant time.
Average insertion time for our push: log2(n) (half constant, half approaches infinity.)
Arrays are very fast. Example: going to 300th element takes same amount of time as going to 2nd.
Array variable refers to first element of the array. (constant pointer)
Can't change address you're just assigned to the array. Cannot point to new arrays. Need int * p = new
How do we find the element in an array? Don't go to first element, then traverse array until we get to
We know first address, type (and therefor size), know index of element we want to access, so
address of first + (index * type size) = address of item we want (at index)
Even if using template, will know type once you instantiate it. Array positions can carry meaning. In which case, need to maintain ordering. Not all data structures
require this. (hash maps)
If you want to keep order, need to move everything to avoid writing over or leaving gaps.
Good things about arrays: fast, random access of elements, memory efficient (array of 1000 integers
requires exactly as much space as required for 1000 ints + 4 bytes for a pointer), easy to use
Bad: don't work very well for ordered structures, size must be known when they are created
Is dynamic, does fast insertions and deletions in the middle (although not needed for stacks)
Need to understand how pointers work to understand linked lists. One of a n