初始化栈顶为数组大小N,写出定义顺序栈、初始化栈、入栈、出栈、判断空栈、应用测试
时间: 2024-10-17 09:14:51 浏览: 32
数据结构实验报告-栈和队列.doc
5星 · 资源好评率100%
顺序栈是一种基于数组实现的数据结构,它遵循先进后出(LIFO,Last In First Out)的原则。以下是使用C++语言定义顺序栈及其操作:
```cpp
template <typename T>
class SequentialStack {
private:
T* data; // 数组存储数据
int top; // 栈顶指针,初始化为-1表示空栈
public:
// 构造函数:初始化栈顶
SequentialStack(int N) : data(new T[N]), top(-1) {}
// 初始化栈:如果给定的N大于0,则将top置为N-1
void initialize() {
if (N > 0) {
top = N - 1;
}
}
// 入栈操作:检查是否已满,然后将元素存于top+1位置,并更新top
bool push(const T& value) {
if (top == N - 1) {
return false; // 栈满,无法入栈
}
data[++top] = value;
return true;
}
// 出栈操作:返回并移除栈顶元素,同时更新top
T pop() {
if (isEmpty()) {
throw std::runtime_error("Stack is empty");
}
T result = data[top];
data[top--] = T(); // 防止泄露未初始化的空间
return result;
}
// 判断空栈:检查top是否等于初始值
bool isEmpty() const {
return top == -1;
}
// 应用测试示例
void test() {
push(1);
push(2);
assert(isEmpty() == false); // 测试非空栈
assert(pop() == 2); // 测试出栈
assert(isEmpty() == true); // 测试出栈后的状态
}
};
```
阅读全文