现决定用链表实现栈。请先设计一个栈,再针对C++对其进行调整。
时间: 2023-12-03 08:44:13 浏览: 37
以下是一个基于链表实现的栈的设计:
1. 首先,我们需要定义一个节点类,用于存储栈中的元素。节点类需要包含两个属性:存储的值和指向下一个节点的指针。
```C++
class Node {
public:
int val; // 存储的值
Node* next; // 指向下一个节点的指针
};
```
2. 然后,我们定义一个栈类,用于操作节点。
```C++
class Stack {
private:
Node* head; // 头节点
public:
Stack() {
head = nullptr; // 初始化头节点为空
}
~Stack() {
while (head != nullptr) { // 释放所有节点
Node* temp = head;
head = head->next;
delete temp;
}
}
void push(int val) {
Node* newNode = new Node(); // 创建新节点
newNode->val = val;
newNode->next = head; // 将新节点插入到头部
head = newNode;
}
void pop() {
if (head == nullptr) { // 栈为空
return;
}
Node* temp = head; // 临时指针指向头节点
head = head->next; // 头节点移动到下一个节点
delete temp; // 释放原头节点
}
int top() {
if (head == nullptr) { // 栈为空
return -1;
}
return head->val; // 返回头节点值
}
bool empty() {
return (head == nullptr); // 头节点为空,即栈为空
}
};
```
3. 最后,我们可以在主函数中创建一个栈对象并测试其功能。
```C++
int main() {
Stack myStack;
myStack.push(1);
myStack.push(2);
myStack.push(3);
cout << myStack.top() << endl; // 输出3
myStack.pop();
cout << myStack.top() << endl; // 输出2
myStack.pop();
cout << myStack.top() << endl; // 输出1
myStack.pop();
cout << myStack.empty() << endl; // 输出1
return 0;
}
```
对于C++语言,我们可以将节点类和栈类封装在一个头文件中,并在需要使用的源文件中包含该头文件。同时,我们可以使用模板类,使得栈类可以存储不同类型的元素。以下是针对C++的调整:
```C++
template <typename T>
class Node {
public:
T val;
Node* next;
};
template <typename T>
class Stack {
private:
Node<T>* head;
public:
Stack() {
head = nullptr;
}
~Stack() {
while (head != nullptr) {
Node<T>* temp = head;
head = head->next;
delete temp;
}
}
void push(T val) {
Node<T>* newNode = new Node<T>();
newNode->val = val;
newNode->next = head;
head = newNode;
}
void pop() {
if (head == nullptr) {
return;
}
Node<T>* temp = head;
head = head->next;
delete temp;
}
T top() {
if (head == nullptr) {
return T();
}
return head->val;
}
bool empty() {
return (head == nullptr);
}
};
```
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)