线性表之数组实现栈结构

用数组实现栈结构

实现

栈结构的数组实现是用一个一维数组存放数据，数据每次从队尾加入，删除时也从队尾删除，要实现这种增删操作需要使用一个记录下标的指针（top）来指向栈顶。当添加元素时添加到 arr[top+1]位置，当要做删除操作时 使top–；指向倒数第二个元素，使其称为新栈顶。旧栈顶则被忽略，当其所占空间要使用时直接覆盖即可。

栈与递归

栈是一种很常用的结构，比如函数调用就使用栈结构，当程序执行到函数调语句时先把当前函数保存在栈中，即压栈。然后进入函数调用执行。当再次碰到函数调用语句时则重复上述步骤。当一个函数调用A执行完后，再把调用A的函数从栈中取出，继续执行这条函数。如此重复，直到main函数执行结束。下面是递归演示

void recursionDemo(array *arr,int count){

    //判断栈是否满，如果已满则不在继续执行。这是递归结束的条件
    if( !(arr->top < arr->length-1) ){
        return ;
    }

    push(arr,count);
    printf(" %d 元素进栈\n",count);

    //调用自身
    recursionDemo(arr,++count);

    //打印后 出栈
    printf(" %d 元素出栈\n",*getTop(arr));
    pop(arr);

  打印结果
 1 元素进栈      
 2 元素进栈
 3 元素进栈
 4 元素进栈
 5 元素进栈
 5 元素出栈
 4 元素出栈
 3 元素出栈
 2 元素出栈
 1 元素出栈
请按任意键继续. . .

}

递归常用于分治法解决问题，每一次递归都使问题规模更小，直到问题规模最小（不可拆分）时结束递归。

完整demo代码如下：

#define SIZE 6 

//定义栈结构
typedef struct array{
    int data[SIZE];
    int length;
    int top;
}array;

//初始化
array *newArr(){
    array *arr = (array *)malloc(sizeof(array));

    //0下标空闲,不使用
    arr->top = 0;
    arr->length = SIZE;
}

//判栈空
int isEmpty(array *arr){
    return arr->top ==  0;
}

//出栈
void pop(array *arr){
    if(isEmpty(arr)){
        printf("the stack is null");
        return;
    }
    arr->top--;
}

//返回栈顶元素的指针
int *getTop(array *arr){

    return isEmpty(arr)? NULL:&arr->data[arr->top];
}

//入栈
void push(array *arr,int value){
    if(arr->top< arr->length-1){
        arr->data[++(arr->top)] = value;
    }
}

//test
void ASTest(){
    array *arr = newArr();
    push(arr,1);
    push(arr,2);
    push(arr,3);
    push(arr,4);
    push(arr,5);

    while(!isEmpty(arr)){
        printf("value = %d top = %d\n",*getTop(arr),arr->top);
        pop(arr);
    }
    //现在是空栈了
    printf("\n递归演示\n");
    //栈的递归演示
    recursionDemo(arr,1);
}
void recursionDemo(array *arr,int count){

    //判断栈是否满，如果已满则不在继续执行。这是递归结束的条件
    if( !(arr->top < arr->length-1) ){
        return ;
    }

    push(arr,count);
    printf(" %d 元素进栈\n",count);

    //调用自身
    recursionDemo(arr,++count);

    //打印后 出栈
    printf(" %d 元素出栈\n",*getTop(arr));
    pop(arr);

}

/*
运行结果：

value = 5 top = 5
value = 4 top = 4
value = 3 top = 3
value = 2 top = 2
value = 1 top = 1

递归演示
 1 元素进栈
 2 元素进栈
 3 元素进栈
 4 元素进栈
 5 元素进栈
 5 元素出栈
 4 元素出栈
 3 元素出栈
 2 元素出栈
 1 元素出栈
请按任意键继续. . .
*/