数据结构与算法面试高频（基础算法）

基础算法

1 实现一个vector⭐⭐⭐⭐

#include <iostream>
#include <stdexcept>

template <typename T>
class MyVector {
private:
    T* data;  // 指向动态分配数组的指针
    size_t size_;  // 当前元素的数量
    size_t capacity_;  // 当前数组的容量

    // 重新分配内存，扩大容量
    void reserve(size_t newCapacity) {
        if (newCapacity <= capacity_) return;

        T* newData = new T[newCapacity];
        for (size_t i = 0; i < size_; ++i) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
        capacity_ = newCapacity;
    }

public:
    // 默认构造函数
    MyVector() : data(nullptr), size_(0), capacity_(0) {}

    // 析构函数
    ~MyVector() {
        delete[] data;
    }

    // 获取当前元素的数量
    size_t size() const {
        return size_;
    }

    // 获取当前数组的容量
    size_t capacity() const {
        return capacity_;
    }

    // 判断向量是否为空
    bool empty() const {
        return size_ == 0;
    }

    // 在向量末尾添加一个元素
    void push_back(const T& value) {
        if (size_ == capacity_) {
            if (capacity_ == 0) {
                reserve(1);
            } else {
                reserve(2 * capacity_);
            }
        }
        data[size_++] = value;
    }

    // 移除向量末尾的元素
    void pop_back() {
        if (size_ > 0) {
            --size_;
        }
    }

    // 访问指定位置的元素
    T& operator[](size_t index) {
        if (index >= size_) {
            throw std::out_of_range("Index out of range");
        }
        return data[index];
    }

    const T& operator[](size_t index) const {
        if (index >= size_) {
            throw std::out_of_range("Index out of range");
        }
        return data[index];
    }
};

// 测试代码
int main() {
    MyVector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);

    std::cout << "Size: " << vec.size() << std::endl;
    std::cout << "Capacity: " << vec.capacity() << std::endl;

    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;

    vec.pop_back();
    std::cout << "Size after pop_back: " << vec.size() << std::endl;

    return 0;
}

2 来手写一个链表⭐⭐⭐⭐

#include <iostream>

// 定义链表节点类
template <typename T>
class Node {
public:
    T data;         // 节点存储的数据
    Node<T>* next;  // 指向下一个节点的指针

    // 构造函数
    Node(T value) : data(value), next(nullptr) {}
};

// 定义链表类
template <typename T>
class LinkedList {
private:
    Node<T>* head;  // 链表头指针

public:
    // 构造函数，初始化头指针为 nullptr
    LinkedList() : head(nullptr) {}

    // 析构函数，释放链表中所有节点的内存
    ~LinkedList() {
        while (head != nullptr) {
            Node<T>* temp = head;
            head = head->next;
            delete temp;
        }
    }

    // 在链表头部插入一个新节点
    void insertAtHead(T value) {
        Node<T>* newNode = new Node<T>(value);
        newNode->next = head;
        head = newNode;
    }

    // 在链表尾部插入一个新节点
    void insertAtTail(T value) {
        Node<T>* newNode = new Node<T>(value);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node<T>* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    // 删除链表头部节点
    void deleteAtHead() {
        if (head == nullptr) {
            return;
        }
        Node<T>* temp = head;
        head = head->next;
        delete temp;
    }

    // 删除链表尾部节点
    void deleteAtTail() {
        if (head == nullptr) {
            return;
        }
        if (head->next == nullptr) {
            delete head;
            head = nullptr;
            return;
        }
        Node<T>* temp = head;
        while (temp->next->next != nullptr) {
            temp = temp->next;
        }
        delete temp->next;
        temp->next = nullptr;
    }

    // 打印链表中的所有元素
    void printList() {
        Node<T>* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }
};

int main() {
    LinkedList<int> list;

    // 在链表尾部插入元素
    list.insertAtTail(1);
    list.insertAtTail(2);
    list.insertAtTail(3);

    // 打印链表
    std::cout << "After inserting at tail: ";
    list.printList();

    // 在链表头部插入元素
    list.insertAtHead(0);

    // 打印链表
    std::cout << "After inserting at head: ";
    list.printList();

    // 删除链表头部元素
    list.deleteAtHead();

    // 打印链表
    std::cout << "After deleting at head: ";
    list.printList();

    // 删除链表尾部元素
    list.deleteAtTail();

    // 打印链表
    std::cout << "After deleting at tail: ";
    list.printList();

    return 0;
}

Node 类：定义了链表的节点，包含一个数据成员 data 和一个指向下一个节点的指针 next。
head：链表的头指针，指向链表的第一个节点。
构造函数：初始化头指针为 nullptr。
析构函数：释放链表中所有节点的内存，防止内存泄漏。
insertAtHead：在链表头部插入一个新节点。
insertAtTail：在链表尾部插入一个新节点。
deleteAtHead：删除链表头部节点。
deleteAtTail：删除链表尾部节点。
printList：打印链表中的所有元素。
main 函数：创建一个链表对象，进行插入和删除操作，并打印链表的内容。

通过上述代码，你可以了解如何使用 C++ 实现一个简单的链表，并对链表进行基本的操作。

3 用数组或链表来实现一个栈⭐⭐⭐⭐⭐

实现的原理都是类似的，用游标变量来控制元素的位置。

栈只需要设置一个游标变量来控制栈顶元素的位置

大家一定要掌握，面试很容易手撕代码。

使用数组实现栈

#include <iostream>
#include <stdexcept>

template <typename T, size_t MAX_SIZE>
class ArrayStack {
private:
    T data[MAX_SIZE];
    int topIndex;

public:
    ArrayStack() : topIndex(-1) {}

    // 判断栈是否为空
    bool empty() const {
        return topIndex == -1;
    }

    // 判断栈是否已满
    bool full() const {
        return topIndex == static_cast<int>(MAX_SIZE - 1);
    }

    // 入栈操作
    void push(const T& value) {
        if (full()) {
            throw std::overflow_error("Stack overflow");
        }
        data[++topIndex] = value;
    }

    // 出栈操作
    void pop() {
        if (empty()) {
            throw std::underflow_error("Stack underflow");
        }
        --topIndex;
    }

    // 获取栈顶元素
    T top() const {
        if (empty()) {
            throw std::underflow_error("Stack is empty");
        }
        return data[topIndex];
    }
};


int main() {
    ArrayStack<int, 5> stack;
    try {
        stack.push(1);
        stack.push(2);
        stack.push(3);
        std::cout << "Top element: " << stack.top() << std::endl;
        stack.pop();
        std::cout << "Top element after pop: " << stack.top() << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Exception: " << e.what() << std::endl;
    }
    return 0;
}

ArrayStack 类使用一个固定大小的数组 data 来存储栈中的元素，topIndex 表示栈顶元素的索引。
empty 方法通过检查 topIndex 是否为 -1 来判断栈是否为空。
full 方法通过检查 topIndex 是否达到数组的最大索引来判断栈是否已满。
push 方法在栈未满时将元素添加到栈顶，并更新 topIndex。
pop 方法在栈非空时将 topIndex 减 1，实现出栈操作。
top 方法在栈非空时返回栈顶元素。

使用链表实现栈

#include <iostream>
#include <stdexcept>

template <typename T>
class Node {
public:
    T data;
    Node<T>* next;

    Node(const T& value) : data(value), next(nullptr) {}
};

template <typename T>
class LinkedStack {
private:
    Node<T>* topNode;

public:
    LinkedStack() : topNode(nullptr) {}

    ~LinkedStack() {
        while (!empty()) {
            pop();
        }
    }

    // 判断栈是否为空
    bool empty() const {
        return topNode == nullptr;
    }

    // 入栈操作
    void push(const T& value) {
        Node<T>* newNode = new Node<T>(value);
        newNode->next = topNode;
        topNode = newNode;
    }

    // 出栈操作
    void pop() {
        if (empty()) {
            throw std::underflow_error("Stack underflow");
        }
        Node<T>* temp = topNode;
        topNode = topNode->next;
        delete temp;
    }

    // 获取栈顶元素
    T top() const {
        if (empty()) {
            throw std::underflow_error("Stack is empty");
        }
        return topNode->data;
    }
};


int main() {
    LinkedStack<int> stack;
    try {
        stack.push(1);
        stack.push(2);
        stack.push(3);
        std::cout << "Top element: " << stack.top() << std::endl;
        stack.pop();
        std::cout << "Top element after pop: " << stack.top() << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Exception: " << e.what() << std::endl;
    }
    return 0;
}

Node 类表示链表中的节点，包含一个数据成员 data 和一个指向下一个节点的指针 next。
LinkedStack 类使用 topNode 指向栈顶节点。
empty 方法通过检查 topNode 是否为 nullptr 来判断栈是否为空。
push 方法创建一个新节点，将其插入到链表头部，成为新的栈顶节点。
pop 方法在栈非空时删除栈顶节点，并释放其内存。
top 方法在栈非空时返回栈顶节点的数据。
析构函数在对象销毁时会依次调用 pop 方法，释放所有节点的内存。

4 用数组或链表来实现一个队列⭐⭐⭐⭐

使用数组实现队列

#include <iostream>
#include <stdexcept>

template <typename T, size_t MAX_SIZE>
class ArrayQueue {
private:
    T data[MAX_SIZE];
    int frontIndex;
    int rearIndex;
    int count;

public:
    ArrayQueue() : frontIndex(0), rearIndex(0), count(0) {}

    // 判断队列是否为空
    bool empty() const {
        return count == 0;
    }

    // 判断队列是否已满
    bool full() const {
        return count == MAX_SIZE;
    }

    // 入队操作
    void enqueue(const T& value) {
        if (full()) {
            throw std::overflow_error("Queue is full");
        }
        data[rearIndex] = value;
        rearIndex = (rearIndex + 1) % MAX_SIZE;
        ++count;
    }

    // 出队操作
    void dequeue() {
        if (empty()) {
            throw std::underflow_error("Queue is empty");
        }
        frontIndex = (frontIndex + 1) % MAX_SIZE;
        --count;
    }

    // 获取队首元素
    T front() const {
        if (empty()) {
            throw std::underflow_error("Queue is empty");
        }
        return data[frontIndex];
    }
};


int main() {
    ArrayQueue<int, 5> queue;
    try {
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        std::cout << "Front element: " << queue.front() << std::endl;
        queue.dequeue();
        std::cout << "Front element after dequeue: " << queue.front() << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Exception: " << e.what() << std::endl;
    }
    return 0;
}

ArrayQueue 类使用一个固定大小的数组 data 来存储队列中的元素。
frontIndex 指向队首元素的位置，rearIndex 指向队尾元素的下一个位置，count 记录队列中元素的数量。
empty 方法通过检查 count 是否为 0 来判断队列是否为空。
full 方法通过检查 count 是否达到数组的最大容量来判断队列是否已满。
enqueue 方法在队列未满时将元素添加到队尾，并更新 rearIndex 和 count。使用取模运算 % 实现循环数组，以充分利用数组空间。
dequeue 方法在队列非空时更新 frontIndex 和 count，实现出队操作。
front 方法在队列非空时返回队首元素。

使用链表实现队列

#include <iostream>
#include <stdexcept>

template <typename T>
class Node {
public:
    T data;
    Node<T>* next;

    Node(const T& value) : data(value), next(nullptr) {}
};

template <typename T>
class LinkedQueue {
private:
    Node<T>* frontNode;
    Node<T>* rearNode;

public:
    LinkedQueue() : frontNode(nullptr), rearNode(nullptr) {}

    ~LinkedQueue() {
        while (!empty()) {
            dequeue();
        }
    }

    // 判断队列是否为空
    bool empty() const {
        return frontNode == nullptr;
    }

    // 入队操作
    void enqueue(const T& value) {
        Node<T>* newNode = new Node<T>(value);
        if (empty()) {
            frontNode = rearNode = newNode;
        } else {
            rearNode->next = newNode;
            rearNode = newNode;
        }
    }

    // 出队操作
    void dequeue() {
        if (empty()) {
            throw std::underflow_error("Queue is empty");
        }
        Node<T>* temp = frontNode;
        frontNode = frontNode->next;
        if (frontNode == nullptr) {
            rearNode = nullptr;
        }
        delete temp;
    }

    // 获取队首元素
    T front() const {
        if (empty()) {
            throw std::underflow_error("Queue is empty");
        }
        return frontNode->data;
    }
};


int main() {
    LinkedQueue<int> queue;
    try {
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        std::cout << "Front element: " << queue.front() << std::endl;
        queue.dequeue();
        std::cout << "Front element after dequeue: " << queue.front() << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Exception: " << e.what() << std::endl;
    }
    return 0;
}

Node 类表示链表中的节点，包含一个数据成员 data 和一个指向下一个节点的指针 next。
LinkedQueue 类使用 frontNode 指向队首节点，rearNode 指向队尾节点。
empty 方法通过检查 frontNode 是否为 nullptr 来判断队列是否为空。
enque

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

嵌入式/C++面试八股文文章被收录于专栏

该专栏面向嵌入式开发工程师、C++开发工程师，包括C语言、C++，操作系统，ARM架构、RTOS、Linux基础、Linux驱动、Linux系统移植、计算机网络、数据结构与算法、数电基础、模电基础、5篇面试题目、HR面试常见问题汇总和嵌入式面试简历模板等文章。超全的嵌入式软件工程师面试题目和高频知识点总结！另外，专栏分为两个部分，大家可以各取所好，为了有更好的阅读体验，后面会持续更新!!!