DS2

3.21 Write routines to implement two stacks using only one arrayYour stack routines should not declare an overflow unless everyslot in the array is used
3.21 编写例程以仅使用一个数组实现两个堆栈除非使用了数组中的每个插槽，否则堆栈例程不应声明溢出

考虑使用如下逻辑结构：

source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>
#include <stdlib.h>

typedef int Array;
Array arr[10];
int l_top, r_top;

//init arr -1
void init() {
    for (int i = 0; i < 10; i++) {
        arr[i] = -1;
    }
    l_top = -1, r_top = 10;
}

void exam() {
    //print arr
    printf("[");
    for (int i = 0; i < 9; i++) {
        printf("%d ", arr[i]);
    }
    printf("%d]\n", arr[9]);
    if (l_top >= r_top) {
        printf("Stack overflow!\n");
    }
    else {
        printf("Stack not overflow!\n");
    }
}

int main() {
    init();
    //e.g.1 pop 3 numbers from left,and pop 7 numbers from right
    printf("---e.g.1---\n");
    for (int i = 0; i < 3; i++) {
        arr[++l_top] = 233;
        exam();
    }
    for (int i = 0; i < 7; i++) {
        arr[--r_top] = 666;
        exam();
    }
    init();
    //e.g.2 pop 3 numbers from left,and pop 8 numbers from right
    printf("---e.g.2---\n");
    for (int i = 0; i < 3; i++) {
        arr[++l_top] = 233;
        exam();
    }
    for (int i = 0; i < 8; i++) {
        arr[--r_top] = 666;
        exam();
    }
    return 0;
}

Part of output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
---e.g.1---
[233 -1 -1 -1 -1 -1 -1 -1 -1 -1]
Stack not overflow!
... ...
[233 233 233 -1 666 666 666 666 666 666]
Stack not overflow!
[233 233 233 666 666 666 666 666 666 666]
Stack not overflow!
---e.g.2---
[233 -1 -1 -1 -1 -1 -1 -1 -1 -1]
Stack not overflow!
... ...
[233 233 233 666 666 666 666 666 666 666]
Stack not overflow!
[233 233 666 666 666 666 666 666 666 666]
Stack overflow!

raw output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
---e.g.1---
[233 -1 -1 -1 -1 -1 -1 -1 -1 -1]
Stack not overflow!
[233 233 -1 -1 -1 -1 -1 -1 -1 -1]
Stack not overflow!
[233 233 233 -1 -1 -1 -1 -1 -1 -1]
Stack not overflow!
[233 233 233 -1 -1 -1 -1 -1 -1 666]
Stack not overflow!
[233 233 233 -1 -1 -1 -1 -1 666 666]
Stack not overflow!
[233 233 233 -1 -1 -1 -1 666 666 666]
Stack not overflow!
[233 233 233 -1 -1 -1 666 666 666 666]
Stack not overflow!
[233 233 233 -1 -1 666 666 666 666 666]
Stack not overflow!
[233 233 233 -1 666 666 666 666 666 666]
Stack not overflow!
[233 233 233 666 666 666 666 666 666 666]
Stack not overflow!
---e.g.2---
[233 -1 -1 -1 -1 -1 -1 -1 -1 -1]
Stack not overflow!
[233 233 -1 -1 -1 -1 -1 -1 -1 -1]
Stack not overflow!
[233 233 233 -1 -1 -1 -1 -1 -1 -1]
Stack not overflow!
[233 233 233 -1 -1 -1 -1 -1 -1 666]
Stack not overflow!
[233 233 233 -1 -1 -1 -1 -1 666 666]
Stack not overflow!
[233 233 233 -1 -1 -1 -1 666 666 666]
Stack not overflow!
[233 233 233 -1 -1 -1 666 666 666 666]
Stack not overflow!
[233 233 233 -1 -1 666 666 666 666 666]
Stack not overflow!
[233 233 233 -1 666 666 666 666 666 666]
Stack not overflow!
[233 233 233 666 666 666 666 666 666 666]
Stack not overflow!
[233 233 666 666 666 666 666 666 666 666]
Stack overflow!