Stacks

A stack is a type of data structure where the last item you add to the data structure will be the first item that gets removed from the data structure. It is thus referred to as a LIFO (last in, first out) structure. Stacks are generally implemented in two ways, the first of which, arrays, will be covered in this section. They can also be easily implemented by way of linked lists. Stacks have two operations that can be performed on them: pushing (adding an item to the stack) and popping (removing the most-recently added item from the stack).

• Lecture

  • Watch on Youtube
  • Watch on the CS50 Video Player
  • Download Lecture
  • Lecture Notes

• Short

  • Stacks

• Supplementary Resources

  • Michael Olorunnisola on How Stacks Work
  • Omar El Gabry on Stacks and Queues
  • Joe Birch on Data Structures: Stacks & Queues

• Thought Questions

  • What are some stack-like situations in the real world? (Hint: Think about a stack of trays or dinner plates, how the “delete” key works on your computer or the “back” button on your browser, or how and when you’d get off a crowded bus.)
  • In what situation would a LIFO data structure, such as a stack, offer advantages? When is it not the best way to store information? Why not?
  • Write some pseudocode for implementing a stack or draw it out, highlighting which specific elements are being added and removed at different points in time.