Class Notes (836,321)
Canada (509,732)
CMPT 225 (60)
John Edgar (28)
Lecture 2

CMPT 225 Week 2 Lecture 2

3 Pages
Unlock Document

Computing Science
CMPT 225
John Edgar

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, the same. 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 int[10]. How do we find the element in an array? Don't go to first element, then traverse array until we get to index 2. 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 Linked Lists 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
More Less

Related notes for CMPT 225

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.