【C++刷题集】-- day4

**【C++刷题集】-- day4**

###1. 题目描述本题目集合包含了 C++ 中一些常见的算法和数据结构问题，包括链表、栈、队列、树等。这些问题将帮助你巩固 C++ 的基本知识，并提高你的编程能力。

###2. 链表相关问题####2.1. 题目描述给定一个单向链表的头节点，求出链表中第二大的数字。

####2.2. 解决方案

cpp// Node类定义struct Node {
 int data;
 Node* next;
};

// 链表相关函数Node* createList(int arr[], int n) {
 Node* head = nullptr;
 Node* tail = nullptr;

 for (int i =0; i < n; ++i) {
 Node* newNode = new Node();
 newNode->data = arr[i];
 newNode->next = nullptr;

 if (!head) {
 head = newNode;
 tail = newNode;
 } else {
 tail->next = newNode;
 tail = newNode;
 }
 }

 return head;
}

int findSecondMax(Node* head) {
 int max1 = INT_MIN, max2 = INT_MIN;

 while (head != nullptr) {
 if (head->data > max1) {
 max2 = max1;
 max1 = head->data;
 } else if (head->data > max2 && head->data != max1) {
 max2 = head->data;
 }

 head = head->next;
 }

 return max2 == INT_MIN ? -1 : max2;
}

####2.3.代码注释* `createList`函数用于创建一个链表，传入一个数组和该数组的大小。
* `findSecondMax`函数用于找到链表中第二大的数字。

###3. 栈相关问题####3.1. 题目描述给定一个栈和一个操作序列，求出栈顶元素。

####3.2. 解决方案

cpp// Stack类定义class Stack {
private:
 int* arr;
 int top;

public:
 Stack(int capacity) {
 arr = new int[capacity];
 top = -1;
 }

 ~Stack() { delete[] arr; }

 void push(int data) {
 if (top == arr.length -1) {
 // Handle stack overflow }
 arr[++top] = data;
 }

 int pop() {
 if (isEmpty()) {
 return INT_MIN; // Handle empty stack }
 return arr[top--];
 }

 bool isEmpty() { return top == -1; }

 int peek() {
 if (isEmpty()) {
 return INT_MIN; // Handle empty stack }
 return arr[top];
 }
};

####3.3.代码注释* `Stack`类定义了一个栈的基本操作，包括push、pop和peek。

###4. 队列相关问题####4.1. 题目描述给定一个队列和一个操作序列，求出队首元素。

####4.2. 解决方案

cpp// Queue类定义class Queue {
private:
 int* arr;
 int front;
 int rear;

public:
 Queue(int capacity) {
 arr = new int[capacity];
 front = rear = -1;
 }

 ~Queue() { delete[] arr; }

 void enqueue(int data) {
 if (rear == arr.length -1) {
 // Handle queue overflow }
 arr[++rear] = data;
 }

 int dequeue() {
 if (isEmpty()) {
 return INT_MIN; // Handle empty queue }
 return arr[front++];
 }

 bool isEmpty() { return front == rear; }

 int peekFront() {
 if (isEmpty()) {
 return INT_MIN; // Handle empty queue }
 return arr[front];
 }
};

####4.3.代码注释* `Queue`类定义了一个队列的基本操作，包括enqueue、dequeue和peekFront。

###5. 树相关问题####5.1. 题目描述给定一棵二叉树，求出该树的高度。

####5.2. 解决方案

cpp// Node类定义struct Node {
 int data;
 Node* left;
 Node* right;
};

// Tree相关函数int findHeight(Node* root) {
 if (root == nullptr) {
 return -1; // Handle empty tree }
 return1 + max(findHeight(root->left), findHeight(root->right));
}

####5.3.代码注释* `findHeight`函数用于找到一棵二叉树的高度。

###6. 总结本题目集合包含了 C++ 中一些常见的算法和数据结构问题，包括链表、栈、队列、树等。这些问题将帮助你巩固 C++ 的基本知识，并提高你的编程能力。