16.11 — std::vector and stack behavior

In this lesson, you'll learn how to use std::vector as a stack data structure. You'll discover the stack operations that vectors provide naturally and understand when and how to leverage this functionality in your programs.

What is a stack?

A stack is a data structure that follows the LIFO (Last In, First Out) principle. Think of it like a stack of plates:

• You can only add plates to the top
• You can only remove plates from the top
• The last plate you put on is the first one you take off

Stacks support these fundamental operations:

• push: Add an element to the top
• pop: Remove the element from the top
• top: Look at the top element without removing it
• empty: Check if the stack is empty

std::vector as a stack

std::vector naturally supports stack operations through these member functions:

• push_back() → push operation
• pop_back() → pop operation
• back() → top operation
• empty() → check if empty

Basic stack operations

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> stack;
    
    std::cout << "Stack operations:" << std::endl;
    
    // Push elements (push_back)
    stack.push_back(10);
    std::cout << "Pushed 10, stack size: " << stack.size() << std::endl;
    
    stack.push_back(20);
    std::cout << "Pushed 20, stack size: " << stack.size() << std::endl;
    
    stack.push_back(30);
    std::cout << "Pushed 30, stack size: " << stack.size() << std::endl;
    
    // Look at top element (back)
    std::cout << "Top element: " << stack.back() << std::endl;
    
    // Pop elements (pop_back)
    stack.pop_back();
    std::cout << "Popped, new size: " << stack.size() << std::endl;
    std::cout << "New top element: " << stack.back() << std::endl;
    
    stack.pop_back();
    std::cout << "Popped, new size: " << stack.size() << std::endl;
    std::cout << "New top element: " << stack.back() << std::endl;
    
    // Check if empty
    std::cout << "Is stack empty? " << (stack.empty() ? "Yes" : "No") << std::endl;
    
    return 0;
}

Output:

Stack operations:
Pushed 10, stack size: 1
Pushed 20, stack size: 2
Pushed 30, stack size: 3
Top element: 30
Popped, new size: 2
New top element: 20
Popped, new size: 1
New top element: 10
Is stack empty? No

Creating a stack wrapper class

For better code organization and clearer intent, you can create a wrapper class:

#include <vector>
#include <iostream>
#include <stdexcept>

template<typename T>
class Stack
{
private:
    std::vector<T> data;
    
public:
    // Push element onto stack
    void push(const T& value)
    {
        data.push_back(value);
    }
    
    // Pop element from stack
    void pop()
    {
        if (empty())
        {
            throw std::runtime_error("Cannot pop from empty stack");
        }
        data.pop_back();
    }
    
    // Get top element
    T& top()
    {
        if (empty())
        {
            throw std::runtime_error("Cannot access top of empty stack");
        }
        return data.back();
    }
    
    const T& top() const
    {
        if (empty())
        {
            throw std::runtime_error("Cannot access top of empty stack");
        }
        return data.back();
    }
    
    // Check if stack is empty
    bool empty() const
    {
        return data.empty();
    }
    
    // Get stack size
    std::size_t size() const
    {
        return data.size();
    }
    
    // Display stack contents (for debugging)
    void display() const
    {
        std::cout << "Stack (bottom to top): ";
        for (const T& element : data)
        {
            std::cout << element << " ";
        }
        std::cout << std::endl;
    }
};

int main()
{
    Stack<std::string> wordStack;
    
    // Push words
    wordStack.push("first");
    wordStack.push("second");
    wordStack.push("third");
    
    wordStack.display();
    
    // Access and pop elements
    while (!wordStack.empty())
    {
        std::cout << "Top: " << wordStack.top() << std::endl;
        wordStack.pop();
        std::cout << "Stack size after pop: " << wordStack.size() << std::endl;
    }
    
    // Try to pop from empty stack (will throw exception)
    try
    {
        wordStack.pop();
    }
    catch (const std::runtime_error& e)
    {
        std::cout << "Error: " << e.what() << std::endl;
    }
    
    return 0;
}

Output:

Stack (bottom to top): first second third 
Top: third
Stack size after pop: 2
Top: second
Stack size after pop: 1
Top: first
Stack size after pop: 0
Error: Cannot pop from empty stack

Practical applications

Application 1: Expression evaluation (parentheses matching)

#include <vector>
#include <iostream>
#include <string>

bool isBalanced(const std::string& expression)
{
    std::vector<char> stack; // Using vector as stack
    
    for (char ch : expression)
    {
        if (ch == '(' || ch == '[' || ch == '{')
        {
            stack.push_back(ch); // Push opening brackets
        }
        else if (ch == ')' || ch == ']' || ch == '}')
        {
            if (stack.empty())
            {
                return false; // Closing bracket without matching opening
            }
            
            char top = stack.back();
            stack.pop_back();
            
            // Check if brackets match
            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{'))
            {
                return false;
            }
        }
    }
    
    return stack.empty(); // All brackets should be matched
}

int main()
{
    std::vector<std::string> expressions = {
        "(a + b)",
        "(a + b]",
        "((a + b) * c)",
        "((a + b) * c]",
        "{[(a + b) * c] + d}",
        "{[(a + b) * c + d}",
        ""
    };
    
    std::cout << "Bracket matching results:" << std::endl;
    
    for (const std::string& expr : expressions)
    {
        std::cout << "\"" << expr << "\" -> " 
                  << (isBalanced(expr) ? "Balanced" : "Not balanced") 
                  << std::endl;
    }
    
    return 0;
}

Output:

Bracket matching results:
"(a + b)" -> Balanced
"(a + b]" -> Not balanced
"((a + b) * c)" -> Balanced
"((a + b) * c]" -> Not balanced
"{[(a + b) * c] + d}" -> Balanced
"{[(a + b) * c + d}" -> Not balanced
"" -> Balanced

Application 2: Undo functionality

#include <vector>
#include <iostream>
#include <string>

class TextEditor
{
private:
    std::string content;
    std::vector<std::string> undoStack;
    
public:
    void type(const std::string& text)
    {
        // Save current state for undo
        undoStack.push_back(content);
        
        // Perform operation
        content += text;
        std::cout << "Typed: \"" << text << "\"" << std::endl;
        std::cout << "Content: \"" << content << "\"" << std::endl;
    }
    
    void deleteLast(std::size_t count = 1)
    {
        if (count > content.length()) count = content.length();
        
        // Save current state for undo
        undoStack.push_back(content);
        
        // Perform operation
        content.erase(content.length() - count);
        std::cout << "Deleted " << count << " characters" << std::endl;
        std::cout << "Content: \"" << content << "\"" << std::endl;
    }
    
    void undo()
    {
        if (undoStack.empty())
        {
            std::cout << "Nothing to undo" << std::endl;
            return;
        }
        
        // Restore previous state
        content = undoStack.back();
        undoStack.pop_back();
        
        std::cout << "Undo performed" << std::endl;
        std::cout << "Content: \"" << content << "\"" << std::endl;
    }
    
    void showStatus() const
    {
        std::cout << "Current content: \"" << content << "\"" << std::endl;
        std::cout << "Undo stack size: " << undoStack.size() << std::endl;
    }
};

int main()
{
    TextEditor editor;
    
    editor.type("Hello");
    editor.type(" World");
    editor.type("!");
    
    std::cout << "\nCurrent state:" << std::endl;
    editor.showStatus();
    
    std::cout << "\nPerforming undo operations:" << std::endl;
    editor.undo(); // Remove "!"
    editor.undo(); // Remove " World"
    
    editor.type(" C++");
    
    std::cout << "\nFinal state:" << std::endl;
    editor.showStatus();
    
    return 0;
}

Output:

Typed: "Hello"
Content: "Hello"
Typed: " World"
Content: "Hello World"
Typed: "!"
Content: "Hello World!"

Current state:
Current content: "Hello World!"
Undo stack size: 3

Performing undo operations:
Undo performed
Content: "Hello World"
Undo performed
Content: "Hello"
Typed: " C++"
Content: "Hello C++"

Final state:
Current content: "Hello C++"
Undo stack size: 3

Application 3: Function call stack simulation

#include <vector>
#include <iostream>
#include <string>

struct StackFrame
{
    std::string functionName;
    std::vector<std::string> localVariables;
    
    StackFrame(const std::string& name) : functionName(name) {}
};

class CallStack
{
private:
    std::vector<StackFrame> stack;
    
public:
    void enterFunction(const std::string& functionName)
    {
        stack.emplace_back(functionName);
        std::cout << "Entered " << functionName << "()" << std::endl;
        printCallStack();
    }
    
    void exitFunction()
    {
        if (!stack.empty())
        {
            std::string functionName = stack.back().functionName;
            stack.pop_back();
            std::cout << "Exited " << functionName << "()" << std::endl;
            printCallStack();
        }
    }
    
    void addLocalVariable(const std::string& varName)
    {
        if (!stack.empty())
        {
            stack.back().localVariables.push_back(varName);
            std::cout << "Added local variable: " << varName << std::endl;
        }
    }
    
    void printCallStack() const
    {
        std::cout << "Call stack (bottom to top):" << std::endl;
        if (stack.empty())
        {
            std::cout << "  [empty]" << std::endl;
        }
        else
        {
            for (std::size_t i = 0; i < stack.size(); ++i)
            {
                std::cout << "  " << i << ": " << stack[i].functionName << "()";
                if (!stack[i].localVariables.empty())
                {
                    std::cout << " [vars: ";
                    for (const auto& var : stack[i].localVariables)
                    {
                        std::cout << var << " ";
                    }
                    std::cout << "]";
                }
                std::cout << std::endl;
            }
        }
        std::cout << std::endl;
    }
};

int main()
{
    CallStack callStack;
    
    // Simulate function calls
    callStack.enterFunction("main");
    callStack.addLocalVariable("x");
    callStack.addLocalVariable("y");
    
    callStack.enterFunction("processData");
    callStack.addLocalVariable("temp");
    
    callStack.enterFunction("helper");
    callStack.addLocalVariable("result");
    
    // Simulate returns
    callStack.exitFunction(); // helper
    callStack.exitFunction(); // processData
    callStack.exitFunction(); // main
    
    return 0;
}

Output:

Entered main()
Call stack (bottom to top):
  0: main()

Added local variable: x
Added local variable: y
Entered processData()
Call stack (bottom to top):
  0: main() [vars: x y ]
  1: processData()

Added local variable: temp
Entered helper()
Call stack (bottom to top):
  0: main() [vars: x y ]
  1: processData() [vars: temp ]
  2: helper()

Added local variable: result
Exited helper()
Call stack (bottom to top):
  0: main() [vars: x y ]
  1: processData() [vars: temp ]

Exited processData()
Call stack (bottom to top):
  0: main() [vars: x y ]

Exited main()
Call stack (bottom to top):
  [empty]

Performance characteristics

Using std::vector as a stack provides excellent performance:

#include <vector>
#include <iostream>
#include <chrono>

void performanceTest()
{
    const int operations = 1000000;
    std::vector<int> stack;
    
    auto start = std::chrono::high_resolution_clock::now();
    
    // Push operations
    for (int i = 0; i < operations; ++i)
    {
        stack.push_back(i);
    }
    
    // Pop operations
    for (int i = 0; i < operations; ++i)
    {
        stack.pop_back();
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    std::cout << "Performed " << operations << " push and " << operations 
              << " pop operations in " << duration.count() << " ms" << std::endl;
}

int main()
{
    std::cout << "std::vector stack performance test:" << std::endl;
    performanceTest();
    
    return 0;
}

Time complexity of stack operations:

• push_back(): O(1) amortized
• pop_back(): O(1)
• back(): O(1)
• empty(): O(1)
• size(): O(1)

When to use std::vector vs std::stack

Use std::vector when:

• You need stack operations AND random access to elements
• You want to iterate through all elements
• You need to inspect the entire stack contents
• You want maximum flexibility

Use std::stack when:

• You only need pure stack operations (push, pop, top)
• You want to enforce the stack interface (no accidental random access)
• You want to make your intent clear in the code

#include <vector>
#include <stack>
#include <iostream>

int main()
{
    // std::vector approach - more flexible
    std::vector<int> vectorStack;
    vectorStack.push_back(1);
    vectorStack.push_back(2);
    vectorStack.push_back(3);
    
    // Can do stack operations
    std::cout << "Vector stack top: " << vectorStack.back() << std::endl;
    
    // But also has additional capabilities
    std::cout << "Vector stack contents: ";
    for (int value : vectorStack) // Can iterate through all elements
    {
        std::cout << value << " ";
    }
    std::cout << std::endl;
    
    std::cout << "Element at index 1: " << vectorStack[1] << std::endl; // Random access
    
    // std::stack approach - pure stack interface
    std::stack<int> pureStack;
    pureStack.push(1);
    pureStack.push(2);
    pureStack.push(3);
    
    std::cout << "Pure stack top: " << pureStack.top() << std::endl;
    // pureStack[1]; // Error! No random access
    // for (int value : pureStack) // Error! Cannot iterate
    
    return 0;
}

Output:

Vector stack top: 3
Vector stack contents: 1 2 3 
Element at index 1: 2
Pure stack top: 3

Best practices

1. Always check if stack is empty before popping

std::vector<int> stack;

// ❌ Dangerous
// stack.pop_back(); // Undefined behavior if empty

// ✅ Safe
if (!stack.empty())
{
    stack.pop_back();
}

2. Use const reference for accessing top element

std::vector<std::string> stack;
stack.push_back("hello");

// ✅ Good - no unnecessary copying
const std::string& top = stack.back();

3. Consider reserving capacity for better performance

std::vector<int> stack;
stack.reserve(1000); // If you expect ~1000 elements

for (int i = 0; i < 1000; ++i)
{
    stack.push_back(i); // No reallocations needed
}

Summary

std::vector provides excellent stack functionality through these operations:

• push_back() for push
• pop_back() for pop
• back() for accessing top element
• empty() for checking if empty

Advantages of using std::vector as a stack:

• Excellent performance (O(1) operations)
• Additional flexibility (random access, iteration)
• No overhead compared to std::stack
• Familiar interface

Key applications:

• Expression parsing and evaluation
• Undo/redo functionality
• Function call simulation
• Depth-first search algorithms
• Backtracking problems

Remember:

• Always check if empty before popping or accessing top
• Consider using a wrapper class for cleaner interfaces
• Reserve capacity when you know the expected size
• Choose between std::vector and std::stack based on your needs

In the next lesson, you'll learn about the special characteristics of std::vector.

Quiz

1. Which std::vector member functions correspond to stack operations push, pop, and top?
2. What happens if you call pop_back() on an empty vector?
3. Why might you choose std::vector over std::stack for implementing stack behavior?
4. What is the time complexity of stack operations using std::vector?
5. How would you safely access the top element of a vector being used as a stack?

Practice exercises

Try these exercises to practice using std::vector as a stack:

1. Calculator: Implement a simple calculator that uses a stack to evaluate postfix expressions (e.g., "3 4 + 2 *" should evaluate to 14).

2. Browser history: Create a browser history simulator that uses a stack to track visited pages, with functionality to go back and forward.

3. Maze solver: Implement a depth-first search maze solver that uses a stack to track the current path and backtrack when hitting dead ends.

4. Expression converter: Write a program that converts infix expressions (like "a + b * c") to postfix expressions using a stack-based algorithm.