AS Knowledge
← Back to Topics

Data Structures

Stacks, queues, binary search trees, and priority queues.

Overview

Data structures are fundamental building blocks in computer science that help organize and store data efficiently. They work hand-in-hand with algorithms - data structures store the data, while algorithms process it.

Core Data Structures in ACSL:

  • Stacks: Last-In-First-Out (LIFO) structure
  • Queues: First-In-First-Out (FIFO) structure
  • Binary Search Trees: Hierarchical structure for efficient searching
  • Priority Queues: Special queue where items have priorities

Key Concepts

Stacks

Key Operations:

Real-world Example: Think of a stack of books - you can only add or remove books from the top.

When POP() is called on an empty stack, it returns NIL (or null).

Queues

Key Operations:

Real-world Example: Like a line at a store - first person to arrive is the first person served.

Items enter at the rear (back) and leave from the front, just like a real queue of people.

Binary Search Trees (BST)

Key Properties:

Important Terms:

Tree Traversals:

Remember:

  • If new value < current node: Go left
  • If new value > current node: Go right
  • If spot is empty: Insert there
  • If duplicate value: Go left (ACSL convention)

Priority Queues

Key Features:

Heap Properties:

Common Operations:

  1. Insert(value):
    • Add at next available spot (left to right)
    • Swap up while parent is larger (bubble-up)
  2. RemoveMin():
    • Take root value (always smallest in min-heap)
    • Move last element to root
    • Swap down with smaller child until heap property restored

Remember:

  • Parent of node at index i is at (i-1)/2
  • Children of node at index i are at 2i+1 and 2i+2
  • Always maintain complete tree shape
  • For min-heap: Parent always smaller than children
  • For max-heap: Parent always larger than children

Examples

Stack operations
  • Ex. PUSH(3) on the stack [1,7,2] results in [1,7,2,3]
  • Ex. X=POP() on the stack [3,8,1,8] results in [3,8,1] and X=8
Queue operations
  • Ex. PUSH(5) on the queue [9,2,5] results in [9,2,5,5]
  • Ex. X=POP() on the queue [5,4,7,1] results in [4,7,1] and X=5
Example: Creating a BST with the word "STACK"

Let's build a BST by inserting one letter at a time:

  1. Insert S (root): 
           S
  2. Insert T (greater than S): 
           S
        \
         T
  3. Insert A (less than S): 
           S
      / \
     A   T
  4. Insert C (less than S, greater than A): 
           S
      / \
     A   T
      \
       C
  5. Insert K (less than S, greater than A, greater than C): 
           S
      / \
     A   T
      \
       C
        \
         K

Tree Analysis:

  • Root node: S (depth 0)
  • First level: A, T (depth 1)
  • Second level: C (depth 2)
  • Third level: K (depth 3)
  • Internal path length = 0 + 2(1) + 1(2) + 1(3) = 7
  • Inorder traversal: A, C, K, S, T (alphabetical order)
Example: Building a Min-Heap with numbers [8,3,5,1,4]

Let's build a min-heap by inserting one number at a time:

  1. Insert 8: Becomes root 
           8
  2. Insert 3: Less than 8, swap up 
           3
      /
     8
  3. Insert 5: Goes right, no swap needed 
           3
      / \
     8   5
  4. Insert 1: Goes left, then swaps up twice 
    Before swap:     After swaps:
       3              1
      / \            / \
     8   5    →     3   5
    /              /
   1              8
  5. Insert 4: 
           1
      / \
     3   5
    / \
   8   4

Practice Problems

Problem 1 Junior

List the nodes at depth 5 of the binary search tree of the string "WATERBOTTLE" from left to right, capitalized.

Problem 2 Junior

Given an initially empty queue and the following sequence of operations, what would be the next POPPED element?
PUSH(G), PUSH(I), PUSH(N), PUSH(N), POP(X), POP(X), POP(X),
PUSH(G), PUSH(E), PUSH(E), PUSH(R), POP(X), POP(X), PUSH(D),
PUSH(O), POP(X), POP(X), POP(X), PUSH(G), PUSH(O), PUSH(O),
POP(X), POP(X), POP(X), PUSH(G), PUSH(E), POP(X)

Problem 3 Intermediate

How many nodes only have one child in the binary search tree for RAINSTORMS?

Problem 4 Intermediate

List the nodes in the bottom row of the min-heap (priority queue) of the word BLANKET from left to right, capitalized.

Problem 5 Senior

Find the internal path length of the binary search tree for KALEIDOSCOPE.