C++ 线性数据结构：数组、链表、栈和队列

在计算机科学中，数据结构是组织和存储数据的一种方式。线性数据结构是其中一种常见的数据结构类型，它以线性的方式存储和访问数据元素。C++ 是一种常用的编程语言，提供了丰富的库和语法来实现和操作线性数据结构。\n\n## 数组\n\n数组是一种简单且常见的线性数据结构，它由一组相同类型的元素组成，这些元素通过索引访问。在 C++ 中，数组的大小在创建时需要指定，并且不能动态调整。以下是一个示例，展示如何声明和访问一个整数数组：\n\ncpp\nint numbers[5]; // 声明一个包含 5 个整数的数组\n\nnumbers[0] = 1; // 访问第一个元素并赋值为 1\nnumbers[1] = 2; // 访问第二个元素并赋值为 2\nnumbers[2] = 3; // 访问第三个元素并赋值为 3\nnumbers[3] = 4; // 访问第四个元素并赋值为 4\nnumbers[4] = 5; // 访问第五个元素并赋值为 5\n\ncout << numbers[2]; // 输出第三个元素的值，结果为 3\n\n\n## 链表\n\n链表是另一种常见的线性数据结构，它由一组称为节点的元素组成，每个节点包含一个数据项和一个指向下一个节点的指针。链表可以分为单向链表和双向链表两种类型。在 C++ 中，链表通常使用指针来连接节点。以下是一个示例，展示如何创建和操作一个单向链表：\n\ncpp\nstruct Node {\n int data;\n Node* next;\n};\n\nNode* head = nullptr; // 头指针初始化为空\n\n// 在链表头部插入一个节点\nvoid insert(int value) {\n Node* newNode = new Node();\n newNode->data = value;\n newNode->next = head;\n head = newNode;\n}\n\n// 遍历链表并输出每个节点的值\nvoid display() {\n Node* current = head;\n while (current != nullptr) {\n cout << current->data << " ";\n current = current->next;\n }\n}\n\n// 测试链表操作\nint main() {\n insert(3);\n insert(2);\n insert(1);\n display(); // 输出结果为 1 2 3\n return 0;\n}\n\n\n## 栈\n\n栈是一种特殊的线性数据结构，它遵循后进先出 (LIFO) 的原则。只允许在栈的顶部进行插入和删除操作，这被称为推入 (push) 和弹出 (pop)。C++ 中可以使用 STL 库中的 std::stack 类来实现栈。以下是一个示例，展示如何使用栈来检查字符串中的括号匹配：\n\ncpp\n#include <stack>\n#include <iostream>\nusing namespace std;\n\nbool checkParentheses(string str) {\n stack<char> parentheses;\n for (char c : str) {\n if (c == '(' || c == '[' || c == '{') {\n parentheses.push(c);\n } else if (c == ')' || c == ']' || c == '}') {\n if (parentheses.empty()) {\n return false;\n } else if ((c == ')' && parentheses.top() == '(') ||\n (c == ']' && parentheses.top() == '[') ||\n (c == '}' && parentheses.top() == '{')) {\n parentheses.pop();\n } else {\n return false;\n }\n }\n }\n return parentheses.empty();\n}\n\nint main() {\n string str = "({[]})";\n if (checkParentheses(str)) {\n cout << "括号匹配" << endl;\n } else {\n cout << "括号不匹配" << endl;\n }\n return 0;\n}\n\n\n## 队列\n\n队列是另一种常见的线性数据结构，它遵循先进先出 (FIFO) 的原则。与栈不同，队列允许在队列的尾部插入元素，并在队列的头部删除元素。C++ 中可以使用 STL 库中的 std::queue 类来实现队列。以下是一个示例，展示如何使用队列来实现广度优先搜索算法：\n\ncpp\n#include <queue>\n#include <iostream>\nusing namespace std;\n\nvoid bfs(vector<vector<int>>& graph, int start) {\n int n = graph.size();\n vector<bool> visited(n, false);\n queue<int> q;\n q.push(start);\n visited[start] = true;\n\n while (!q.empty()) {\n int node = q.front();\n q.pop();\n cout << node << " ";\n\n for (int neighbor : graph[node]) {\n if (!visited[neighbor]) {\n q.push(neighbor);\n visited[neighbor] = true;\n }\n }\n }\n}\n\nint main() {\n vector<vector<int>> graph = {{1, 2}, {0, 2, 3}, {0, 1, 3, 4}, {1, 2, 4}, {2, 3}};\n bfs(graph, 0); // 输出结果为 0 1 2 3 4\n return 0;\n}\n\n\n以上是 C++ 中常见的线性数据结构的简介和示例。在实际编程中，根据具体问题的需求选择适当的数据结构非常重要，这将有助于提高代码的效率和可读性。