Stacks and Queues Flashcards
does a stack operate by lifo or fifo
lifo
does a queue operate by lifo or fifo
fifo
sample of API for stacks
public class Stack()
Stack() = constructor to make an empty stack void push(int number) int pop() boolean isEmpty() int size()
where are the two locations that can the hold the top of stack
head
tail
if the top of the stack is at the head of the list, what is the running time for the push operation
big theta (1)
just change the next, prev and head pointers (all constant time)
if the top of the stack is at the head, what is the running time for push
big theta (1)
just move top of stack refernce
if the top of stack is at the bottom of the list, what is the run time of the push function
big theta (1)
if the top of the stack is at the bottom of the list, what is the run time for pop
big theta (N)
the temp pointer has to move from the beginning to the end to find the top of the stack
for maximum efficiency, where should the top of the stack be
the first element in the list
how much memory does a stack with N nodes take up
40N bytes
what does the memory for each element in a stack include
reference to node
reference to data in node
object overhead
what is loitering
holding a reference to an object that is no longer needed
when there is overflow in an array, it should be
resized
when there is underflow in an array
an exception must be thrown
why is creating a new array each time the size gets altered expenisve
array must be made
all elements must be copied over
how to avoid having to change the size of the array for every alteration
allow the array to have extra empty spaces
example of resizing thresholds
doubles when full
halves when half full
Array is always between 25% and 100% full
what is a priority queue
queue that removes the largest or smallest item with the remove function
what is a requirement for priority queues
keys must be comparable
eg ints, alphabetical
example of a use of a priority queue
isolating larger transactions to flag suspicious activity
eg find the M largest transactions in a list of N transactios
Find the M largest numbers in a list of N numbers
How would this be implemented using a elementary priority queue and unsorted array
What will the run time be
inserting elements onto the end of the array has a constant time of 1
deleting the smallest has a run time of M
a loop containing these two will be iterated N times
Total runtime theta(NM)
Find the M largest numbers in a list of N numbers
How would this be implemented using a elementary priority queue and sorted array
What will the run time be
cost of inserting into the ordered array is M
cost of removing minium element is 1
this loop will be iterated Ntime
Total is theta (NM)
Find the M largest numbers in a list of N numbers
How would this be implemented using an array and sorting it
What will the run time be
load all the N numbers (big theta N)
sort all the N numbers (big theta N logN)
print the top M numbers (big theta M)
total = big theta (NlogN + M)
use of stack example
runtime stack
keeps track and retraces steps to find out where error occurs
use of queues example
printer
prints out what was sent to it first
