这个是使用数组实现的顺序栈，可以实现扩容和缩容，链表栈原理一样，上一篇链表中也实现了相关的函数，直接调用即可完成栈操作，就不重复写了。

扩容规则是栈满则扩大一倍；

缩容规则是当前数量为容量的 1/4 时，容量缩小到当前的一半，之所以要到 1/4 的时候再缩容而不是到 1/2 就缩容，是为了防止数量刚到 1/2 时又立刻压入栈元素导致扩容，缩容后立即扩容会有以下两个问题：

  1. 效率低下，申请资源和释放资源都都需要时间，这个问题可以使用链表解决，但这里仅讨论顺序表实现的顺序栈；
  2. 因为是顺序栈，万一资源紧张，当释放掉一半的资源后立即申请两倍的资源，是有可能申请不到的，这个也可以用链表栈解决；

相关结构体定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//
// Created by Tianyi on 2021/11/2.
//

#ifndef DATA_STRUCT_ARRAYSTACK_STRUCT_H
#define DATA_STRUCT_ARRAYSTACK_STRUCT_H

#endif //DATA_STRUCT_ARRAYSTACK_STRUCT_H

struct ArrayStack {
    int * data;
    int count;
    int capacity;
};

顺序栈相关操作

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
//
// Created by Tianyi on 2021/11/2.
//
#include <stdlib.h>
#include <string.h>

#ifndef DATA_STRUCT_ARRAYSTACK_UTILS_H
#define DATA_STRUCT_ARRAYSTACK_UTILS_H

#endif //DATA_STRUCT_ARRAYSTACK_UTILS_H

typedef struct ArrayStack ArrayStack;

void extendList(struct ArrayStack *stack);

void reduceList(struct ArrayStack *stack);

void addLastEle(struct ArrayStack *stack, int element);

void removeEle(struct ArrayStack *stack, int index);


struct ArrayStack *newStack(int capacity) {

    int *data = (int *) calloc(capacity, sizeof(int));

    struct ArrayStack *stack = (ArrayStack *) malloc(sizeof(ArrayStack));

    stack->data = data;
    stack->capacity = capacity;
    stack->count = 0;

    return stack;
}


void push(struct ArrayStack *stack, int element) {
    addLastEle(stack, element);
}


int top(struct ArrayStack *stack) {
    int top = stack->data[stack->count - 1];
    return top;
}


int pop(struct ArrayStack *stack) {
    int topValue = top(stack);
    removeEle(stack, stack->count - 1);
    return topValue;
}


void addEle(struct ArrayStack *stack, int index, int element) {
    // 判断是否需要扩容
    if (stack->count + 1 > stack->capacity) {
        extendList(stack);
    }
    // 判断传入的下标是否有效
    if (index >= stack->capacity || index < 0) {
        printf("This index is invalid!!!");
        return;
    }
    // 单独拿出数组操作
    int *data = stack->data;
    // 在指定位置插入元素
    for (int i = stack->count; i > index; i--) {
        data[i] = data[i - 1];
    }
    data[index] = element;
    stack->count++;
}


void addLastEle(struct ArrayStack *stack, int element) {
    addEle(stack, stack->count, element);
}


void removeEle(struct ArrayStack *stack, int index) {
    // 先判断 List 是否为空
    if (stack->count == 0) {
        printf("This list is empty, there is no element to delete!!!");
    }
    // 判断传入的下标是否有效
    if (index >= stack->capacity || index < 0) {
        printf("This index is invalid!!!");
        return;
    }
    // 单独拿出数组操作
    int *data = stack->data;
    // 删除指定位置元素（数据往前移动，count - 1）
    for (int i = index; i < stack->count - 1; ++i) {
        data[i] = data[i + 1];
    }
    stack->count--;
    // 判断是否需要缩容
    if (stack->count <= stack->capacity / 4) {
        reduceList(stack);
    }
}


void extendList(struct ArrayStack *stack) {
    int *newData = (int *) calloc(stack->capacity * 2, sizeof(int));
    int *oldData = stack->data;
    for (int i = 0; i < stack->count; ++i) {
        newData[i] = oldData[i];
    }
    free(oldData);
    stack->capacity = stack->capacity * 2;
    stack->data = newData;
}


void reduceList(struct ArrayStack *stack) {
    int *newData = (int *) calloc(stack->capacity / 4, sizeof(int));
    int *oldData = stack->data;
    for (int i = 0; i < stack->capacity / 2; ++i) {
        newData[i] = oldData[i];
    }
    free(oldData);
    stack->capacity = stack->capacity / 2;
    stack->data = newData;
}


void show(struct ArrayStack *stack) {

    for (int level = stack->count - 1; level >= 0 ; level--) {
        printf("stack level %d -- value %d\n", level, stack->data[level]);
    }
}

测试代码

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
#include <stdio.h>

#include "lib/struct.h"
#include "lib/utils.h"

int main() {
    struct ArrayStack * stack = newStack(5);
    for (int i = 0; i < 40; ++i) {
        push(stack, i);
    }
    show(stack);
    printf("======================\n");
    for (int i = 0; i < 5; ++i) {
        int value = pop(stack);
        printf("pop value is %d\n", value);
    }
    printf("======================\n");
    show(stack);
    for (int i = 0; i < 30; ++i) {
        int value = pop(stack);
    }
    printf("======================\n");
    show(stack);
    return 0;
}