数据结构是计算机科学中的重要概念，它指的是在计算机存储、组织和管理数据的方式。在程序设计中，合理选择和使用数据结构可以极大地提高代码的效率和可维护性。
C++是一种强大的编程语言，提供了丰富的数据类型和操作，非常适合实现各种数据结构。在本篇博客中，我们将使用C++实现几种常见的数据结构，并介绍它们的特点和应用场景。
数组（Array）
数组是一种最基本的数据结构，它由一组连续的内存空间组成，用于存储相同类型的数据。C++中的数组可以通过下标访问和修改元素，数组的大小在创建时需要指定，并且在后续操作中无法改变。
#include <iostream>
int main() {
int arr[5] = {1, 2, 3, 4, 5};
// 遍历数组
for (int i = 0; i < 5; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
// 修改数组元素
arr[0] = 10;
// 输出修改后的数组
for (int i = 0; i < 5; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
数组适用于需要随机访问元素的情况，但由于其大小固定，不适用于需要频繁插入和删除元素的场景。
链表（Linked List）
链表是一种基于指针的数据结构，它由一系列不连续的节点组成，每个节点包含数据和指向下一个节点的指针。C++中可以使用指针或智能指针来实现链表。
#include <iostream>
#include <memory>
struct Node {
int data;
std::shared_ptr<Node> next;
};
int main() {
std::shared_ptr<Node> head = std::make_shared<Node>();
std::shared_ptr<Node> second = std::make_shared<Node>();
std::shared_ptr<Node> third = std::make_shared<Node>();
// 构建链表
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = nullptr;
// 遍历链表
std::shared_ptr<Node> current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
return 0;
}
链表适用于需要频繁插入和删除元素的场景，但由于访问元素需要遍历整个链表，效率较低。
栈（Stack）
栈是一种先进后出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。C++中可以使用数组或链表来实现栈。
#include <iostream>
class Stack {
private:
int maxSize;
int top;
int* arr;
public:
Stack(int size) {
maxSize = size;
top = -1;
arr = new int[maxSize];
}
~Stack() {
delete[] arr;
}
void push(int data) {
if (top < maxSize - 1) {
arr[++top] = data;
}
}
void pop() {
if (top >= 0) {
--top;
}
}
int peek() {
if (top >= 0) {
return arr[top];
}
return -1;
}
bool isEmpty() {
return top == -1;
}
};
int main() {
Stack stack(5);
stack.push(1);
stack.push(2);
stack.push(3);
std::cout << stack.peek() << std::endl; // 输出3
stack.pop();
std::cout << stack.peek() << std::endl; // 输出2
return 0;
}
栈适用于需要后进先出操作的场景，如表达式求值、括号匹配等。
队列（Queue）
队列是一种先进先出（FIFO）的数据结构，只允许在队尾插入元素，在队头删除元素。C++中可以使用数组或链表来实现队列。
#include <iostream>
class Queue {
private:
int maxSize;
int front;
int rear;
int* arr;
public:
Queue(int size) {
maxSize = size;
front = 0;
rear = -1;
arr = new int[maxSize];
}
~Queue() {
delete[] arr;
}
void enqueue(int data) {
if (rear < maxSize - 1) {
arr[++rear] = data;
}
}
void dequeue() {
if (front <= rear) {
++front;
}
}
int getFront() {
if (front <= rear) {
return arr[front];
}
return -1;
}
bool isEmpty() {
return front > rear;
}
};
int main() {
Queue queue(5);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
std::cout << queue.getFront() << std::endl; // 输出1
queue.dequeue();
std::cout << queue.getFront() << std::endl; // 输出2
return 0;
}
队列适用于需要按照先后顺序处理数据的场景，如任务调度、消息队列等。
总结
数据结构是程序设计中的重要概念，选择合适的数据结构可以极大地提高代码的效率和可维护性。本篇博客使用C++实现了几种常见的数据结构，分别是数组、链表、栈和队列。通过学习这些数据结构的实现方式，可以帮助我们更好地理解和应用它们。在实际开发中，根据具体需求选择合适的数据结构是非常重要的一环。
本文来自极简博客，作者：闪耀星辰，转载请注明原文链接：使用C++实现数据结构
