数据结构-栈

Posted on | In |

基本操作

描述：FILO（先进后出）

只允许栈顶进行删除和插入

  • 创建
  • 销毁
  • 长度
  • 是否满
  • 是否空
  • 入栈
  • 出栈
  • 遍历

实现

顺序栈
1
2
3
4
5
6
7
8
9
//栈数据
typedef struct array_stack
{
    int size;//栈大小
    int pos;//栈顶元素
    int *array;//数据存储区
}ArrayStack;

void array_stack_test(void);
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>


/**
 获取栈长度

 @param stack 栈
 @return 栈长度
 */
int array_stack_length(ArrayStack *stack)
{
    return stack->size;
}

/**
 获取栈是否空

 @param stack 栈
 @return 是否空
 */
bool array_stack_is_empty(ArrayStack *stack)
{
    return stack->pos == -1;
}

/**
 获取栈是否满

 @param stack 栈
 @return 是否满
 */
bool array_stack_is_full(ArrayStack *stack)
{
    return stack->pos == (stack->size - 1);
}

/**
 初始化栈

 @param size 栈大小
 @return 栈
 */
ArrayStack *array_stack_create(int size)
{
    ArrayStack *stack = (ArrayStack *)malloc(sizeof(ArrayStack));
    if (stack == NULL) {
        return NULL;
    }
    
    stack->size = size;
    stack->pos = -1;
    stack->array = (int *)malloc(sizeof(int) * size);
    
    if (stack->array == NULL) {
        free(stack);
        return NULL;
    }
    
    return stack;
}

/**
 销毁栈

 @param stack 栈
 */
void array_stack_destory(ArrayStack *stack)
{
    if (stack == NULL) {
        return;
    }
    
    if (stack->array != NULL) {
        free(stack->array);
    }
    free(stack);
    return;
}

/**
 出栈

 @param stack 栈
 @return 栈顶元素
 */
int array_stack_pop(ArrayStack *stack)
{
    int data = 0;
    if (array_stack_is_empty(stack)) {
        return -1;
    }
    
    data = stack->array[stack->pos];
    stack->pos--;
    
    return data;
}

/**
 入栈

 @param stack 栈
 @param data 入栈元素
 @return 是否入栈成功
 */
int array_stack_push(ArrayStack *stack, int data)
{
    if (array_stack_is_full(stack)) {
        return -1;
    }
    
    stack->pos++;
    stack->array[stack->pos] = data;
    
    return 0;
}

/**
 入栈 不足申请新空间

 @param stack 栈
 @param data 入栈元素
 @return 是否入栈成功
 */
int array_stack_push_new(ArrayStack *stack, int data)
{
    if (!array_stack_is_full(stack)) {
        return array_stack_push(stack, data);
    }
    
    int *temp = (int *)malloc(2 * stack->size * sizeof(int));
    if (temp == NULL) {
        return -1;
    }
    
    memcpy(temp, stack->array, stack->size * sizeof(int));
    free(stack->array);
    
    stack->array = temp;
    stack->size = 2 * stack->size;
    stack->pos++;
    stack->array[stack->pos] = data;
    
    return 0;
}

/**
 遍历栈

 @param stack 栈
 */
void array_stack_dump(ArrayStack *stack)
{
    if (array_stack_is_empty(stack)) {
        printf("栈空\n");
        return ;
    }
    
    printf("打印栈size=%d,pos=%d\n",stack->size,stack->pos);
    for (int i = 0; i <= stack->pos; i++) {
        printf("array[%d] = %d\n",i,stack->array[i]);
    }
}

/**
 测试栈
 */
void array_stack_test()
{
    ArrayStack *stack = array_stack_create(4);
    if (stack == NULL) {
        printf("创建失败\n");
    }
    
    for (int i = 0; i < 5; i++) {
        int ret = array_stack_push(stack, i);
        if (ret != 0) {
            printf("入栈失败 %d\n",i);
        }
    }
    
    array_stack_dump(stack);
    
    int ret = array_stack_push_new(stack, 4);
    if (ret != 0) {
        printf("入栈失败\n");
    }
    array_stack_dump(stack);
    
    array_stack_destory(stack);
}
链栈
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
//栈数据
#include <stdio.h>
#include <stdbool.h>
typedef struct link_stack
{
    int data;//数据域
    struct link_stack *next;//指针域
}LinkStack;

/**
 获取栈是否空
 
 @param stack 栈
 @return 是否空
 */
bool link_stack_is_empty(LinkStack *stack);

/**
 初始化栈
 
 @return 栈
 */
LinkStack *link_stack_create(void);

/**
 销毁栈
 
 @param stack 栈
 */
void link_stack_destory(LinkStack *stack);

/**
 出栈
 
 @param stack 栈
 @param data 栈顶元素
 @return 是否出栈成功
 */
int link_stack_pop(LinkStack *stack, int *data);

/**
 栈顶元素
 
 @param stack 栈
 @param data 栈顶元素
 @return 是否获取栈顶成功
 */
int link_stack_top(LinkStack *stack, int *data);

/**
 入栈
 
 @param stack 栈
 @param data 入栈元素
 @return 是否入栈成功
 */
int link_stack_push(LinkStack *stack, int data);

/**
 遍历栈
 
 @param stack 栈
 */
void link_stack_dump(LinkStack *stack);

/**
 测试栈
 */
void link_stack_test(void);
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>


/**
 获取栈是否空
 
 @param stack 栈
 @return 是否空
 */
bool link_stack_is_empty(LinkStack *stack)
{
    return stack->next == NULL;
}

/**
 初始化栈
 
 @return 栈
 */
LinkStack *link_stack_create()
{
    LinkStack *stack = (LinkStack *)malloc(sizeof(LinkStack));
    if (stack == NULL) {
        return NULL;
    }
    stack->next = NULL;
    
    return stack;
}

/**
 销毁栈
 
 @param stack 栈
 */
void link_stack_destory(LinkStack *stack)
{
    LinkStack *temp = NULL;
    while (!link_stack_is_empty(stack)) {
        temp = stack->next;
        stack->next = temp->next;
        free(temp);
    }
    free(stack);
}

/**
 出栈
 
 @param stack 栈
 @param data 栈顶元素
 @return 是否出栈成功
 */
int link_stack_pop(LinkStack *stack, int *data)
{
    if (data == NULL) {
        return -1;
    }
    
    if (link_stack_is_empty(stack)) {
        return -1;
    }
    
    *data = stack->next->data;
    LinkStack *temp = stack->next;
    stack->next = temp->next;
    
    free(temp);
    
    return 0;
}


/**
 栈顶元素

 @param stack 栈
 @param data 栈顶元素
 @return 是否获取栈顶成功
 */
int link_stack_top(LinkStack *stack, int *data)
{
    if (data == NULL) {
        return -1;
    }
    
    if (link_stack_is_empty(stack)) {
        return -1;
    }
    
    *data = stack->next->data;
    
    return 0;
}

/**
 入栈
 
 @param stack 栈
 @param data 入栈元素
 @return 是否入栈成功
 */
int link_stack_push(LinkStack *stack, int data)
{
    LinkStack *temp = (LinkStack *)malloc(sizeof(LinkStack));
    if (temp == NULL) {
        return -1;
    }
    
    temp->data = data;
    temp->next = stack->next;
    stack->next = temp;
    
    return 0;
}

/**
 遍历栈
 
 @param stack 栈
 */
void link_stack_dump(LinkStack *stack)
{
    printf("打印栈\n");
    LinkStack *temp = stack->next;
    while (temp != NULL) {
        printf("data = %d\n",temp->data);
        temp = temp->next;
    }
}

/**
 测试栈
 */
void link_stack_test()
{
    LinkStack *stack = link_stack_create();
    if (stack == NULL) {
        printf("创建失败\n");
    }
    
    for (int i = 0; i < 4; i++) {
        int ret = link_stack_push(stack, i);
        if (ret != 0) {
            printf("入栈失败%d\n",i);
        }
    }
    
    link_stack_dump(stack);
    
    printf("出栈\n");
    int data = 0;
    for (int i = 0; i < 5; i++) {
        int ret = link_stack_pop(stack, &data);
        if (ret != 0) {
            printf("出栈失败%d\n",i);
        }
        else {
            printf("data = %d\n",data);
        }
    }
    link_stack_destory(stack);
}