CS 371: Recursion Module: Stacks And Queues
Module content developed by Professor Tralie. Module engine developed by Professor Tralie and Professor Mongan.
Read section 6.2, 6.3, and 7.3 in the Sheehy book to review stacks, queues, and how both can be implemented with linked lists. Make sure you can explain the following:
- A stack can be implemented with a linked list so that both push and pop are O(1)
- A queue has to be implemented with a doubly-linked list so that both enqueue (adding to the end of the line) and dequeue (removing from the front of the line) are both O(1). Please review ch. 8 if you need more practice with doubly-linked lists. Luckily, all of these sections are only a couple of pages!
When you feel comfortable with all of this, move on to the warm-up video and exercise for the class activity on Friday on the following pages