C++线性表深度解析之动态数组与单链表和栈及队列的实现

动态数组的实现

动态数组是一种可以动态扩展的数组结构，它的容量可以随着需要而动态增加。在C++中，使用vector类可以实现动态数组的功能。vector类相当于动态分配了一块内存空间，在使用时可以根据需要进行动态扩展。下面是一个示例代码：

#include <vector>
#include <iostream>

int main() {
    std::vector<int> arr; // 定义一个空的vector
    arr.push_back(1); // 向vector中添加元素
    arr.push_back(2);
    arr.push_back(3);
    for (int i = 0; i < arr.size(); i++) { // 遍历vector中的元素
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

示例输出：

1 2 3

单链表的实现

单链表是一种基本的数据结构，它由链表节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。在C++中，我们可以自己定义链表节点的结构体，然后通过指针将多个节点串起来，得到一个完整的链表。下面是一个示例代码：

#include <iostream>

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

int main() {
    ListNode* head = new ListNode(1); // 创建链表头节点
    ListNode* p = head; // 用指针p记录头节点
    p->next = new ListNode(2); // 添加节点2
    p = p->next; // 移动指针p到节点2
    p->next = new ListNode(3); // 添加节点3
    p = p->next; // 移动指针p到节点3
    while (head != NULL) { // 遍历链表中的元素
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
    return 0;
}

示例输出：

1 2 3

栈的实现

栈是一种后进先出的数据结构，可以使用数组或链表来实现。在C++中，我们可以使用STL中的stack类来实现栈的功能。stack类提供了push和pop方法，用于向栈中添加元素和弹出栈顶元素。下面是一个示例代码：

#include <iostream>
#include <stack>

int main() {
    std::stack<int> st; // 定义一个空的栈
    st.push(1); // 向栈中添加元素
    st.push(2);
    st.push(3);
    while (!st.empty()) { // 弹出栈顶元素并输出
        std::cout << st.top() << " ";
        st.pop();
    }
    std::cout << std::endl;
    return 0;
}

示例输出：

3 2 1

队列的实现

队列是一种先进先出的数据结构，可以使用数组或链表来实现。在C++中，我们可以使用STL中的queue类来实现队列的功能。queue类提供了push和pop方法，用于向队列中添加元素和弹出队首元素。下面是一个示例代码：

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q; // 定义一个空的队列
    q.push(1); // 向队列中添加元素
    q.push(2);
    q.push(3);
    while (!q.empty()) { // 弹出队首元素并输出
        std::cout << q.front() << " ";
        q.pop();
    }
    std::cout << std::endl;
    return 0;
}

示例输出：

1 2 3

以上就是动态数组和单链表、栈和队列的实现方法，希望能够对初学者有所帮助。