$(20$ points$)$ Answer "True" or "False". Suppose the measure is time complexity under the big

O$-$notation.

$($a$)$ doubly linked list structure is worse than a singly linked list if we plan to do a lot of insertions.

$($b$)$ doubly linked list structure is worse than a singly linked list if we plan to do a lot of deletions.

$($c$)$ doubly linked list structure is worse than a singly linked list if we plan to print the entire list

frequently.

$($d$)$ An array implementation of a queue is more difficult to manage than the array implementation

of a stack.

Solution: $(40$ points$)$ Parenthesis Matching

Each $"(","\{",$ or $"["$ must be paired with a matching $")","\}",$ or $"["$

correct:

correct:

incorrect: $)$

incorrect: $(\{[])\}$

incorrect: $($

Let S be an empty stack

for i$=0$ to n$-1$ do

if X$[$i$]$ is an opening grouping symbol then S$.$push$($X$[$i$])$

else if X$[$i$]$ is a closing grouping symbol then

if S$.$isEmpty$()$ then return false $//$ nothing to match with

if S$.$pop$()$ not match X$[$i$]$ then return false $//$ wrong type

if S$.$isEmpty$()$ then return true $//$ every symbol matched

else return false $//$ some symbols were never matched

$($a$)$ Please the above Pseudocode into Java Code "MatchDelimiters.java".

$($b$)$ Test your code with the above examples and provide a screenshot of your running result.

Solution: $(40$ points$)$ Describe how to implement the stack ADT using a single queue as an instance

variable, and only constant additional local memory within the method bodies. What is the running

time of the push$(),$ pop$(),$ and top$()$ methods for your design?

Solution: