Class5.md

Class 5: Lists, Stacks & Queues

Minute-by-Minute [OPTIONAL]

NOTE: Fill in with the appropriate items

Elapsed	Time	Activity
0:00	0:05	Objectives
0:05	0:15	Overview
0:20	0:45	In Class Activity I
1:05	0:10	BREAK
1:15	0:45	In Class Activity II
TOTAL	2:00

Learning Objectives (5 min)

NOTE: Fill in with the appropriate items

By this end of this lesson, students should be able to...

1. Explain the use cases for stacks and queues, and why they may use them over a list
2. Differentiate between arrays and dynamic arrays, and when to use each.

Topics

• Compare abstract data types and concrete data structures
• Abstract data types: list, stack, queue, deque (double-ended queue)
• Concrete data structures: array, dynamic array (resizable array, vector), linked list

Resources

• Review Make School's stack and queue slides
• Watch Make School's stack and queue video lecture
• Read Vaidehi Joshi's articles on stacks and queues with beautiful drawings and excellent examples
• Watch HackerRank's stack and queue video
• Watch Harvard's stack video and queue video
• Play with VisuAlgo's interactive stack and queue visualization

Challenges

• Implement LinkedStack class (stack with linked list) and ArrayStack class (stack with dynamic array) using stack starter code:
  • Implement is_empty - check if the stack is empty
  • Implement length - return the number of items in the stack
  • Implement push(item) - insert item on the top of the stack
  • Implement peek - return the item on the top of the stack
  • Implement pop - remove and return the item on the top of the stack
  • Run pytest stack_test.py to run the stack unit tests and fix any failures
• Annotate push and pop methods with running time complexity analysis
• Implement LinkedQueue class (queue with linked list) and ArrayQueue class (queue with dynamic array) using queue starter code:
  • Implement is_empty - check if the queue is empty
  • Implement length - return the number of items in the queue
  • Implement enqueue(item) - insert item at the back of the queue
  • Implement front - return the item at the front of the queue
  • Implement dequeue - remove and return the item at the front of the queue
  • Run pytest queue_test.py to run the queue unit tests and fix any failures
• Annotate enqueue and dequeue methods with running time complexity analysis

Stretch Challenges

• Implement Deque class (double-ended queue) with doubly linked list or dynamic array (your choice):
  • Implement is_empty - check if the deque is empty
  • Implement length - return the number of items in the deque
  • Implement push_front(item) - insert item at the front of the deque
  • Implement push_back(item) - insert item at the back of the deque
  • Implement front - return the item at the front of the deque
  • Implement back - return the item at the back of the deque
  • Implement pop_front - remove and return the item at the front of the deque
  • Implement pop_back - remove and return the item at the back of the deque
• Write unit tests for to ensure the Deque class is robust
  • Include test cases for each class instance method
• Annotate push_front, push_back, pop_front, and pop_back methods with running time complexity analysis