Stack (Last-In-First-Out)

At a base level, a stack is simply a list data structure with a constrained set of methods that make it uniquely suited for some programming tasks. These methods are push, which adds an item to the head of the list and pop which removes and returns the item in the head position. The most common analogy is a stack of plates. You place a plate on top of the stack, and you must retrieve the last plate placed on the stack before you can access plates below it. In software parlance, a stack is known as a Last-in-First-Out data structure because the last item pushed on the stack is the first one out (clever, huh?).

Typically, a Linked List is used when implementing a stack. However, an Array is also a viable option. The reader is encouraged to examine the accompanying code to get a better understanding of how stacks work.

Applications

  • Memory Management: Operating systems use a stack for managing memory.
  • Backtracking: Keep track of tasks so they can be undone if necessary. Think of what happens when you press ctrl+z while using MS Word, or u when using VIM.
  • Graph Depth First Search

Asymptotic Complexity

  • Push: $O(1)$
  • Pop: $O(1)$

Pseudo Code

push:
    Adds an item to the head of the list

pop:
    Remove item from the head the list and returns it

peek:
    Return item from the head without removing it from the list

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions

Source Code