C++线性技巧，STL

**C++线性技巧与STL**

在编程领域，线性技巧（Linear Techniques）是指使用线性的算法来解决问题的方法。这些技巧包括了各种数据结构和算法，如链表、栈、队列、树等。在C++中，我们可以使用标准模板库（STL）提供的容器类来实现这些线性技巧。

**1. 链表**

链表是一种常见的线性数据结构，它由一系列的结点组成，每个结点包含一个值和一个指向下一个结点的指针。链表可以用于实现栈、队列等数据结构。

cpp// 定义一个结点类struct Node {
 int data;
 Node* next;
};

// 链表类class LinkedList {
public:
 Node* head;

 // 构造函数 LinkedList() : head(nullptr) {}

 // 添加元素到链表尾部 void push_back(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) {
 if (head == nullptr) return;

 if (head->data == value) {
 Node* temp = head;
 head = head->next;
 delete temp;
 return;
 }

 Node* current = head;
 while (current->next != nullptr) {
 if (current->next->data == value) {
 Node* temp = current->next;
 current->next = current->next->next;
 delete temp;
 return;
 }
 current = current->next;
 }
 }

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

cpp// 定义一个栈类class Stack {
private:
 int* elements;
 int top;
 int capacity;

public:
 // 构造函数 Stack(int size) : capacity(size), top(-1) {
 elements = new int[capacity];
 }

 // 添加元素到栈顶 void push(int value) {
 if (top == capacity -1) {
 std::cerr << "Stack is full!" << std::endl;
 return;
 }
 elements[++top] = value;
 }

 // 删除栈顶元素 int pop() {
 if (top == -1) {
 std::cerr << "Stack is empty!" << std::endl;
 return -1; // or throw an exception }
 return elements[top--];
 }

 // 查看栈顶元素 int peek() {
 if (top == -1) {
 std::cerr << "Stack is empty!" << std::endl;
 return -1; // or throw an exception }
 return elements[top];
 }

 // 判断栈是否为空 bool isEmpty() {
 return top == -1;
 }

 // 销毁栈 ~Stack() {
 delete[] elements;
 }
};

cpp// 定义一个队列类class Queue {
private:
 int* elements;
 int front;
 int rear;
 int capacity;

public:
 // 构造函数 Queue(int size) : capacity(size), front(0), rear(-1) {
 elements = new int[capacity];
 }

 // 添加元素到队列尾部 void enqueue(int value) {
 if (rear == capacity -1) {
 std::cerr << "Queue is full!" << std::endl;
 return;
 }
 elements[++rear] = value;
 }

 // 删除队列头部元素 int dequeue() {
 if (front > rear) {
 std::cerr << "Queue is empty!" << std::endl;
 return -1; // or throw an exception }
 return elements[front++];
 }

 // 查看队列头部元素 int peek() {
 if (front > rear) {
 std::cerr << "Queue is empty!" << std::endl;
 return -1; // or throw an exception }
 return elements[front];
 }

 // 判断队列是否为空 bool isEmpty() {
 return front > rear;
 }

 // 销毁队列 ~Queue() {
 delete[] elements;
 }
};

cpp// 使用vector实现链表#include <vector>

class LinkedList {
public:
 std::vector<int> elements;

 // 添加元素到链表尾部 void push_back(int value) {
 elements.push_back(value);
 }

 // 删除链表中的元素 void remove(int value) {
 elements.erase(std::remove(elements.begin(), elements.end(), value), elements.end());
 }

 // 打印链表中的元素 void print() {
 for (int element : elements) {
 std::cout << element << " ";
 }
 std::cout << std::endl;
 }
};

cpp// 使用stack实现栈#include <stack>

class Stack {
public:
 std::stack<int> stack;

 // 添加元素到栈顶 void push(int value) {
 stack.push(value);
 }

 // 删除栈顶元素 int pop() {
 return stack.top();
 }

 // 查看栈顶元素 int peek() {
 return stack.top();
 }
};

cpp// 使用queue实现队列#include <queue>

class Queue {
public:
 std::queue<int> queue;

 // 添加元素到队列尾部 void enqueue(int value) {
 queue.push(value);
 }

 // 删除队列头部元素 int dequeue() {
 return queue.front();
 }

 // 查看队列头部元素 int peek() {
 return queue.front();
 }
};