手写C版本的queue

记录一个小demo，留着以后批判。

实现了除了运算符重载以外的所有功能(大概)，测试时没发现问题。queue使用的是const static queuefuntion queue **类似于C++的namespace**中的通用接口。

用到的宏

1
#define TYPE int//勉强范型吧

data定义

1
2
3
4
5
6
7
8
typedef struct queuedata{
    TYPE data;
    unsigned int size;
    struct queuedata* next;
    struct queuedata* prev;
    struct queuedata* head;
    struct queuedata* tail;
}queuedata;

funtion定义

1
2
3
4
5
6
7
8
9
10
typedef struct queuefuntion{
    queuedata* (*initqueue)(TYPE);
    TYPE (*front)(queuedata*);
    TYPE (*back)(queuedata*);
    unsigned int (*size)(queuedata*);
    char (*empty)(queuedata*);
    void (*push)(queuedata*,TYPE);
    void (*pop)(queuedata*);
    void (*swap)(queuedata**,queuedata**);
}queuefuntion;

测试函数

1
2
3
4
5
6
7
8
9
10
11
12
void queuetest(void){
    queuedata* q = queue.initqueue(20);
    queue.pop(q);
    printf("back = %d\n",queue.back(q));
    queue.push(q,10);
    for(int i  = 0 ; i < 1000; i++)
        queue.push(q,i);
    for(int i = 0; i < 100; i++)
        queue.pop(q);
    printf("fornt = %d back = %d\n",queue.front(q),queue.back(q));
    
}

完整代码

Queue.h

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
//
//  queue.h
//  CwithSTL
//
//  Created by echo on 2021/2/21.
//  Copyright © 2021 echo. All rights reserved.
//

#ifndef queue_h
#define queue_h

#include <stdio.h>
#include <stdlib.h>
#define TYPE int
typedef struct queuedata{
    TYPE data;
    unsigned int size;
    struct queuedata* next;
    struct queuedata* prev;
    struct queuedata* head;
    struct queuedata* tail;
}queuedata;

typedef struct queuefuntion{
    queuedata* (*initqueue)(TYPE);
    TYPE (*front)(queuedata*);
    TYPE (*back)(queuedata*);
    unsigned int (*size)(queuedata*);
    char (*empty)(queuedata*);
    void (*push)(queuedata*,TYPE);
    void (*pop)(queuedata*);
    void (*swap)(queuedata**,queuedata**);
}queuefuntion;


#endif /* queue_h */

Queue.c

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
//
//  queue.c
//  CwithSTL
//
//  Created by echo on 2021/2/21.
//  Copyright © 2021 echo. All rights reserved.
//

#include "queue.h"

TYPE Qfront(queuedata* this){
    if(this->head->next == this->tail){
        printf("the queue is empty!\n");
        return (TYPE)(0);
    }else{
        return this->head->next->data;
    }
}

TYPE Qback(queuedata* this){
    if(this->tail->prev == this->head){
        printf("Warning: the queue is empty!\n");
        return (TYPE)(0);
    }else{
        return this->tail->prev->data;
    }
}

unsigned int Qsize(queuedata* this){
    return this->size;
}

char Qempty(queuedata* this){
    return this->data != 0 ? 0 : 1;//size == 0 return true
}

void Qpush(queuedata* this,TYPE data){
    queuedata* tmp = (queuedata*)malloc(sizeof(queuedata));
    this->tail->prev->next = tmp;//tail节点的前一节点的next指针指向插入节点
    tmp->prev = this->tail->prev;//插入节点的prev指针指向tail节点的前一节点
    tmp->next = this->tail;//插入节点的next指针指向tail节点
    this->tail->prev = tmp;//tail节点的prev指针指向插入节点
    this->size++;
    tmp->data = data;
}

void Qpop(queuedata* this){
    if(this->size == 0){
        printf("the queue is empty\n");
        return;
    }
    queuedata* tmp = this->tail->prev;
    tmp->prev->next = this->tail;
    this->tail->prev = tmp->prev;
    this->size--;
    free(tmp);
    tmp = NULL;
}

void Qswap(queuedata** p,queuedata** q){
    queuedata* tmp = *q;
    p = q;
    q = &tmp;
}

queuedata* initqueue(TYPE data){
    queuedata* this = (queuedata*)malloc(sizeof(queuedata));
    this->head = (queuedata*)malloc(sizeof(queuedata));
    this->tail = (queuedata*)malloc(sizeof(queuedata));
    this->head->prev = NULL;
    this->head->next = this;
    this->tail->prev = this;
    this->tail->next = NULL;
    this->next = this->tail;
    this->prev = this->head;
    this->data = data;
    this->size = 1;
    return  this;
}


const struct queuefuntion queue = {
    initqueue,Qfront,Qback,Qsize,Qempty,Qpush,Qpop,Qswap
};

Main.c

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
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "vector.h"
#include "stack.h"
#include "queue.h"
extern const struct VectorFuntion vector;
//貌似sort有点小问题，排序貌似不支持01开始
extern const struct stackFuntion stack;
//貌似deque有点小问题，不支持扩容，最大容量通过修改stack.c中的SIZE宏来确定
extern const struct queuefuntion queue;
//queue没有使用deque容器，使用过程中没有发现问题

void queuetest(void){
    queuedata* q = queue.initqueue(20);
    queue.pop(q);
    printf("back = %d\n",queue.back(q));
    queue.push(q,10);
    for(int i  = 0 ; i < 1000; i++)
        queue.push(q,i);
    for(int i = 0; i < 100; i++)
        queue.pop(q);
    printf("fornt = %d back = %d\n",queue.front(q),queue.back(q));
    
}

int main(){
    queuetest();
    return 0;
}