Using std::vector as a Stack

std::vector and stack behavior

When collecting user input of unknown quantity, pre-sizing the vector is impractical. Stack operations provide an elegant solution.

The input collection problem

Suppose you're building a gradebook application where teachers enter student scores. You don't know in advance how many scores they'll enter. Several approaches exist, but all have drawbacks:

• Pre-ask for count: Forces users to count entries manually
• Guess maximum size: Wasteful and artificially limiting
• Manual resize logic: Mixes array management with program logic

There's a better way: stack operations.

Understanding stacks

Imagine a dispenser holding cafeteria trays. Due to the heavy trays, you can only interact with the top tray:

1. Place a new tray on top (hiding the one below)
2. Remove the top tray (exposing the one below)

You cannot access middle or bottom trays without first removing trays above them.

This describes last-in, first-out (LIFO) ordering: the last tray added is the first removed.

Stacks in programming

A stack is a container following LIFO ordering, implementing two core operations:

Common optional operations:

C++ adds stack capabilities to existing containers rather than creating separate stack types. This provides both stack operations and the container's native functionality.

Stack operations on std::vector

std::vector implements stack behavior through these methods:

Example:

#include <iostream>
#include <vector>

void display(const std::vector<int>& stack)
{
    if (stack.empty())
        std::cout << "Empty";

    for (auto val : stack)
        std::cout << val << ' ';

    std::cout << "  Capacity: " << stack.capacity()
              << " Length: " << stack.size() << '\n';
}

int main()
{
    std::vector<int> stack {};

    display(stack);

    stack.push_back(5);
    display(stack);

    stack.push_back(10);
    display(stack);

    stack.push_back(15);
    display(stack);

    std::cout << "Top: " << stack.back() << '\n';

    stack.pop_back();
    display(stack);

    stack.pop_back();
    display(stack);

    return 0;
}

Sample output:

Empty  Capacity: 0 Length: 0
5  Capacity: 1 Length: 1
5 10  Capacity: 2 Length: 2
5 10 15  Capacity: 4 Length: 3
Top: 15
5 10  Capacity: 4 Length: 2
5  Capacity: 4 Length: 1

Notice push_back() increments length and reallocates when necessary.

Reallocation with extra capacity

When pushing triggers reallocation, vectors often allocate extra capacity:

In the example above, the third push increased capacity from 2 to 4 (not just 3). This strategy reduces future reallocations:

• GCC/Clang: Doubles capacity
• Visual Studio: Multiplies capacity by 1.5

This explains varying output across compilers.

Why resize() doesn't work for stacks

You might try pre-allocating capacity with resize:

#include <iostream>
#include <vector>

void display(const std::vector<int>& stack)
{
    for (auto val : stack)
        std::cout << val << ' ';
    std::cout << "  Capacity: " << stack.capacity()
              << " Length: " << stack.size() << '\n';
}

int main()
{
    std::vector<int> stack(3);  // Resize to 3

    display(stack);

    stack.push_back(5);
    display(stack);

    stack.push_back(10);
    display(stack);

    return 0;
}

Output:

0 0 0  Capacity: 3 Length: 3
0 0 0 5  Capacity: 6 Length: 4
0 0 0 5 10  Capacity: 6 Length: 5

The problem: resize() sets both capacity AND length, creating three zero-initialized elements. Pushing adds elements after these zeros.

Using reserve() for stack operations

reserve() increases capacity without changing length:

#include <iostream>
#include <vector>

void display(const std::vector<int>& stack)
{
    if (stack.empty())
        std::cout << "Empty";

    for (auto val : stack)
        std::cout << val << ' ';

    std::cout << "  Capacity: " << stack.capacity()
              << " Length: " << stack.size() << '\n';
}

int main()
{
    std::vector<int> stack {};

    display(stack);

    stack.reserve(10);  // Reserve capacity without changing length
    display(stack);

    stack.push_back(5);
    display(stack);

    stack.push_back(10);
    display(stack);

    return 0;
}

Output:

Empty  Capacity: 0 Length: 0
Empty  Capacity: 10 Length: 0
5  Capacity: 10 Length: 1
5 10  Capacity: 10 Length: 2

Perfect! The capacity increased without creating unwanted elements.

push_back() vs emplace_back()

When the object already exists, use push_back():

int value { 42 };
stack.push_back(value);  // Preferred

When creating a temporary to push, emplace_back() can be more efficient:

stack.push_back({ "Hello", 5 });  // Creates temporary, then copies
stack.emplace_back("Hello", 5);   // Constructs directly in vector (no copy)

emplace_back() forwards arguments to construct the object in-place, avoiding copies for expensive types.

Solving the input collection problem

Stack operations elegantly handle unknown input quantities:

#include <iostream>
#include <limits>
#include <vector>

int main()
{
    std::vector<int> grades {};

    std::cout << "Enter grades (-1 to finish): ";

    while (true)
    {
        int grade {};
        std::cin >> grade;

        if (!std::cin)
        {
            std::cin.clear();
            std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
            continue;
        }

        if (grade == -1)
            break;

        grades.push_back(grade);
    }

    std::cout << "You entered " << grades.size() << " grades: ";
    for (const auto& g : grades)
        std::cout << g << ' ';
    std::cout << '\n';

    return 0;
}

No counting, no pre-sizing, no manual memory management—just pure logic!

Summary

Stack behavior: A stack is a last-in, first-out (LIFO) container that supports push (add to top) and pop (remove from top) operations. C++ adds stack functionality to existing containers like std::vector rather than creating separate stack types.

Vector stack operations: push_back() and emplace_back() add elements to the end, pop_back() removes the last element, and back() views the last element without removing it. These operations automatically manage vector length and capacity.

The input collection problem: When collecting unknown quantities of input, stack operations provide an elegant solution. Users can enter items one by one, with each entry automatically added via push_back() without pre-determining array size.

resize() vs reserve(): resize() changes both length and capacity, creating elements that occupy indices. reserve() only changes capacity without creating elements, making it appropriate when using stack operations to build up a vector.

push_back() vs emplace_back(): Use push_back() when pushing existing objects. Use emplace_back() when constructing objects in-place from arguments, which avoids unnecessary copies for expensive types.

Reallocation strategies: When push_back() triggers reallocation, implementations typically allocate extra capacity (GCC/Clang double capacity, Visual Studio multiplies by 1.5) to reduce future reallocation frequency.

Stack operations transform std::vector from a simple array into a powerful, self-managing data structure perfect for scenarios where the final size isn't known upfront.