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
