Homework 3

Due Monday, January 27 at 5:00 PM. Please refer to the homework policy here.

  1. Recall that a stack can be implemented as a linked list with time to push items onto the stack and pop items off of the stack. Show how to use stacks to implement a queue that supports enqueue and dequeue in amortized time.

    (This is used in functional programming languages (e.g., haskell) to build immutable queues using immutable lists.)