Stacks and Queues quiz

Suppose that, starting from an empty data structure, we perform N push operations in our resizing array implementation of a stack. How many times is the resize() method called?

constant
logarithmic
linear

Suppose that you implement a queue using a null-terminated singly-linked list, maintaining a reference to the item least recently added (the front of the list) but not maintaining a reference to the item most recently added (the end of the list). What are the worst case running times for enqueue and dequeue?

constant time for both enqueue and dequeue
constant time for enqueue and linear time for dequeue
linear time for enqueue and constant time for dequeue
linear time for both enqueue and dequeue

Consider the following code that defines a ResizingArrayStackOfStrings:
```public class ResizingArrayStackOfStrings  {
private String[] s;
private int N;
...
}
```
If the array is completely full, how many bytes does the stack use to store N strings? Give your answer in Tilde notation. Don't count the memory of the actual strings (impossible, since they are of unknown length).

~N bytes
~4N bytes
~8N bytes
~16N bytes
~32N bytes
~16N + 40 bytes

How much memory does a ResizingArrayStackOfStrings use in the worst case as a function of N? Give your answer in Tilde notation.

~N bytes
~4N bytes
~8N bytes
~16N bytes
~32N bytes
~16N + 40 bytes