博客

原理：

想要一个数组实现两个栈，那么就必须一个栈的栈顶从数组下标为0处开始，另一个栈从数组额最大下标处开始，两个栈相对而生如下图所示：

如何判断栈满？

当两个栈顶标记重合时，表示共享栈已经满了

代码如下：

头文件ShareStack.h

#pragma once

#include<stdio.h>
#include<stdlib.h>

typedef char StackType;

typedef struct ShareStack{
    StackType* space;
    size_t size_left;
    size_t size_right;
    size_t max_size;
}ShareStack;

void ShareStackInit(ShareStack* stack); //共享栈的初始化

void ShareStackDestroy(ShareStack* stack); //销毁共享栈


//对左边栈进行操作
void LeftShareStackPush(ShareStack* stack, StackType value);//入栈

void LeftShareStackPop(ShareStack* stack); //出栈

int LeftShareStackTop(ShareStack* stack, StackType* value); //取栈顶元素


//对右边栈进行操作
void RightShareStackPush(ShareStack* stack, StackType value); //入栈

void RightShareStackPop(ShareStack* stack); //出栈

int RightShareStackTop(ShareStack* stack, StackType* value);//取栈顶元素

头文件的实现ShareStack.c：

#include"ShareStack.h"

void ShareStackInit(ShareStack* stack) {
    if(stack == NULL) {
        return;
    }
    stack->max_size = 10;
    stack->size_left = 0;
    stack->size_right = stack->max_size;
    stack->space = malloc(stack->max_size * sizeof(ShareStack));
    return;
}

void ShareStackDestroy(ShareStack* stack) {
    if(stack == NULL) {
        return;
    }
    stack->max_size = 0;
    stack->size_left = 0;
    stack->size_right = 0;
    free(stack->space);
    stack->space = NULL;
}

void LeftShareStackPush(ShareStack* stack, StackType value) {
    if(stack == NULL) {
        return;
    }
    if(stack->size_left == stack->size_right) {
        return;
    }
    stack->space[stack->size_left] = value;
    stack->size_left++;
    return;
}

void LeftShareStackPop(ShareStack* stack) {
    if(stack == NULL) {
        return;
    }
    if(stack->size_left == 0) {
        return;
    }
    stack->size_left--;
    return;
}

int LeftShareStackTop(ShareStack* stack, StackType* value) {
    if(stack == NULL || value == NULL) {
        return 0;
    }
    if(stack->size_left == 0) {
        return 0;
    }
    *value = stack->space[stack->size_left - 1];
    return 1;
}


void RightShareStackPush(ShareStack* stack, StackType value) {
    if(stack == NULL) {
        return;
    }
    if(stack->size_left == stack->size_right) {
        return;
    }
    stack->size_right--;
    stack->space[stack->size_right] = value;
    return;
}

void RightShareStackPop(ShareStack* stack) {
    if(stack == NULL) {
        return;
    }
    if(stack->size_left == stack->max_size) {
        return;
    }
    stack->size_right++;
    return;
}

int RightShareStackTop(ShareStack* stack, StackType* value) {
    if(stack == NULL || value == NULL) {
        return 0;
    }
    if(stack->size_right == stack->max_size) {
        return 0;
    }
    *value = stack->space[stack->size_right];
    return 1;
}

///
//以下为测试代码
///

void TestShareStack() {
    int ret;
    StackType value;
    ShareStack stack;
    ShareStackInit(&stack);
    printf("LeftStack:\n");
    LeftShareStackPush(&stack, 'a');
    LeftShareStackPush(&stack, 'b');
    LeftShareStackPush(&stack, 'c');
    LeftShareStackPush(&stack, 'd');
    ret = LeftShareStackTop(&stack, &value);
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect d, actual %c\n", value);
    LeftShareStackPop(&stack);

    ret = LeftShareStackTop(&stack, &value);
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect c, actual %c\n", value);
    LeftShareStackPop(&stack);

    ret = LeftShareStackTop(&stack, &value);
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect b, actual %c\n", value);
    LeftShareStackPop(&stack);

    ret = LeftShareStackTop(&stack, &value);
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect a, actual %c\n", value);
    LeftShareStackPop(&stack);

   ret = LeftShareStackTop(&stack, &value); //对空栈进行取栈顶元素
    LeftShareStackPop(&stack); //对空栈出栈
    printf("ret expect 0, actual %d\n", ret);



    printf("\nRightStack\n");
    RightShareStackPush(&stack, 'A');
    RightShareStackPush(&stack, 'B');
    RightShareStackPush(&stack, 'C');
    RightShareStackPush(&stack, 'D');

    ret = RightShareStackTop(&stack, &value);
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect D, actual %c\n", value);
    RightShareStackPop(&stack);

    ret = RightShareStackTop(&stack, &value);
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect C, actual %c\n", value);
    RightShareStackPop(&stack);

    ret = RightShareStackTop(&stack, &value);
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect B, actual %c\n", value);
    RightShareStackPop(&stack);

    ret = RightShareStackTop(&stack, &value);
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect A, actual %c\n", value);
    RightShareStackPop(&stack);

   ret = RightShareStackTop(&stack, &value); //对空栈进行取栈顶元素
    RightShareStackPop(&stack); //对空栈出栈
    printf("ret expect 0, actual %d\n", ret);

    ShareStackDestroy(&stack);
}

int main()
{
    TestShareStack();
    return 0;
}