可以用链表实现栈结构，通过定义节点和栈类实现LIFO操作，核心是将链表头部作为栈顶，支持push、pop、peek和empty等方法，示例代码展示了入栈出栈过程，使用时需注意内存管理。
在C++中，可以用链表来实现栈结构。栈是一种“后进先出”（LIFO）的数据结构，使用链表实现可以动态管理内存，避免数组实现时的容量限制。
定义链表节点和栈类
首先需要定义一个链表节点结构体，每个节点存储数据和指向下一个节点的指针。然后创建一个栈类，维护栈顶指针并提供入栈、出栈等操作。
示例代码：
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Stack {
private:
ListNode top;
public:
Stack() : top(nullptr) {}
void push(int x) {
ListNode newNode = new ListNode(x);
newNode->next = top;
top = newNode;
}
void pop() {
if (top == nullptr) {
std::cout
return;
}
ListNode* temp = top;
top = top->next;
delete temp;
}
int peek() const {
if (top == nullptr) {
throw std::runtime_error("栈为空");
}
return top->val;
}
bool empty() const {
return top == nullptr;
}
// 析构函数，释放所有节点
~Stack() {
while (top != nullptr) {
ListNode* temp = top;
top = top->next;
delete temp;
}
}
};
关键操作说明
链表实现栈的核心在于将链表头部作为栈顶，这样所有操作都能在常数时间内完成。
立即学习“C++免费学习笔记（深入）”；
- push(x)：创建新节点，将其 next 指向当前栈顶，再更新 top 指针。
- pop()：检查是否为空，非空则删除头节点并更新 top 指针。
- peek()：返回 top 节点的值，不修改栈结构。
- empty()：判断 top 是否为 nullptr。
使用示例
下面是一个简单的测试代码：
int main() {
Stack s;
s.push(1);
s.push(2);
s.push(3);
std::cout
s.pop();
std::cout
return 0;
}
基本上就这些。用链表实现栈灵活高效，适合不确定元素数量的场景。注意手动管理内存或结合智能指针提升安全性。
