Stacks & Queues

1. Match the following implementations with the facts about them. The matching should be one-to-one (one and only one for each) (1.2 pts, -0.4 pts/mistake)

The five queue implementations:

A) a singly-linked list with no tail pointer

B) a doubly-linked list

C) a circularly-linked list (tail node points to the head, and you maintain a tail pointer)

D) an array, adding and removing from the end only

E) an circular array - having the head move (not just at index 0) during add or removes from the head

Facts about those implementations:

______ Great FIFO and LIFO, O(1), but you have to deal with capacity vs. size issues

______ Great FIFO and LIFO, O(1), no capacity issues and you can remove either from the head or tail.

______ O(1) for both add and remove as a FIFO and LIFO queue, but you can only remove from the head for that speed.

______ Great LIFO, terrible FIFO (that is, O(n)). ArrayList essentially implements it for you (using add(E) and remove(myList.size()-1) )

______ Great LIFO, terrible FIFO (that is, O(n)) as normally implemented. Elements are not in contiguous portions of memory.

2. If we take a typical singly-linked list implementation and maintain a pointer to the tail, which of the following are O(1) operations. Circle all the apply. (0.6 pts, -0.2 per mistake)

a) Removing the tail element

b) Removing the second element (the one the head points to)

c) Adding an element at the head

d) Adding an element to the tail

e) Removing the head element

f) Removing the second to last element (the one that points to the tail element)