6-7在一个数组中实现两个堆栈

题目描述

实现带头结点的链式表操作集，也就是对带头结点的链表进行增删改查。

题目地址为:https://pintia.cn/problem-sets/15/problems/730

Stack结构定义 其中Tag是堆栈编号，取1或2；MaxSize堆栈数组的规模 

1
2
3
4
5
6
7
typedef int Position;
struct SNode {
    ElementType *Data;
    Position Top1, Top2;
    int MaxSize;
};
typedef struct SNode *Stack;

思考

位置安排

两个栈如何来安排位置？

比较容易想到的也就是教科书上所描述的那种方式，栈顶放在中间。

栈顶元素

那么栈顶是否存放元素呢？

如果栈顶存放元素，栈的起始位置应该为-1以及MaxSize（数组刚好越界为1的地方）。不存放的话也和这个差别不大。秉持勤俭节约的美德，还是放元素吧！

判满判空

对于两个栈分别判满这个简单，就看栈顶加一或者减一是否和另一个栈栈顶重合。

判空那就更简单了，直接看栈顶位置，要是是越界的就是空的。

创建堆栈

要求

观察结构体发现需要两次malloc，一次是具体存放数据的数组，另一次是管理堆栈的数据结构

具体代码

1
2
3
4
5
6
7
8
9
Stack CreateStack( int MaxSize ) {
    ElementType* Data = (ElementType *)malloc(sizeof(ElementType) * MaxSize);
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = Data;
    S->Top1 = -1;
    S->Top2 = MaxSize;
    S->MaxSize = MaxSize;
    return S;
}

入栈

要求

如果堆栈已满，Push函数必须输出“Stack Full”并且返回false。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool Push( Stack S, ElementType X, int Tag ) {
    if (Tag == 1) {
        if(S->Top1 + 1 == S->Top2) {
            printf("Stack Full\n");
            return false;
        }
        S->Top1++;
        S->Data[S->Top1] = X;
    } else {
        if(S->Top2 - 1 == S->Top1) {
            printf("Stack Full\n");
            return false;
        }
        S->Top2--;
        S->Data[S->Top2] = X;
    }
    return true;
}

出栈

要求

如果某堆栈是空的，则Pop函数必须输出“Stack Tag Empty”（其中Tag是该堆栈的编号），并且返回ERROR。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ElementType Pop( Stack S, int Tag ) {
    ElementType number;
    if (Tag == 1) {
        if (S->Top1 == -1) {
            printf("Stack %d Empty\n",Tag);
            return ERROR;
        }
        number = S->Data[S->Top1];
        S->Top1--;
    } else {
        if (S->Top2 == S->MaxSize) {
            printf("Stack %d Empty\n",Tag);
            return ERROR;
        }
        number = S->Data[S->Top2];
        S->Top2++;
    }
    return number;
}