堆栈顺序存储及实现
时间: 2024-01-02 07:11:03 浏览: 47
堆栈是一种具有后进先出(Last In First Out,LIFO)特性的数据结构,顺序存储是其中一种实现方式。
堆栈的顺序存储实现需要使用数组来存储元素,同时需要一个指针来指示栈顶位置。新元素可以通过将其插入到数组的栈顶来入栈,而出栈则是将栈顶元素弹出,并将栈顶指针下移。
下面是一个堆栈的顺序存储实现的示例代码:
```
#define MAX_SIZE 100 // 定义堆栈最大容量
typedef struct {
int data[MAX_SIZE]; // 存储堆栈元素的数组
int top; // 指示当前栈顶位置的指针
} Stack;
// 初始化堆栈
void InitStack(Stack* s) {
s->top = -1; // 栈顶指针初始化为-1,表示堆栈为空
}
// 判断堆栈是否为空
int IsEmpty(Stack* s) {
return s->top == -1;
}
// 判断堆栈是否已满
int IsFull(Stack* s) {
return s->top == MAX_SIZE - 1;
}
// 将元素入栈
int Push(Stack* s, int x) {
if (IsFull(s)) return 0; // 堆栈已满,无法入栈
s->data[++(s->top)] = x; // 栈顶指针上移并将元素插入栈顶
return 1;
}
// 将栈顶元素出栈
int Pop(Stack* s) {
if (IsEmpty(s)) return 0; // 堆栈为空,无法出栈
--(s->top); // 栈顶指针下移
return 1;
}
// 获取栈顶元素的值
int Top(Stack* s) {
if (IsEmpty(s)) return -1; // 堆栈为空,返回-1表示错误
return s->data[s->top]; // 返回栈顶元素的值
}
```
通过以上代码,我们可以实现一个基于数组的堆栈,并且可以进行入栈、出栈、获取栈顶元素等操作。