堆栈的顺序存储表示及实现
时间: 2024-05-03 16:22:43 浏览: 8
堆栈的顺序存储表示是利用数组来实现的,我们可以通过数组的下标来表示栈顶指针,栈顶指针始终指向栈顶元素的下一个位置。具体实现如下:
1. 定义一个数组和一个栈顶指针 top,初始化 top 为 -1。
2. 入栈操作时,将元素存入数组中 top+1 的位置,并将 top 的值加一。
3. 出栈操作时,返回数组中 top 位置的元素值,并将 top 的值减一。
4. 获取栈顶元素时,返回数组中 top 位置的元素值。
5. 判断栈是否为空时,判断 top 是否等于 -1。
以下是基于 C 语言的代码实现:
```c
#define MAXSIZE 100 // 定义栈的最大容量
typedef struct {
int data[MAXSIZE]; // 数组存储元素
int top; // 栈顶指针
} SqStack;
// 初始化栈
void InitStack(SqStack *S) {
S->top = -1;
}
// 判断栈是否为空
int IsEmpty(SqStack S) {
if (S.top == -1) {
return 1;
} else {
return 0;
}
}
// 判断栈是否已满
int IsFull(SqStack S) {
if (S.top == MAXSIZE - 1) {
return 1;
} else {
return 0;
}
}
// 入栈操作
int Push(SqStack *S, int x) {
if (IsFull(*S)) {
return 0; // 栈已满,入栈失败
} else {
S->top++; // 栈顶指针加一
S->data[S->top] = x; // 存储元素
return 1; // 入栈成功
}
}
// 出栈操作
int Pop(SqStack *S, int *x) {
if (IsEmpty(*S)) {
return 0; // 栈为空,出栈失败
} else {
*x = S->data[S->top]; // 返回栈顶元素
S->top--; // 栈顶指针减一
return 1; // 出栈成功
}
}
// 获取栈顶元素
int GetTop(SqStack S, int *x) {
if (IsEmpty(S)) {
return 0; // 栈为空,获取栈顶元素失败
} else {
*x = S.data[S.top]; // 返回栈顶元素
return 1; // 获取栈顶元素成功
}
}
```
以上就是堆栈的顺序存储表示及实现的基本思路和代码实现。