Data Structure Basics: Arrays, Stacks, Queues, Trees, and Hash Tables

This article is written for teaching. Examples are intentionally small; in production C++, prefer a suitable standard-library container unless a custom implementation has a measured reason to exist.

Learning data structures can look like memorizing names such as push, pop, and linked-list nodes. The real skill is deciding how to arrange data so that the operations a program performs most often become simple, cheap, and predictable.

The same ten values may belong in an array when indexed access dominates, a stack when the latest action must be undone, a queue when the oldest request goes first, or a hash table when lookup happens by key. This article connects those choices from memory layout to practical C++ interfaces.

Data structures and abstract data types

A stack is a rule: the most recently inserted item is removed first. It can be implemented with a contiguous array or a linked list. The visible operations and rules form an abstract data type; the concrete storage is its implementation.

A typical stack offers:

• push to insert at the top;
• pop to remove the top item;
• top or peek to inspect it without removal;
• empty to test whether an item exists;
• size to report the count.

C++ std::stack is a container adapter. Its default underlying container is std::deque, but another compatible container may be selected.

A minimal complexity vocabulary

Big O is not the entire performance story. Memory use, cache locality, allocation, iterator invalidation, and implementation complexity also matter.

Arrays use contiguous storage

int scores[5] = { 10, 20, 30, 40, 50 };

Given the base address and element size, the address of index i can be computed directly.

address(i) = base + i × sizeof(element)

Indexing is therefore O(1), and contiguous traversal is often cache-friendly. Inserting in the middle requires shifting later values, so it is O(N) in the worst case.

For a fixed-size C++ array with container-style operations, use std::array.

std::array<int, 5> scores { 10, 20, 30, 40, 50 };

Dynamic arrays and std::vector

std::vector is usually the first general-purpose sequence to consider in C++.

std::vector<int> values;
values.push_back(10);
values.push_back(20);
values.push_back(30);

A vector tracks its contiguous storage, current size, and available capacity. Appending while capacity remains is constant-time. When space runs out, it allocates a larger block and moves existing elements. One reallocation is O(N), but a long series of push_back operations is amortized O(1) per insertion.

std::vector<int> values;
values.reserve(1'000);

reserve can reduce reallocations when the approximate count is known. Reallocation may invalidate pointers, references, and iterators to old elements, a common source of bugs.

Linked lists connect separate nodes

struct Node
{
    int value;
    Node* next;
};

If a node is already known, inserting directly after it changes only a few links and is O(1).

void insertAfter(Node* current, Node* newNode)
{
    newNode->next = current->next;
    current->next = newNode;
}

Finding the hundredth element still requires walking through the previous nodes, so random access is O(N). Lists also spend memory on links, often have weaker cache locality, and make ownership harder in hand-written implementations.

“Many insertions” alone does not prove that a list beats a vector. Include the cost of finding the insertion point and actual memory behavior. C++ provides std::forward_list and std::list when their guarantees fit.

Stacks remove the latest item first

A stack follows LIFO, Last In First Out.

std::stack<int> numbers;
numbers.push(10);
numbers.push(20);
numbers.push(30);

int top = numbers.top();
numbers.pop();

top is 30, and the stack then contains 10 and 20.

pop does not return the value

In C++, std::stack::pop() removes the top element and returns void. Read first, then remove.

if (!numbers.empty())
{
    int value = numbers.top();
    numbers.pop();
    use(value);
}

Never call top or pop on an empty stack. Separating access from removal also gives the interface clearer behavior when copying or moving a value can fail.

A small vector-backed stack

template <typename T>
class SimpleStack
{
public:
    void push(const T& value) { values_.push_back(value); }

    void pop()
    {
        if (values_.empty()) throw std::underflow_error("empty stack");
        values_.pop_back();
    }

    T& top()
    {
        if (values_.empty()) throw std::underflow_error("empty stack");
        return values_.back();
    }

    bool empty() const { return values_.empty(); }
    std::size_t size() const { return values_.size(); }

private:
    std::vector<T> values_;
};

push, pop, and top are amortized or direct O(1) operations here.

Common uses for a stack

• function calls and local state;
• undo history;
• matching brackets;
• depth-first search;
• postfix-expression evaluation;
• replacing recursion with iteration.

Bracket matching demonstrates LIFO clearly: each opening bracket is pushed, and a closing bracket must match the most recent opening one.

Queues remove the oldest item first

A queue follows FIFO, First In First Out.

std::queue<int> jobs;
jobs.push(101);
jobs.push(102);
jobs.push(103);

int first = jobs.front();
jobs.pop();

first is 101. As with stack, pop() removes without returning the value.

Queues fit task scheduling, message processing, printer jobs, breadth-first search, and packet buffering.

Circular buffers

Removing the first element of a plain array by shifting everything is expensive. A queue can instead track separate head and tail indexes. When an index reaches the physical end, modular arithmetic reuses space at the beginning.

tail = (tail + 1) % Capacity;
head = (head + 1) % Capacity;

A fixed-capacity ring buffer is useful for audio, game events, and bounded producer-consumer pipelines. Multiple threads require synchronization or a purpose-built concurrent queue; index arithmetic alone is not thread safety.

Deques use both ends

Deque means double-ended queue. It supports insertion and removal at both front and back.

std::deque<int> values;
values.push_front(10);
values.push_back(20);
values.pop_front();
values.pop_back();

It is useful for work-stealing schedulers, sliding windows, and bidirectional queues. A std::deque is not guaranteed to occupy one contiguous block like a vector.

Priority queues use priority, not arrival order

std::priority_queue<int> scores;
scores.push(30);
scores.push(10);
scores.push(50);

int highest = scores.top();
scores.pop();

highest is 50. A priority queue is usually backed by a heap. Inspecting the top is O(1); insertion and removal of the top are O(log N). Typical uses include pathfinding frontiers, event simulation, and job priorities.

Hash tables map keys to buckets

std::unordered_map<std::string, int> health;
health["knight"] = 120;
health["mage"] = 70;

int mageHealth = health.at("mage");

A hash function chooses a bucket. With a reasonable distribution and load factor, lookup, insertion, and deletion are average O(1). Different keys can collide, so implementations need chaining or open addressing.

Worst-case lookup can be O(N). The hash quality, bucket count, and whether an attacker controls keys can matter. For a custom key, equality and hashing must agree: equal keys must have equal hashes.

Trees represent hierarchy

struct TreeNode
{
    std::string name;
    std::vector<std::unique_ptr<TreeNode>> children;
};

Trees fit file systems, UI widgets, scene graphs, and document structure. A root has no parent, a leaf has no children, depth measures distance from the root, height measures distance to a deepest leaf, and a subtree contains a node and all descendants.

Binary search trees

A binary search tree has at most two children per node. A common rule stores smaller keys in the left subtree and larger ones in the right.

When balanced, search, insertion, and deletion are O(log N). Inserting sorted keys into a naive tree can make it a long chain and degrade operations to O(N). Ordered standard containers therefore commonly use a self-balancing tree.

std::map<std::string, int> scores;
scores["alice"] = 90;
scores["bob"] = 80;

std::map preserves key order with O(log N) operations. If order is unnecessary and average constant lookup matters more, consider std::unordered_map.

Heaps are only partially ordered

In a max-heap, every parent is at least as large as its children. A min-heap reverses the rule. Siblings and the entire collection are not fully sorted.

A complete binary tree maps efficiently to an array. For zero-based index i:

left child  = 2 × i + 1
right child = 2 × i + 2
parent      = (i - 1) / 2

Insertion appends and performs sift up. Removing the root moves the last element to the root and performs sift down. A heap is excellent for repeatedly taking a minimum or maximum, but searching for an arbitrary value remains O(N).

Tries store prefixes

A trie uses characters or bits of a key as a path. car, card, and care can share the path for car. Search depends mainly on key length L, commonly described as O(L), but a large child representation can consume substantial memory. Tries fit autocomplete, dictionaries, prefix search, and routing tables.

Graphs represent general relationships

A graph consists of vertices and edges. Edges may be directed or undirected and may carry weights such as distance or cost.

An adjacency matrix stores a V × V table. Edge testing is O(1), while memory is O(V²), making it suitable for dense graphs.

An adjacency list stores each vertex's neighbors.

using Graph = std::vector<std::vector<int>>;

Graph graph(4);
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(3);

It uses about O(V + E) memory and fits sparse graphs. Breadth-first search uses a queue; depth-first search uses recursion's call stack or an explicit stack.

Representative complexity table

Actual guarantees depend on the implementation and preconditions.

How to choose

Ask:

1. Which operation occurs most often?
2. Must order be preserved?
3. Is indexed access required?
4. Is lookup by key, or is repeated minimum/maximum access needed?
5. Is the maximum count known?
6. Must pointers and references remain stable?
7. Does an external API require contiguous memory?
8. Will multiple threads access the structure?

For an ordinary sequence of values, begin with std::vector. Move to another structure when a concrete requirement justifies it.

Common mistakes

• Calling top, front, or pop on an empty container.
• Assuming C++ pop returns the removed value.
• Keeping vector pointers across a reallocation.
• Assuming a linked list is always faster for insertion while ignoring how the position is found.
• Describing every hash-table operation as guaranteed O(1).
• Ignoring call-stack depth in recursive traversal.
• Building an ownership graph with raw pointers and no clear deletion policy.

Practice exercises

1. Implement a stack with one vector and define its empty-state policy.
2. Implement a fixed-size circular queue and distinguish full from empty.
3. Validate brackets with a stack.
4. Find the shortest number of grid steps with a queue.
5. Count words with unordered_map.
6. Remove the three smallest values from a min-heap.
7. Traverse an adjacency-list graph with BFS and DFS.
8. Benchmark middle insertion in vector and list, including the cost of finding the position.

Summary

Arrays and vectors provide fast indexed access and strong locality. Linked lists make link changes cheap at a known position but pay for traversal and scattered memory. Stacks serve newest-first work, queues oldest-first work, deques both ends, and priority queues the most important item. Hash tables provide fast average key lookup, balanced trees preserve order, heaps repeatedly expose an extreme value, and graphs model general connections.

The best data structure is not the most elaborate one. It is the one that makes the program's real operations clear and predictable.