Week 3 Flashcards
1
Q
How does the resize() method work?
A
It allocates a new array B, with size 2n and copies the original elements into the first n positions in b
2
Q
How long does resize() take?
A
O(n)
3
Q
How does adding elements trigger a resize()?
A
If the array is full and we want to add another element
4
Q
How does removing elements trigger a resize()?
A
We remove an element and the array becomes 2/3 empty
5
Q
How many add or remove operations does there at least have to be before a resize can happen?
A
at least n/2 add or remove operations since the preceding resize
6
Q
Why is ArrayStack not a good choice of implementation for a FIFO queue?
A
ArrayStack would require frequent shifting
7
Q
What does ArrayDeque efficiently do?
A
Allows for addition and removal at both ends
