抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

栈与队列

秃头王
基础数据结构

发布于：2022年1月16日
次浏览

队列 (FIFO)

结构操作：尾部入队、头部出队（排队做核酸！捅一个走一个 哈哈哈！）

FIFO first in firas out : 先进先出

结构定义：

队列长度 (length)

队头位置 (head)

队尾位置 (tail)

任意类型元素 (data_type) (int \ char)

连续空间存储

循环队列

在队列结构定义之上 count

计数 (count) 可判断满和空

tail % leng

image-20220116103748456

出队操作 - 入队操作

出队 (head += 1)

入队 (tail += 1)

假溢出

出队操作 - 入队操作 - 假溢出优化

入队 (q->count != q->length) 当前队列数据总长度 (count)、队列总长度 (q->length)

满足条件情况：

  1. q->data[q->tail++] = val;
  2. if(q->tail == q->leng ) q->tail = 0;
  3. q->count++;

出队 empty(q) 是否存在元素

满足条件情况：

  1. q->head++;
  2. if(q->head == q->leng) q->head = 0;
  3. q->count–;

image-20220116102131019

队列代码演示 - 无假溢出优化

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
/*************************************************************************
        > File Name: 队列 - 假溢出.c
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2022年01月16日 星期日 09时44分03秒
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct Queue {
    int *data;
    int head, tail;
    int length;
} Queue;

Queue *init(int n) {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->data = (int *)malloc(sizeof(int) * n);
    q->head = 0;
    q->tail = 0;
    q->length = n;
    return q;
}

int push(Queue *q, int val) {
    // 空
    if(q == NULL) return 0;
    // 满
    if(q->tail == q->length) return 0;
    q->data[q->tail++] = val;
    return 1;
}

int empty(Queue *q) {
    return q->tail == q->head;
}

int pop(Queue *q) {
    if(q == NULL) return 0;
    if(empty(q)) return 0;
    q->head++;
    return 1;
}

int front(Queue *q) {
    if(q == NULL) return -1;
    return q->data[q->head];
}

void clear(Queue *q) {
    if(q == NULL) return ;
    free(q->data);
    free(q);
    return ;
}

void output(Queue *q) {
    if(q == NULL) return ;
    printf("Queue(%d) [", q->length);
    for(int i = q->head; i < q->tail; i++) {
        i != q->head && printf(",");
        printf("%d", q->data[i]);
    }
    printf("]");
    printf("\n");
    return ;
}

int main() {
    #define MAX_OP  20
    srand(time(0));
    Queue *q = init(MAX_OP);
    for(int i = 0; i < MAX_OP; i++) {
        // 0 1 2
        int op = rand() % 3;
        int val = rand() % 100;
        switch(op) {
            case 0: {
                if(!empty(q)) {
                    printf("pop front from the Queue = %d \n", pop(q));
                }
            } break;
            case 1: {
                printf("push %d to the Queue = %d\n", val, push(q, val));
            } break;
            case 2: {
                printf("front one from Queue = %d\n", front(q));
            } break;
        }
        output(q), printf("\n");
    }
    #undef MAX_OP
    clear(q);
    return 0;
}

队列代码演示 - 假溢出优化

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
/*************************************************************************
        > File Name: 队列 - 假溢出优化.c
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2022年01月16日 星期日 09时44分03秒
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct Queue {
    int *data;
    int head, tail;
    int length;
    int count;
} Queue;

Queue *init(int n) {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->data = (int *)malloc(sizeof(int) * n);
    q->head = 0;
    q->tail = 0;
    q->count = 0;
    q->length = n;
    return q;
}

int push(Queue *q, int val) {
    // 空
    if(q == NULL) return 0;
    // 满
    if(q->length == q->count) return 0;
    q->data[q->tail++] = val;
    if(q->tail == q->length) q->tail = 0;
    q->count++;
    return 1;
}

int empty(Queue *q) {
    return q->count == 0;
}

int pop(Queue *q) {
    if(q == NULL) return 0;
    if(empty(q)) return 0;
    q->head++;
    if(q->head == q->length) q->head = 0;
    q->count--;
    return 1;
}

int front(Queue *q) {
    if(q == NULL) return -1;
    return q->data[q->head];
}

void clear(Queue *q) {
    if(q == NULL) return ;
    free(q->data);
    free(q);
    return ;
}

void output(Queue *q) {
    if(q == NULL) return ;
    printf("Queue(%d) [", q->length);
    for(int i = q->head, j = 0; j < q->count; j++) {
        j && printf(",");
        printf("%d", q->data[(i + j) % q->length]);
    }
    printf("]");
    printf("\n");
    return ;
}

int main() {
    #define MAX_OP  20
    srand(time(0));
    Queue *q = init(4);
    for(int i = 0; i < MAX_OP; i++) {
        // 0 1 2
        int op = rand() % 3;
        int val = rand() % 100;
        switch(op) {
            case 0: {
                if(!empty(q)) {
                    printf("pop front from the Queue = %d \n", pop(q));
                }
            } break;
            case 1: {
                printf("push %d to the Queue = %d\n", val, push(q, val));
            } break;
            case 2: {
                printf("front one from Queue = %d\n", front(q));
            } break;
        }
        output(q), printf("\n");
    }
    #undef MAX_OP
    clear(q);
    return 0;
}

队列代码演示 - 假溢出优化 - 自动扩容

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
/*************************************************************************
        > File Name: 栈与队列.c
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2022年01月16日 星期日 09时44分03秒
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct Queue {
    int *data;
    int head, tail;
    int length;
    int count;
} Queue;

Queue *init(int n) {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->data = (int *)malloc(sizeof(int) * n);
    q->head = 0;
    q->tail = 0;
    q->count = 0;
    q->length = n;
    return q;
}

int expand(Queue *q) {
    int extr_size = q->length;
    int *p;
    while(extr_size) {
        p = (int *)malloc(sizeof(int) * (extr_size + q->length)); // 不能用 realloc
        if(p != NULL) break;
        extr_size >>= 1;
    }
    if(p == NULL) return 0;
    for(int i = q->head, j = 0; j < q->count; j++) {
        p[j] = q->data[(i + j) % q->length];
    }
    q->data = p;
    q->head = 0, q->tail = q->count;
    q->length += extr_size;
    return 1;
}

int push(Queue *q, int val) {
    // 空
    if(q == NULL) return 0;
    // 满
    if(q->length == q->count) {
        if(!expand(q)) {
            printf("自动扩容失败！\n");
            return 0;
        }
        printf("自动扩容成功！\n");
    }
    q->data[q->tail++] = val;
    if(q->tail == q->length) q->tail = 0;
    q->count++;
    return 1;
}

int empty(Queue *q) {
    return q->count == 0;
}

int pop(Queue *q) {
    if(q == NULL) return 0;
    if(empty(q)) return 0;
    q->head++;
    if(q->head == q->length) q->head = 0;
    q->count--;
    return 1;
}

int front(Queue *q) {
    if(q == NULL) return -1;
    return q->data[q->head];
}

void clear(Queue *q) {
    if(q == NULL) return ;
    free(q->data);
    free(q);
    return ;
}

void output(Queue *q) {
    if(q == NULL) return ;
    printf("Queue(%d) [", q->length);
    for(int i = q->head, j = 0; j < q->count; j++) {
        j && printf(",");
        printf("%d", q->data[(i + j) % q->length]);
    }
    printf("]");
    printf("\n");
    return ;
}

int main() {
    #define MAX_OP  20
    srand(time(0));
    Queue *q = init(1);
    for(int i = 0; i < MAX_OP; i++) {
        // 0 1 2
        int op = rand() % 3;
        int val = rand() % 100;
        switch(op) {
            case 0: {
                if(!empty(q)) {
                    printf("pop front from the Queue = %d \n", pop(q));
                }
            } break;
            case 1: {
                printf("push %d to the Queue = %d\n", val, push(q, val));
            } break;
            case 2: {
                printf("front one from Queue = %d\n", front(q));
            } break;
        }
        output(q), printf("\n");
    }
    #undef MAX_OP
    clear(q);
    return 0;
}

栈 (FILO) - (手枪弹夹🔫)

FILO first in last out : 先进后出

结构定义：

栈大小 (size)

栈顶指针 (top)

栈中元素 (data_type)

连续空间存储

image-20220116171822673

栈代码演示 - 自动扩容

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
/*************************************************************************
        > File Name: 栈.c
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2022年01月16日 星期日 17时20分08秒
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Stack {
    int *data;
    int size;
    int top;
} Stack;

Stack *init(int n) {
    Stack *s = (Stack *) malloc(sizeof(Stack));
    s->data = (int *)malloc(sizeof(int) * n);
    s->size = n;
    s->top = -1;
    return s;
}

void clear(Stack *s) {
    if(s == NULL) return ;
    free(s->data);
    free(s);
    return ;
}
int expand(Stack *s) {
    int extr_size = s->size;
    int *p;
    while(extr_size) {
        p = (int *) realloc(s->data,sizeof(int) * ( extr_size * s->size));
        if(p != NULL) break;
        extr_size >>= 1;
    }
    if(p == NULL) return 0;
    s->data = p;
    s->size += extr_size;
    return 1;
}

int push(Stack *s, int val) {
    if(s == NULL) return 0;
    if(s->top == s->size - 1) {
        if(!expand(s)) {
            printf("自动扩容失败！\n");
            return 0;
        }
        printf("自带扩容成功！\n");
    }
    s->data[++(s->top)] = val;
    return 1;
}

int empty(Stack *s) {
    if(s == NULL) return 1;
    return s->top == -1;
}

int pop(Stack *s) {
    if(s == NULL) return 0;
    if(empty(s)) return 0;
    s->top--;
    return 1;
}

int top(Stack *s) {
    if(s == NULL) return 0;
    if(empty(s)) return 0;
    return s->data[s->top];
}

void output(Stack *s) {
    if(s == NULL) return ;
    printf("Stack(%d, %d) : [", s->size, s->top);
    for(int i = s->top; ~i; i--) {
        i != s->top && printf(", ");
        printf("%d", s->data[i]);
    }
    printf("]\n");
    return ;
}

int main() {
    srand(time(0));
    #define MAX_OP 20
    Stack *s = init(1);
    for(int i = 0; i < MAX_OP; i++) {
        int val = rand() % 100;
        int op = rand() % 3;
        switch(op) {
            case 0: {
                if(s != NULL)
               printf("top %d from the Stack \n", top(s));
            } break;
            case 1: {
                printf("push %d to the Stack = %d\n", val, push(s, val));
            } break;
            case 2: {
                if(s != NULL)
                printf("pop %d from the Stack \n", pop(s));
            } break;
        }
        output(s), printf("\n");
    }

    #undef MAX_OP
    clear(s);
    return 0;
}

链栈

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
/*************************************************************************
        > File Name: 链栈.cpp
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2022年01月18日 星期二 16时28分15 秒
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct StackNode {
    int data;
    StackNode *next;
} StackNode;

typedef struct LinkStack {
    StackNode *top;
    int length;
} LinkStack;

StackNode *init_node(int val) {
    StackNode *p = (StackNode * )malloc(sizeof(StackNode));
    p->data = val;
    p->next = NULL;
    return p;
}

LinkStack *init_stack() {
    LinkStack *l = (LinkStack *)malloc(sizeof(LinkStack));
    l->top = NULL;
    l->length = 0;
    return l;
}

int empty(LinkStack *l) {
    return l->top == NULL;
}

int Stack_top(LinkStack *l) {
    if(empty(l)) return -1;
    return l->top->data;
}

int push(LinkStack *l, int val) {
    if(l == NULL) return 0;
    StackNode *node = init_node(val);
    node->next = l->top;
    l->top = node;
    l->length += 1;
    return 1;
}

void clear_node(StackNode *node) {
    if(node == NULL) return ;
    free(node);
    return ;
}

void clear(LinkStack *l) {
    if(l == NULL) return ;
    StackNode *p = l->top, *t;
    while(p) {
        t = p->next;
        clear_node(p);
        p = t;
    }
    free(l);
    return ;
}

int pop(LinkStack *l) {
    if(l == NULL) return 0;
    if(empty(l)) return 0;
    StackNode *p = l->top;
    l->top = l->top->next;
    clear_node(p);
    l->length -= 1;
    return 1;
}

void output_node(StackNode *p) {
    if(p == NULL) return ;
    while(p) {
        printf("%d ", p->data);
        p = p->next;
    }
    return ;
}

void output(LinkStack *l) {
    if(l == NULL) return ;
    printf("LinkStack(%d) : ", l->length);
    output_node(l->top);
    printf("\n");
    return ;
}

int main() {
    srand(time(0));
    #define MAX_OP 20
    LinkStack *s = init_stack();
    for(int i = 0; i < MAX_OP; i++) {
        int op = rand() % 2;
        int val = rand() % 100;
        switch(op) {
            case 0 : {
                printf("pop %d from the LinkStack = ", Stack_top(s));
                printf("%d\n", pop(s));
            } break;
            case 1 : {
                printf("push %d to the form LinkStack = %d\n", val, push(s, val));
            } break;
        }
        output(s), printf("\n");
    }

    return 0;
}

// 待做 链栈、链队列、循环队列扩容、还没实现

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://tutouwang.vercel.app/2022/01/16/%E5%9F%BA%E7%A1%80%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97/

更新于：2022年5月22日

栈与队列

评论