栈和队列经典例题

1.将两个栈S1和S2共享一组数组a[0,1…MAX],为了最大限度地利用数组空间,两个栈应该如何共享?给出入栈,出栈,判断栈满和判断栈空的算法。

 #include <stdio.h>
#include <stdbool.h>

#define MAX 10 // 假设最大值为10

int a[MAX + 1]; // 数组存储栈数据
int top1 = 0;   // 栈S1的栈顶指针
int top2 = MAX; // 栈S2的栈顶指针

// S1入栈
bool push1(int x) {
    if (top1 < top2) { // 检查栈是否已满
        a[top1++] = x;
        return true;
    }
    return false; // 栈已满
}

// S2入栈
bool push2(int x) {
    if (top1 < top2) { // 检查栈是否已满
        a[--top2] = x;
        return true;
    }
    return false; // 栈已满
}

// S1出栈
int pop1() {
    if (top1 > 0) { // 检查栈是否为空
        return a[--top1];
    }
    printf("Stack S1 is empty.\n");
    return -1; // 栈为空
}

// S2出栈
int pop2() {
    if (top2 <= MAX) { // 检查栈是否为空
        return a[top2++];
    }
    printf("Stack S2 is empty.\n");
    return -1; // 栈为空
}

// 判断S1是否为空
bool isEmpty1() {
    return top1 == 0;
}

// 判断S2是否为空
bool isEmpty2() {
    return top2 == MAX;
}

// 判断栈是否已满
bool isFull() {
    return top1 == top2;
}

2.已知递归函数F(m),其中div表示整除。 

 写出F(m)的递归算法。 写出F(m)的非递归算法。

#include <stdio.h>

// 递归函数 F(m)
int F_recursive(int m) {
    if (m == 0) {
        return 1;
    } else {
        return m * F_recursive(m / 2);
    }
}

int main() {
    int m;
    printf("Enter a non-negative integer m: ");
    scanf("%d", &m);
    printf("F(%d) = %d\n", m, F_recursive(m));
    return 0;
}

#include <stdio.h>

// 非递归函数 F(m)
int F_non_recursive(int m) {
    int result = 1;
    while (m > 0) {
        result *= m;
        m /= 2;
    }
    return result;
}

int main() {
    int m;
    printf("Enter a non-negative integer m: ");
    scanf("%d", &m);
    printf("F(%d) = %d\n", m, F_non_recursive(m));
    return 0;
}