Föreläsning 4

Question 1

När man tar ut ett element från en stack (med pop) får man:

Answer 1

Det senast inlagda elementet

Question 2

När man tar ut ett element från en kö (med dequeue) får man:

Answer 2

Det tidigast inlagda elementet (av de som finns kvar)

Question 3

Vad skrivs ut (med print) här:

stack.push(A)
stack.push(B)
print(stack.pop())
stack.push(C)
stack.push(D)
print(stack.pop())

Answer 3

B, D

Question 4

Vad skrivs ut (med print) här:

stack = create_empty_queue()
queue.push(A)
queue.push(B)
print(queue.pop())
queue.push(C)
queue.push(D)
print(queue.pop())

Answer 4

A, B

Question 5

Vad är sant om operationerna för att lägga till eller ta bort element till en självexpanderande array (som ResizingArrayStack-implementationen på föreläsningen, där operationerna är push och pop)?

Answer 5

• I värsta fall är tiden för en operation linjär i antalet element
• Den amorterade tiden för operationerna är konstant