SubstitutePlans.com · Teacher phone guide

Stacks and Queues by Hand: Last In First Out, First In First Out

SP-CS-019 · Grades 9-12 · 45 minutes

Teacher directions only. Student worksheets and the answer key are in the complete teacher PDF. This downloaded guide opens offline.

SubstitutePlans.com
Technology and Computer Science • Computer Science
SP-CS-019  •  Free to print and use in your classroom  •  substituteplans.com

Stacks and Queues by Hand: Last In First Out, First In First Out
Technology and Computer Science • Computer Science • Grades 9-12 • 45 minutes

Time needed: 45 minutes (one class period)
Prep: Copy the 3-page worksheet (one per student). No computers needed.
Technology: None.
Student independence: High. Individual tracing and problem solving.
Copies to make: One 3-page worksheet per student
Materials: Pencils, Worksheet

Goal for today: Students will describe the operations of a stack (push, pop, peek) and a queue (enqueue, dequeue), trace a sequence of operations to the final contents, and choose the right structure for a real-world problem.

BEFORE THE BELL
☐ Copy the worksheet, one per student (3 pages).
☐ Write on the board: STACK = LIFO (last in, first out), like a stack of plates. push = add to top, pop = remove from top, peek = look at top.
☐ Write: QUEUE = FIFO (first in, first out), like a line at a store. enqueue = join the back, dequeue = leave from the front.

SAY THIS TO START
Computers store lists of things in a few standard shapes, and two of the simplest are a stack and a queue. One works like a pile of plates, the other like a line at the store. Today you will run both by hand, use a stack to catch a very common coding bug, and decide which shape fits real problems.

RUN OF SHOW
0–5 min - YOU: Take attendance. Hand out the worksheet and read the two definitions on the board.
      STUDENTS: Follow along.
5–12 min - YOU: Students read page 1 and the two worked traces.
      STUDENTS: Read the examples.
12–28 min - YOU: Students complete Part A (stack traces) and Part B (queue traces). Walk the room; check that pops come from the top and dequeues from the front.
      STUDENTS: Trace the operations.
28–38 min - YOU: Students complete Part C (bracket matching) and Part D (which structure?).
      STUDENTS: Apply a stack; choose structures.
38–44 min - YOU: Read the answers from the key. Ask: why does the bracket check need a stack and not a queue?
      STUDENTS: Check and discuss.
44–45 min - YOU: Collect worksheets.
      STUDENTS: Hand in the worksheet.

IF THINGS GO WRONG
• If students remove from the wrong end, have them redraw the structure vertically (stack) or horizontally (queue) and label top or front.
• If students ask what happens when you pop an empty stack, say it is an error in most languages, and the bracket check uses that fact.
• If a student finishes early, use the early finisher list.

EARLY FINISHERS
• Trace this with a stack: push A, push B, pop, push C, push D, pop, pop, peek. Write the final contents and everything that was popped.
• Design a queue trace of six operations that ends with exactly one item, and give the final answer.

SUPPORT AND CHALLENGE
• Support: Let students draw boxes for every step of the traces and skip problem 9.
• Challenge: Ask students to describe how to reverse a queue using only a stack, step by step.

NOTES FOR THE TEACHER (you fill this in)
How far the class got / what to pick up next:
Students who were especially helpful:
Anything the teacher should know:

The complete PDF has the student worksheet (pages 4-6) and the answer key (page 7).