[C++知识库]C语言实现队列

代码

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

//链表队列
typedef struct Node { //链表节点的自定义数据类型
    int val;
    struct Node *next;
} Node;

typedef struct Queue {
    Node *head, *tail;
} Queue;

Node *initNode(int val) { //初始化链表节点
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n) return NULL;
    n->val = val;
    n->next = NULL;
    return n;
}

void freeNode(Node *p) { //释放链表节点
    if (p) free(p);
    return ;
}

Queue *initQueue() { //初始化队列
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->head = NULL, q->tail = NULL;
    return q;
}

void freeQueue(Queue *q) {
    if (!q) return ;
    Node *p = q->head, *k;
    while (p) {
        k = p;
        p = p->next;
        freeNode(k);
    }
    free(q);
    return ;
}

int push(Queue *q, int val) { //入队列
    if (!q) return 0;
    Node *n = initNode(val);
    if (!n) return 0;
    if (q->tail) { //尾插法
        q->tail->next = n;
        q->tail = n;
    } else //空链表
        q->head = n, q->tail = n;
    return 1;
}

int isEmpty(Queue *q) {
    return !(q && q->head);
}

int pop(Queue *q) { //出队列
    Node *k = q->head;
    int tmp = k->val;
    q->head = k->next;
    freeNode(k);
    if (!q->head) q->tail = NULL;
    return tmp;
}

#if 0 //普通队列
typedef struct Queue {
    int *data, size, head, tail;
} Queue;

int expand(Queue *q);

Queue *initQueue(int n) { //初始化
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->data = (int *)malloc(sizeof(int) * n);
    q->size = n;
    q->head = 0;
    q->tail = 0;
}

void freeQueue(Queue *q) {
    if (!q) return ;
    free(q->data);
    free(q);
    return ;
}

int push(Queue *q, int val) {
    if (!q) return 0;
    if ((q->tail + 1) % q->size == q->head) { //满队
        if (!expand(q)) return 0;
    }
    q->data[q->tail] = val;
    q->tail = (q->tail + 1) % q->size;
    return 1;
}

int isEmpty(Queue *q) {
    return !q || q->head == q->tail;
}

int pop(Queue *q) {
    int tmp = q->data[q->head];
    q->head = (q->head + 1) % q->size;
    return tmp;
}

int expand(Queue *q) { //扩容
    if (!q) return 0;
    int expsize = q->size, *tmp;
    while (expsize) {
        tmp = (int *)malloc(sizeof(int) * (q->size + expsize));
        if (tmp) break;
        expsize >>= 1;
    }
    if (!tmp) return 0;

    //把队列中德数据搬到新家
    int i, j;
    for (i = q->head, j = 0; i != q->tail; i = (i +1) % q->size, ++j)
        tmp[j] = q->data[i];
    free(q->data);

    q->data = tmp, q->head = 0, q->tail = j, q->size += expsize;
    printf("expand successfully~, new size is %d\n", q->size);

    return 1;
}
#endif

int main() {
    return 0;
}