《栈和队列学习笔记》-队列代码实现

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

typedef struct vector {
    int *data;
    int size;
}vector;

typedef struct Queue {
    vector *data;
    int size, head, tail, count;
} Queue;

vector *initVector(int n) {
    vector *v = (vector *)malloc(sizeof(vector));
    v->size = n;
    v->data = (int *)malloc(sizeof(int) * n);
    return v;
}

int vectorSeek(vector *v, int pos) {
    if (pos < 0 || pos >= v->size) return -1;
    return v->data[pos];
}

int insertVector(vector *v, int pos, int val) {
    if (pos < 0 || pos >= v->size) return 0;
    return v->data[pos] = val;
}

void clearVector(vector *v) {
    if (v == NULL) return ;
    free(v->data);
    free(v);
    return ;
}

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

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

int push(Queue *q, int val) {
    if (q->count == q->size) return 0;
    insertVector(q->data, q->tail, val);
    q->tail += 1;
    if (q->tail == q->size) q->tail = 0;
    q->count += 1;
    return 1;
}

int front(Queue *q) { 
    return vectorSeek(q->data, q->head);
}

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

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

void outputQueue(Queue *q) {
    printf("Queue : ");
    for (int i = 0; i < q->count; i++) {
        printf("%4d", vectorSeek(q->data, (q->head + i) % q->size));
    }
    printf("\n");
    return ;
}

int main() {
    srand(time(0));

    #define MAX_OP 10
    Queue *q = initQueue(5);
    for (int i = 0; i < MAX_OP; i++) {
        int op = rand() % 5, val = rand() % 100; 
        switch (op) {
            case 0:
                printf("front of queue : %d\n", front(q));
                pop(q);
                break;
            case 1:
            case 2:
            case 3:
            case 4: 
                printf("push %d to queue\n", val);
                push(q, val);
                break;
        }
        outputQueue(q);
    }
    clearQueue(q);
    return 0;
}

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

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

typedef struct LinkList{
    Node head, *tail;

}LinkList;

typedef struct Queue {
    LinkList *l;
    int count;
} Queue;

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

LinkList *initLinkList() {
    LinkList *l = (LinkList *)malloc(sizeof(LinkList));
    l->head.next = NULL;
    l->tail = &(l->head);
    return l;
}

int emptyList(LinkList *l) {
    return l->head.next == NULL;
}

int frontList(LinkList *l) {
    if (emptyList(l)) return 0;
    return l->head.next->data;
}

int insertTail(LinkList *l, int val) {
    Node *node = getNewNode(val);
    l->tail->next = node;
    l->tail = node;
    return 1;
}

int eraseHead(LinkList *l) {
    if (emptyList(l)) return 0;
    Node *p = l->head.next;
    l->head.next = l->head.next->next;
    free(p);
    if (p == l->tail) l->tail = &(l->head);
    return 1;
}

void clearLinkList(LinkList *l) {
    Node *p = l->head.next, *q;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    free(l);
    return ;
}

Queue *initQueue() {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->l = initLinkList();
    q->count = 0;
    return q;
}

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

int front(Queue *q) {
    if (empty(q)) return 0;

    return frontList(q->l);
}

int pop(Queue *q) {
    eraseHead(q->l);
    q->count--;
    return 1;
}

int push(Queue *q, int val) {
    insertTail(q->l, val);
    q->count++;
    return 1;
}

void clearQueue(Queue *q) {
    if (q == NULL) return ;
    clearLinkList(q->l);
    free(q);
    return ;
}

void outputQueue(Queue *q) {
    printf("Queue : ");
    Node *p = q->l->head.next;
    for (int i = 0; i < q->count; i++) {
        printf("%4d", p->data);
        p = p->next;
    }
    printf("\n\n");
    return ;
}

int main() {
    srand(time(0));

    #define MAX_OP 10
    Queue *q = initQueue();
    for (int i = 0; i < MAX_OP; i++) {
        int op = rand() % 5, val = rand() % 100; 
        switch (op) {
            case 0:
                printf("front of queue : %d\n", front(q));
                pop(q);
                break;
            case 1:
            case 2:
            case 3:
            case 4: 
                printf("push %d to queue\n", val);
                push(q, val);
                break;
        }
        outputQueue(q);
    }
    clearQueue(q);

    return 0;
}