现决定用链表实现栈。请先设计一个栈,再针对C++对其进行调整。
时间: 2023-12-03 17:43:58 浏览: 68
栈是一种后进先出(LIFO)的数据结构,只能在栈顶进行插入和删除操作。基于链表实现栈,我们可以定义一个链表结点类来表示栈中的元素,然后使用链表的头指针作为栈顶指针,每次插入和删除操作都在头指针处进行。
下面是一个简单的栈的头文件设计:
```cpp
template <typename T>
class StackNode {
public:
T data;
StackNode<T>* next;
StackNode(T d) : data(d), next(nullptr) {}
};
template <typename T>
class Stack {
private:
StackNode<T>* top;
public:
Stack() : top(nullptr) {}
~Stack();
void push(T);
T pop();
bool isEmpty();
T peek();
};
template <typename T>
Stack<T>::~Stack() {
while (top) {
StackNode<T>* temp = top;
top = top->next;
delete temp;
}
}
template <typename T>
void Stack<T>::push(T d) {
StackNode<T>* node = new StackNode<T>(d);
node->next = top;
top = node;
}
template <typename T>
T Stack<T>::pop() {
if (!top)
throw std::out_of_range("Stack is empty!");
T data = top->data;
StackNode<T>* temp = top;
top = top->next;
delete temp;
return data;
}
template <typename T>
bool Stack<T>::isEmpty() {
return top == nullptr;
}
template <typename T>
T Stack<T>::peek() {
if (!top)
throw std::out_of_range("Stack is empty!");
return top->data;
}
```
这里我们定义了一个模板类`StackNode`表示栈中的节点,其中包含数据成员`data`和指向下一个节点的指针`next`。然后我们定义了另一个模板类`Stack`表示整个栈,其中包含一个指向栈顶节点的指针`top`。
在类中,我们定义了构造函数和析构函数,以及`push`、`pop`、`isEmpty`和`peek`等公共成员函数。其中`push`函数用于在栈顶插入一个元素,`pop`函数用于删除栈顶元素并返回其值,`isEmpty`函数用于判断栈是否为空,`peek`函数用于返回栈顶元素的值但不删除。需要注意的是,在删除元素时需要判断栈是否为空,否则会抛出异常。
如果需要使用该栈来存储自定义类型,可以在栈模板类定义之前先定义该类型的小于运算符(即`<`运算符),例如:
```cpp
struct Student {
int id;
std::string name;
bool operator<(const Student& rhs) const {
return id < rhs.id;
}
};
```
这样可以让该类型的对象在栈中进行比较和排序。
阅读全文