Ch 3: Stacks, Queues, Exceptions, Templates Flashcards
what is a stack?
an ADT in which items are only inserted on or removed from the top of the stack
what are the two operations of stacks and what do they do?
- push: inserts an item on the top of the stack
2. pop: removes and returns the item at the top of the stack
what is the acronym rule for stacks?
FILO- first in last out
what does peek do for stacks?
returns but does not remove the item at the top of the stack
does peek change the stack?
no, just returns the item at the top of the stack
should peek and pop be called on an empty stack? why?
they should not be called on empty stacks because the behavior may be undefined
what is a queue?
an ADT in which items are inserted at the end of the queue and removed from the front of the queue
what are the two operations of queues and what do they do?
- enqueue: insert an item at the end of the queue
2. dequeue: removes and returns the item at the front of the queue
what is the acronym rule for queues?
FIFO - first in first out
what is a deque (deck) ?
- an ADT in which items can be inserted and removed at both the front and back
- aka “double-ended” queue”
what is an array-based list?
a list ADT implemented using an array
what happens if there is no more room for objects in the array?
- array must be resized
- array size is doubled
what is the Big O for resizing and why?
O(N) because it has to go through each item in the array and copy it to the new array
what is the Big O for push back when there is no more room in an array and why?
- push back is O(1) because it always knows where the end of the list is
- having to resize is O(N)
- because you double the size when resizing, the impact of O(N) is minimal as it continues to do it, so, therefore, push back and having to resize is O(1)
what is error-checking code?
code a programmer writes to detect and handle errors that occur during program execution
what is an exception?
a circumstance that a program was not designed to handle
what are exception-handling constructs?
- special constructs to keep error-checking code separate and to reduce redundant checks
- try, catch, throw
what is the try block?
surrounds normal code, which is exited immediately if a throw statement executes
what is a throw statement?
- appears within a try block; if reached, execution jumps immediately to the end of the try block
- written so only error situations lead to reaching a throw
what is a catch clause?
- immediately follows a try block; if the catch was reached due to an exception of the catch clauses’ parameter type, the clause executes
- catches the thrown exception
what is a handler?
catch block; handles the exception
what is the point of try-catch?
- to simplify code
- so that code is not bombarded with endless if-statements checking for error
do catch blocks have to follow try blocks?
yes
explain try-catches in main & function
try block is in main, when it calls a function, the throw is in the function if it is in a situation that it doesn’t know how to handle. then the function ends and the throw is taken back to main and the catch is executed
explain how throws and catches work for different types
throws can be for different types, therefore there are catches of different types
what is “catch(…)”?
- a catch-all handler that catches any type
- useful when listed as the last handler
should the catch-all ( catch(…)) be before the other catches?
no because the catches are run in order when the exception is thrown. since the catch-all is for last resorts, it should be called after the other handlers
what is a function template?
a function definition having a special type parameter that may be used in place of types in the function
what is a type parameter?
used through the function for any parameter types, return types or local variable types
what is a class template?
a class definition having a special type parameter that may be used in place of type in the class
what is the point of templates?
avoid writing and maintaining redundant classes that only differ by data type
