Stacks and Queues

Question 1

does a stack operate by lifo or fifo

Answer 1

lifo

Question 2

does a queue operate by lifo or fifo

Answer 2

fifo

Question 3

sample of API for stacks

Answer 3

public class Stack()

Stack() = constructor to make an empty stack
void push(int number)
int pop()
boolean isEmpty()
int size()

Question 4

where are the two locations that can the hold the top of stack

Answer 4

head

tail

Question 5

if the top of the stack is at the head of the list, what is the running time for the push operation

Answer 5

big theta (1)

just change the next, prev and head pointers (all constant time)

Question 6

if the top of the stack is at the head, what is the running time for push

Answer 6

big theta (1)

just move top of stack refernce

Question 7

if the top of stack is at the bottom of the list, what is the run time of the push function

Answer 7

big theta (1)

Question 8

if the top of the stack is at the bottom of the list, what is the run time for pop

Answer 8

big theta (N)

the temp pointer has to move from the beginning to the end to find the top of the stack

Question 9

for maximum efficiency, where should the top of the stack be

Answer 9

the first element in the list

Question 10

how much memory does a stack with N nodes take up

Answer 10

40N bytes

Question 11

what does the memory for each element in a stack include

Answer 11

reference to node
reference to data in node
object overhead

Question 12

what is loitering

Answer 12

holding a reference to an object that is no longer needed

Question 12

when there is overflow in an array, it should be

Answer 12

resized

Question 13

when there is underflow in an array

Answer 13

an exception must be thrown

Question 14

why is creating a new array each time the size gets altered expenisve

Answer 14

array must be made

all elements must be copied over

Question 15

how to avoid having to change the size of the array for every alteration

Answer 15

allow the array to have extra empty spaces

Question 16

example of resizing thresholds

Answer 16

doubles when full
halves when half full

Array is always between 25% and 100% full

Question 17

what is a priority queue

Answer 17

queue that removes the largest or smallest item with the remove function

Question 18

what is a requirement for priority queues

Answer 18

keys must be comparable

eg ints, alphabetical

Question 19

example of a use of a priority queue

Answer 19

isolating larger transactions to flag suspicious activity

eg find the M largest transactions in a list of N transactios

Question 20

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

Answer 20

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)

Question 21

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

Answer 21

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)

Question 22

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

Answer 22

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)

Question 23

use of stack example

Answer 23

runtime stack

keeps track and retraces steps to find out where error occurs

Question 24

use of queues example

Answer 24

printer

prints out what was sent to it first