Stack

Table of Contents

A stack is like a stack of plates. It's "last in, first out" (LIFO), which means that the item that…

Quick reference

A stack stores items in a last-in, first-out (LIFO) order.

Picture a pile of dirty plates in your sink. As you add more plates, you bury the old ones further down. When you take a plate off the top to wash it, you're taking the last plate you put in. "Last in, first out."

Stengths:

  • Fast operations. All stack operations take O(1) time.

Uses:

  • The call stack is a stack that tracks function calls in a program. When a function returns, which function do we "pop" back to? The last one that "pushed" a function call.
  • Depth-first search uses a stack (sometimes the call stack) to keep track of which nodes to visit next.
  • String parsing – stacks turn out to be useful for several types of string parsing.
Table 1: Worst Case
space O(n)
push O(1)
pop O(1)
peek O(1)

Implementation

You can implement a stack with either a linked list or a dynamic array – they both work pretty well:

  Stack Push Stack Pop
Linked Lists insert at head remove at head
Dynamic Arrays append remove last element

Date: 2020-01-30 Thu 23:43

Author: Jack Liu

Created: 2020-02-08 Sat 21:27

Validate