用c++写栈,使用链表
时间: 2024-03-22 13:18:13 浏览: 18
以下是使用链表实现栈的C++代码:
```c++
#include <iostream>
using namespace std;
// 定义栈的结构体
struct Node {
int data;
Node* next;
};
class Stack {
private:
Node* top; // 栈顶指针
public:
Stack() { top = NULL; } // 构造函数,初始化栈顶指针为 NULL
// 入栈操作
void push(int val) {
Node* newNode = new Node; // 创建新节点
newNode->data = val;
newNode->next = top; // 新节点指向当前栈顶
top = newNode; // 更新栈顶指针
}
// 出栈操作
int pop() {
int val;
if (isEmpty()) {
cout << "栈已空,无法出栈!" << endl;
return -1;
}
Node* temp = top; // 保存当前栈顶
val = temp->data; // 获取栈顶元素
top = top->next; // 更新栈顶指针
delete temp; // 释放原栈顶节点的内存
return val;
}
// 判断栈是否为空
bool isEmpty() {
return top == NULL;
}
};
int main() {
Stack stk;
// 入栈操作
stk.push(1);
stk.push(2);
stk.push(3);
// 出栈操作
cout << stk.pop() << endl;
cout << stk.pop() << endl;
cout << stk.pop() << endl;
cout << stk.pop() << endl; // 栈已空,无法出栈!
return 0;
}
```
在上面的代码中,我们使用了一个 `Node` 结构体来表示链表中的节点,其中包含了 `data` 和 `next` 两个成员变量,分别表示节点中存储的数据和下一个节点的指针。同时,我们还定义了一个 `Stack` 类,使用链表实现栈的操作。在 `push` 操作中,我们创建一个新节点,并将其插入到链表头部,同时更新栈顶指针;在 `pop` 操作中,我们首先判断栈是否为空,如果是,则返回一个错误提示;否则,我们获取当前栈顶元素,更新栈顶指针,然后释放原栈顶节点的内存。最后,我们在 `main` 函数中测试了我们实现的栈。