Held: Friday, 7 November 2014

Back to Outline 36 - Doubly-Linked Lists. On to Outline 38 - Implementing Queues with Arrays.

Summary

We consider a general class of collections called "linear structures". We explore one kind of linear structure, the stack, in a bit more depth.

Related Pages

• Reading: Linear Structures
• Reading: Stacks
• Lab: Stacks
• Repository: https://github.com/Grinnell-CSC207/linear
• EBoard 37 (Source 37) (HTML 37)

Overview

• Linear structures.
• Stacks.
• An application of stacks: Matching parens.

Administrivia

• Continue lab partners.
• Extended office hours continue next week.
• Sorry that I could not be here today. Be nice to Mira.

Upcoming Work

• Homework 9: Skip Lists due Wednesday.
• Reading for Monday.
  • Queues

Cool Upcoming Events on Campus

• Peace studies talk Monday at 4:15 p.m. in JRC 101 "With All the World’s Violence, Where is Peace?"

Extra Credit

Academic

• CS Table Friday: Open Data.
• Convocation Wednesday at noon: Dean Latham.
  • Convo returns to the awesome time of 11:00 a.m. on Thursdays starting in Fall 2015!
• Wednesday one week: 7:30 p.m. Internship panel with Nelson, Mira, and Lea.

Peer Support

• Ajuna's Radio show Mondays at 8pm. Listen to African music.
• Ezra's Radio show Thursdays at midnight. Radio melodrama.
• Charlie's Friday Night "War in Animated Film" ExCo. tonight!
• Womens soccer game today, 2:00 p.m., at Lake Forest.

Linear Structures

• Simple collections.
• Two basic operations: put and get.
• Sam thinks of linear structures as a magic box. You give the box a policy for returning values and it folows that policy when you get something.

Stacks

• Linear structures with a "last in, first out" policy.
• Terminology: put is called push; get is called pop.
• Can be implemented with arrays or linked structures.

Lab

• Read code.
• Fix code.
• Use code.