单链表寻找栈的最大值
时间: 2023-09-19 17:11:37 浏览: 47
单链表无法直接实现栈的数据结构,但是我们可以通过在单链表中记录当前的最大值来实现一个“最大值栈”。
具体实现方法是,在定义单链表节点的结构体中增加一个max值,表示该节点所在链表中,以该节点为结尾的子链表的最大值。每次入栈时,将新节点的max值更新为当前节点与新节点值的最大值;每次出栈时,将前一个节点的max值更新为前一个节点与当前节点的max值的最大值。
这样,我们就可以通过访问单链表的尾节点的max值来获取当前最大值。
以下是一个简单的示例代码实现:
```C++
#include <iostream>
using namespace std;
struct Node {
int val; // 节点值
int max; // 当前子链表的最大值
Node* next; // 指向下一个节点的指针
Node(int x) : val(x), max(x), next(nullptr) {}
};
class MaxStack {
private:
Node* head; // 栈顶节点
public:
MaxStack() : head(nullptr) {}
void push(int x) {
Node* node = new Node(x);
if (head == nullptr) {
head = node;
} else {
node->max = max(head->max, x);
node->next = head;
head = node;
}
}
int pop() {
if (head == nullptr) {
return -1; // 栈为空
} else {
int res = head->val;
head = head->next;
return res;
}
}
int getMax() {
if (head == nullptr) {
return -1; // 栈为空
} else {
return head->max;
}
}
};
int main() {
MaxStack s;
s.push(5);
s.push(1);
s.push(3);
cout << s.getMax() << endl; // 5
s.pop();
cout << s.getMax() << endl; // 5
s.pop();
cout << s.getMax() << endl; // 5
s.pop();
cout << s.getMax() << endl; // -1,栈为空
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)