共享栈的一种实现方法
in 算法与数据结构 with 0 comment

共享栈的一种实现方法

in 算法与数据结构 with 0 comment

共享栈的一种实现方法

栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

口诀

进栈时:先压后加
出栈时:先减后弹
注:进栈时候应该先把元素压入栈,在让top移动到其下一个位置。
出栈时,应该先把top移动到当前栈顶元素,然后再弹出去。
(这里说的top指向的始终为当前元素的下一个位置,下面的代码部分中演示的top指向的是当前位置。
其实这两者都是一样的,只需要做稍微的改动就可以。)

#include<stdio.h> 
#include<malloc.h> 
//定义 
typedef struct{
    int top[2], bot[2];
    int *V;
    int m;
}DblStack;

/* 
初始化:为栈空间分配一个大小为m的数组空间。0号栈的栈顶指针和栈底指针的初始值都是-1; 
1号栈的栈顶指针和栈底指针的初始值都是m。表示栈空。
*/
int InitStack(DblStack &S, int m){

    //S.V=new int[m];//写成下面的语句也一样  
    S.V = (int *)malloc(m*sizeof(int));
    if (!S.V){
        return 0;//存储分配失败  
    }
    S.top[0] = -1;
    S.bot[0] = -1;
    S.top[1] = m;
    S.bot[1] = m;
    return 1;
}

/* 
判断双栈是否为空:0号栈的栈顶指针和栈底指针的初始值都是-1; 
1号栈的栈顶指针和栈底指针的初始值都是m。表示栈空。 
*/
int IsEmpty(DblStack &S){
    if ((S.top[0] == S.bot[0]) && (S.top[1] == S.bot[1])){
        return 1;//栈空  
    }
    else{
        return 0;//栈非空  
    }
}

/* 
判断栈是否满:当S.top[1]-S.top[0]==1时,表示栈满。
*/
int IsFull(DblStack &S){
    if (S.top[1] - S.top[0] == 1){
        return 1;//栈满  
    }
    else{
        return 0;//栈不满  
    }
}

/* 
进栈:首先判断栈是否满,若满返回0;否则返回1.
*/
int Push(DblStack &S, int e1, int e2){
    //元素e1进入0号栈,元素e2进入1号栈  
    if (IsFull(S)){
        return 0;//栈已满,无法入栈  
    }
    // *++S.top[0]=e1; 
    // *++S.top[1]=e2; 
    S.V[++S.top[0]] = e1;
    //因为栈空间是放在数组中的,所以,进操作类似于向数组中添加元素。  
    S.V[--S.top[1]] = e2;
    return 1;
}

/* 
出栈:首先判断栈是否为空,若空返回0;否则返回1。
*/
int Pop(DblStack &S, int &e1, int &e2){
    //用e1返回0号栈的栈顶元素;用e2返回1号栈的栈顶元素。 
    if (IsEmpty(S)){
        return 0;
    }
    // e1=*--S.top[0]; 
    // e2=*--S.top[1]; 
    e1 = S.V[S.top[0]--];//出栈操作也类似于数组的操作。  
    e2 = S.V[S.top[1]++];
    return 1;
}


int main(){

    DblStack S;
    int m;
    printf("请输入双栈的数组空间大小:");
    scanf_s("%d", &m);
    if (InitStack(S, m)){
        printf("双栈初始化成功!\n");
    }
    else{
        printf("双栈初始化失败!\n");
    }

    if (IsEmpty(S)){
        printf("双栈S为空!\n");
    }
    else{
        printf("双栈S非空!\n");
    }

    if (IsFull(S)){
        printf("双栈已满!\n");
    }
    else{
        printf("双栈未满!\n");
    }

    int n;
    printf("请输入每个栈入栈的元素个数:");
    scanf_s("%d", &n);
    for (int i = 0; i<n; i++){
        int e1, e2;
        printf("请输入每个栈的第%d个元素:", i + 1);
        scanf_s("%d%d", &e1, &e2);
        if (Push(S, e1, e2)){
            printf("入栈成功\n");
        }
        else{
            printf("入栈失败\n");
        }
    }

    int e1, e2;
    Pop(S, e1, e2);
    printf("两个栈的栈顶元素出栈:%d %d", e1, e2);
}
Responses