定义栈的基本操作(初始化栈、判空、出栈、入栈等)
时间: 2024-10-09 08:16:05 浏览: 92
栈是一种特殊的线性数据结构,遵循“先进后出”(Last In First Out, LIFO)原则。下面是栈的一些基本操作的定义:
1. **初始化栈**:
对于无界数组实现的栈,可以简单地创建一个空数组作为栈的容器;对于动态内存,你可以使用`malloc`或`new`分配一块内存,并将顶部指针指向`NULL`。
```c++
// 动态内存实现
struct StackElement *top = NULL;
// 数组实现(假设已有一个足够大的数组)
Stack stack[STACK_SIZE];
top = stack + STACK_SIZE - 1; // 把数组大小减一当作栈顶
```
2. **判断栈是否为空**:
只需检查栈顶元素是否为`NULL`或者数组下标是否超出界限即可。
```c++
bool isEmpty(StackElement* top) {
return top == NULL || (arrayBased && top == stack);
}
```
3. **入栈(压栈)**:
新元素添加到栈顶,如果是数组,更新`top`指针;如果是动态内存,将新元素放在`top`位置并递增`top`。
```c++
void push(StackElement value) {
if (dynamicMemory) {
*top = value;
top++;
} else {
stack[--top] = value;
}
}
```
4. **出栈(弹栈)**:
删除并返回栈顶元素,然后调整`top`。
```c++
StackElement pop() {
if (isEmpty()) {
throw EmptyStackException(); // 如果空栈则抛异常
}
StackElement result = *top;
if (dynamicMemory) {
top--;
} else {
top++;
}
return result;
}
```
5. **获取栈顶元素**(查看但不删除):
可以单独提供一个方法来获取当前栈顶元素而不改变栈的状态。
```c++
StackElement peek() const {
if (isEmpty()) {
throw EmptyStackException();
}
return *top;
}
```
以上就是栈的基本操作,注意在实际使用中,你需要考虑错误处理和资源释放等问题。
阅读全文