顺序栈的出栈算法c语言
时间: 2023-12-25 16:04:47 浏览: 39
顺序栈的出栈算法C语言实现如下:
```
int pop(Stack *s) {
int data;
if (isEmpty(s)) {
printf("Stack is empty.\n");
return -1;
} else {
data = s->data[s->top];
s->top--;
return data;
}
}
```
其中,`Stack`结构体表示顺序栈,`top`表示栈顶元素的下标,`data`表示存储元素的数组。`pop`函数用于出栈,先判断顺序栈是否为空,如果为空则输出提示信息并返回-1,否则弹出栈顶元素,将`top`减1,并返回弹出的元素。
相关问题
顺序进栈和出栈用01算法C语言实现
以下是顺序进栈和出栈用01算法的C语言实现,其中使用了一个栈(stack)和一个指向出栈序列的指针(outptr)。
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 100
int stack[MAX_SIZE]; // 定义一个栈
int top = -1; // 栈顶指针初始化为-1
bool is_valid_order(int in_order[], int out_order[], int n) {
int outptr = 0;
for (int i = 0; i < n; i++) {
stack[++top] = in_order[i]; // 将当前元素入栈
while (top >= 0 && stack[top] == out_order[outptr]) { // 栈顶元素和出栈序列当前元素匹配
top--; // 弹出栈顶元素
outptr++; // 指向出栈序列的指针后移一位
}
}
return (top == -1); // 如果栈为空,说明两个序列匹配,返回true;否则返回false
}
int main() {
int in_order[] = {0, 0, 1, 1, 0, 0};
int out_order[] = {0, 0, 0, 1, 1, 1};
int n = sizeof(in_order) / sizeof(int);
if (is_valid_order(in_order, out_order, n)) {
printf("The order is valid.\n");
} else {
printf("The order is invalid.\n");
}
return 0;
}
```
这段代码首先定义了一个大小为MAX_SIZE的栈,然后定义了一个栈顶指针top,表示当前栈顶元素的下标。is_valid_order函数接受进栈序列in_order、出栈序列out_order和序列长度n作为参数,然后依次遍历进栈序列中的每个元素,将其入栈,并判断栈顶元素是否和出栈序列中的下一个元素相等,如果相等则弹出栈顶元素,重复这个过程直到遍历完整个进栈序列。最后,如果栈为空,则说明两个序列匹配,返回true;否则返回false。
后序遍历的非递归算法c语言栈实现
后序遍历的非递归算法可以使用栈来实现。具体步骤如下:
1. 初始化一个空栈,将根节点压入栈中。
2. 取出栈顶元素,如果该元素没有左右子节点,则输出该元素的值,如果有,则按照右节点、左节点的顺序依次将其子节点压入栈中。
3. 重复第2步,直到栈为空。
下面是C语言代码实现:
```c
void postOrderTraversal(TreeNode* root) {
if (root == NULL) return;
Stack stack;
TreeNode* prev = NULL;
push(&stack, root);
while (!isEmpty(&stack)) {
TreeNode* curr = peek(&stack);
if (prev == NULL || prev->left == curr || prev->right == curr) {
// 如果当前节点是根节点或者上一次访问的节点是它的子节点,则将其子节点(如果有)压入栈中
if (curr->left != NULL) push(&stack, curr->left);
else if (curr->right != NULL) push(&stack, curr->right);
} else if (curr->left == prev) {
// 如果当前节点的左子节点是上一次访问的节点,则将其右子节点(如果有)压入栈中
if (curr->right != NULL) push(&stack, curr->right);
} else {
// 否则,输出当前节点的值并弹出栈顶元素
printf("%d ", curr->val);
pop(&stack);
}
prev = curr;
}
}
```
其中,`TreeNode` 表示二叉树节点的结构体,`Stack` 表示栈的结构体,`push`、`pop`、`isEmpty` 和 `peek` 分别表示入栈、出栈、判断栈是否为空和获取栈顶元素的函数。在实现时需要注意,因为要输出每个节点的值,所以需要保存上一次访问的节点,用于判断当前节点是其父节点的左子节点还是右子节点。