03 Stacks and Queues

Stacks and Queues

1. Stacks - Liyosi

Tuesday: Feb 23, 2021, 8:00 - 9 am EAT

Content and Plan

ℹ Have a time keeper

Tools

• Use python and python notebook: Jupyter notebook

Lesson plan

• 5 min: ice-break : This is Better Than That ​

  • Stranded on a small desert island with Godzilla.​
  • Your objective is survival.​
  • You have 4 objects: matchstick, rope, bottle of water and a knife. [2]​
  • Rank each object based on usefulness.​
  • Explain your reasoning.​

• 10 min: warm up challenge - Evaluate a mathematical expression

• 10 min: Introduce stack data structure:

  • LIFO concept
  • Stack operations: push, pop
  • Example of Stacks
    • Plates
    • Browser history

• 20 min: How it's implemented

  • Array based implementation:
  • LinkedList based implementation

• 10 min: Applications/Use cases for stacks:

  • Function invocation (Recursion - later)

Assignments

• Complete these assignments by Thursday 02/25.

Further reading

• https://introcs.cs.princeton.edu/java/43stack/
• https://app.codility.com/programmers/lessons/7-stacks_and_queues/

2. Queues - George

Thursday: Feb 24, 2021, 8:00 - 9 am EAT

ℹ Have a time keeper

Tools

• Use python and python notebook

Lesson plan

• 5 min: ice-break

• 10 min: warm up challenge - // todo

  • Bank queue analogy (FIFO)

• 10 min: Introduce queue data structure:

  • Queue
  • Deque (Homework item)
  • Priority Queues( Just mention)

• 20 min: How it's implemented

  • Gradual progress from fundamentals (lists)
  • Better ways to implement

• 10 min: Applications/Use cases for queues:

  • Fair scheduling (how we can actually achieve true fairness - priority queue)

Further reading

• Dequeu
• priority queue
• alternative implementations(using linked list)
• https://app.codility.com/programmers/lessons/7-stacks_and_queues/

In-class challenges

• Looking for balancing parenthesis
• // todo

Assignments

• Implement a queue using a two stacks - Finish add hackerrank challenge by Monday 03/01.

Further reading

• https://introcs.cs.princeton.edu/java/43stack/
• https://medium.com/techie-delight/queue-data-structure-practice-problems-and-interview-questions-f459bf0578db

Todo

• Do a jupyter notebook for queues (G) and stacks(C) (From 11:30 - 12: 30 dry run)