Stacks

Question 1

Name the three core stack methods.

Answer 1

Push, pop, and peek.

Question 2

Fill in the blank:

public interface PureStack<E>{
void \_\_(E item);
\_\_ pop();
E \_\_\_();
boolean \_\_();
int \_\_();
}</E>

Answer 2

push; E; peek; isEmpty; size

Question 3

Stacks may be implemented using what two data structures?

Answer 3

Arrays and linked lists.

Question 4

For a array-backed stack, the push, pop, and peek operations have what runtime?

Answer 4

O(1)

Question 5

For a linked list-backed stack, the push, pop, and peek operations have what runtime?

Answer 5

O(1)

Question 6

The stack method push() is analogous to what List method?

Answer 6

add()

Question 7

The stack method peek() is analogous to what List method?

Answer 7

get(size() - 1)

Question 8

The stack method pop() is analogous to what List method?

Answer 8

remove(size() - 1)

Question 9

The stack method push() is analogous to what Deque method?

Answer 9

addFirst()

Question 10

The stack method pop() is analogous to what Deque method?

Answer 10

removeFirst()

Question 11

The stack method peek() is analogous to what Deque method?

Answer 11

peekFirst()

Question 12

Define “overflow”.

Answer 12

Trying to push onto a full stack.

Question 13

Define “underflow”.

Answer 13

Trying to pop on an empty stack.

Question 14

Write the pop() method for an array-based stack.

Answer 14

@Override
public E pop()
{
if (top == 0) throw new NoSuchElementException();
E ret = data[–top];
data[top] = null;
return ret;
}

Question 15

Write the push() method for an array-based stack.

Answer 15

@Override
public void push(E item)
{
checkCapacity();
data[top++] = item;
}

/**
* Ensures that the backing array has space to store at least
* one additional element.
*/
private void checkCapacity()
{
if (top == data.length)
{
// create a copy of the data array with double the capacity
data = Arrays.copyOf(data, data.length * 2);
}
}