Data Structures

Data structures provide different ways to store and access data. There are many data structures you will come across in OI:

• Array, dynamic array
• Stack, queue, deque, linked list
• Heap, binary search tree
• Segment tree, sparse table

Today we will discuss the stack and the C++ stack and vector.

Stack

Stack is a last-in-first-out (LIFO) data structure. It supports three operations:

• Push: Push an element onto the top of the stack
• Pop: Remove the topmost element
• Top: Get the topmost element

The stack can be impemented using an array with a pointer to the last element, which acts as the top of the stack.

The stack is available in the C++ Standard Template Library (STL).

// #include <stack>

stack<int> s;
s.push(6);        // Push
int t = s.top();  // Top
s.pop();          // Pop

Vector

A vector is a variable-sized array, similar to a Python list. It can work as a stack but it is more powerful.

// #include <vector>

vector<int> v1;                   // Construct an empty vector
vector<int> v2(n, 6);             // Construct a vector with n elements 6

int sz = v.size();                // Get size of vector

int x = v[k];                     // Access element at index k
int y = v.front(), z = v.back();  // Access first and last element

v.push_back(9);                   // Append an element
v.pop_back();                     // Remove the last element

v.insert(v.begin() + k, 9);       // Insert element at index k
v.erase(v.begin() + k);           // Remove element at index k

You can loop over a vector using the usual way:

for (int i = 0; i < v.size(); i++) {
    cout << v[i] << "\n";
}

Or use a range-based for-loop:

for (int x : v) {
    cout << x << "\n";
}