CS 271: 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 an exercise involving stacks and queues on the next page

---