Chapter 5b - Data Structures

Why Data Structures?

A data structure is a way of organizing data in memory so that operations on it (insert, delete, search) are efficient. Choosing the right one is one of the most important decisions in software engineering.

Structure	Access	Insert/Delete	Search	Use when
Array / vector	O(1)	O(n) (middle)	O(n)	Random access, cache-friendly
Linked List	O(n)	O(1) (at known node)	O(n)	Frequent insert/delete, unknown size
Stack	O(1) top	O(1)	—	LIFO: undo, call stack, DFS
Queue	O(1) front	O(1)	—	FIFO: task queue, BFS
Map (unordered_map)	O(1) avg	O(1) avg	O(1) avg	Key-value lookup

---

Arrays (Fixed Size)

C-style arrays have a fixed size set at compile time.

int scores[5] = {90, 85, 78, 92, 88};

cout << scores[2] << endl;   // 78

for (int i = 0; i < 5; i++) {
    cout << scores[i] << " ";
}

---

Mini quiz — arrays

Quiz

Why structures, and arrays

1 / 3

A data structure is mainly…

Pick an answer to see if you are right.

---

vector — Dynamic Array (STL)

std::vector is a resizable array. Prefer it over raw arrays almost always.

#include <vector>
using namespace std;

vector<int> nums = {1, 2, 3};

nums.push_back(4);    // append
nums.push_back(5);

cout << nums.size() << endl;   // 5
cout << nums[2]     << endl;   // 3

Iterating a Vector

for (int n : nums) {
    cout << n << " ";
}

🧪 Vector operations

---

Linked List (Manual Implementation)

A linked list is a chain of nodes, each holding data and a pointer to the next node.

struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

🧪 Linked list

---

Mini quiz — vector and lists

Quiz

vector and linked lists

1 / 3

std::vector can…

Pick an answer to see if you are right.

---

Stack

A stack is LIFO (Last In, First Out) — like a stack of plates. Use std::stack from <stack>.

#include <stack>

stack<int> s;
s.push(1);
s.push(2);
s.push(3);
cout << s.top() << endl;   // 3
s.pop();

Application: Balanced Parentheses

🧪 Balanced parentheses

---

Challenge: balanced parens

Finish isBalanced so it returns yes if every ( ) pair matches, otherwise no. Only round parentheses are tested.

Input	Return
()	yes
(()	no

---

Queue

A queue is FIFO (First In, First Out) — like a line of people. Use std::queue from <queue>.

#include <queue>

queue<string> q;
q.push("Alice");
q.push("Bob");
cout << q.front() << endl;  // Alice
q.pop();

Application: Print Queue Simulation

🧪 Print queue

---

Map (Hash Map / Dictionary)

std::unordered_map stores key-value pairs with O(1) average access.

#include <unordered_map>

unordered_map<string, int> ages;
ages["Alice"] = 22;
ages["Bob"]   = 19;
cout << ages["Alice"] << endl;  // 22

Word Frequency Counter

🧪 Word frequency

---

Mini quiz — queue and map

Quiz

Queue and map

1 / 3

A queue is…

Pick an answer to see if you are right.

---

set — Unique Sorted Elements

#include <set>

set<int> s = {3, 1, 4, 1, 5, 9, 2, 6, 5};
for (int x : s) cout << x << " ";
// Output: 1 2 3 4 5 6 9

🧪 set

---

Choosing a Container

Do you need key-value pairs?
  YES → unordered_map (fast) or map (sorted)
  NO  →
    Do you need unique elements?
      YES → unordered_set or set
      NO  →
        Do you need LIFO?  → stack
        Do you need FIFO?  → queue
        Otherwise          → vector (default choice)

---

Mini quiz — set and choosing containers

Quiz

set and container choice

1 / 3

A set stores…

Pick an answer to see if you are right.

---

Exercises

Activity: Implement a Stack with a Linked List

Without using std::stack, implement a Stack<int> class backed by a linked list with push, pop, top, and isEmpty methods.

📒 Solution