【数据结构】一个数组实现两个栈

╰+哭是因爲堅強的太久メ 2022-09-27 14:22 152阅读 0赞

面对这个问题，我首先想到的是将一个数组的空间一分为二来为两个栈使用。可以将一个栈的底设在数组的起始位置，另一个栈的底设在数组的中间位置。但是这样并不能有效地利用数组的空间，比如当一个栈已满而另一个栈不满时，明明仍有剩余空间，却无法向前一个栈压入数据。为了能有效利用空间，考虑将两个栈的底分别设在数组的两端，这样栈顶位置由两端向中间移动保证了在数组空间被全部使用之前，元素可以压入任意一个栈中。

***Talk is cheap，show you the code.***

#include <stdio.h>
    #include <stdlib.h>
    #define MaxSize 10
    typedef struct{
        int Date[MaxSize];
        int Top1;
        int Top2;
    } DStack;
    
    void Push(DStack *PtrS, int item, int tag)
    {
        if(PtrS->Top2 - PtrS->Top1 == 1){
            printf("栈已满\n");
            return;
        }
        if(tag == 1)
            PtrS->Date[++PtrS->Top1] = item;
        else
            PtrS->Date[--PtrS->Top2] = item;
    }
    int Pop(DStack *PtrS,int tag)
    {
        if(tag == 1){
            if(PtrS->Top1 == -1){
                printf("栈已空\n");
                return NULL;
            }
            else
                return PtrS->Date[PtrS->Top1--];
        }
        else{
            if(PtrS->Top2 == MaxSize){
                printf("栈已空\n");
                return NULL;
            }
            else
                return PtrS->Date[PtrS->Top2++];
        }
    }