链表
链表是一种常见的数据结构，由一系列节点组成。每个节点包含两部分：数据和指向下一个节点的指针。链表可以分为单向链表和双向链表。
单向链表
单向链表是最简单的链表形式，只能从头节点逐个遍历到尾节点。每个节点的指针只指向下一个节点。
struct Node {
int data;
Node* next;
};
class LinkedList {
public:
LinkedList() {
head = nullptr;
}
void insert(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->next = nullptr;
if (head == nullptr) {
head = newNode;
} else {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
}
void remove(int value) {
Node* current = head;
Node* previous = nullptr;
while (current != nullptr) {
if (current->data == value) {
if (previous != nullptr) {
previous->next = current->next;
} else {
head = current->next;
}
delete current;
return;
}
previous = current;
current = current->next;
}
}
void display() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
private:
Node* head;
};
双向链表
双向链表比单向链表更灵活，每个节点除了指向下一个节点的指针，还有指向前一个节点的指针。
struct Node {
int data;
Node* prev;
Node* next;
};
class DoublyLinkedList {
public:
DoublyLinkedList() {
head = nullptr;
}
void insert(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->prev = nullptr;
newNode->next = nullptr;
if (head == nullptr) {
head = newNode;
} else {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
}
}
void remove(int value) {
Node* current = head;
while (current != nullptr) {
if (current->data == value) {
if (current->prev != nullptr) {
current->prev->next = current->next;
} else {
head = current->next;
}
if (current->next != nullptr) {
current->next->prev = current->prev;
}
delete current;
return;
}
current = current->next;
}
}
void display() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
private:
Node* head;
};
栈
栈是一种遵循"后进先出"（LIFO）原则的数据结构。栈有两个基本操作：入栈（push）和出栈（pop）。
class Stack {
public:
Stack() {
top = -1;
}
void push(int value) {
if (top >= MAX_SIZE - 1) {
cout << "Stack Overflow" << endl;
return;
}
data[++top] = value;
}
int pop() {
if (top < 0) {
cout << "Stack is Empty" << endl;
return INT_MIN;
}
return data[top--];
}
int peek() {
if (top < 0) {
cout << "Stack is Empty" << endl;
return INT_MIN;
}
return data[top];
}
bool isEmpty() {
return top < 0;
}
private:
static const int MAX_SIZE = 100;
int data[MAX_SIZE];
int top;
};
队列
队列是一种遵循"先进先出"（FIFO）原则的数据结构。队列有两个基本操作：入队（enqueue）和出队（dequeue）。
class Queue {
public:
Queue() {
front = -1;
rear = -1;
}
void enqueue(int value) {
if (rear >= MAX_SIZE - 1) {
cout << "Queue Overflow" << endl;
return;
}
if (front == -1) {
front = 0;
}
data[++rear] = value;
}
int dequeue() {
if (front == -1 || front > rear) {
cout << "Queue is Empty" << endl;
return INT_MIN;
}
return data[front++];
}
int peek() {
if (front == -1 || front > rear) {
cout << "Queue is Empty" << endl;
return INT_MIN;
}
return data[front];
}
bool isEmpty() {
return front == -1 || front > rear;
}
private:
static const int MAX_SIZE = 100;
int data[MAX_SIZE];
int front, rear;
};
以上是 C++ 中链表、栈和队列的基本实现。这些数据结构在算法和数据处理中经常会被用到，对于理解和解决问题非常重要。在实际应用中，你可以根据需要对这些数据结构进行扩展和优化。
