1. 普通队列

1.1. Queue.h

#pragma once

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

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

typedef struct Queue {
    Node *head;
    Node *rear;
} Queue;

void QueueInit(Queue *pQ);

void QueueDestroy(Queue *pQ);

Node* getNode(int data);

void QueuePush(Queue *pQ, int data);

void QueuePop(Queue *pQ);

int QueueHead(Queue *pQ);

int QueueRear(Queue *pQ);

int QueueEmpty(Queue *pQ);

int QueueSize(Queue *pQ);

1.2. Queue.c

#include "Queue.h"

void QueueInit(Queue *pQ) {
    assert(pQ);

    pQ->head = NULL;
    pQ->rear = NULL;
}

void QueueDestroy(Queue *pQ) {
    assert(pQ);

    Node *cur, *tmp;
    cur = pQ->head;
    while (cur) {
        tmp = cur->next;
        free(cur);
        cur = tmp;
    }
    pQ = NULL;
}

Node* getNode(int data) {
    Node* res = (Node *)malloc(sizeof(Node));
    res->next = NULL;
    res->data = data;

    return res;
}

void QueuePush(Queue *pQ, int data) {
    assert(pQ);

    Node* newNode = getNode(data);
    if (pQ->head == NULL) {  // empty queue
        pQ->head = pQ->rear = newNode;
    }
    else {
        pQ->rear = pQ->rear->next = newNode;
    }
}

void QueuePop(Queue *pQ) {
    assert(pQ);

    if (pQ->head != NULL) {  // if not empty queue
        Node *tmp = pQ->head;
        if (pQ->head == pQ->rear) {  // only one node
            pQ->head = pQ->rear = NULL;
        }
        else {
            pQ->head = pQ->head->next;
        }
        free(tmp);
    }
}

int QueueHead(Queue *pQ) {
    assert(pQ);
    assert(pQ->head);

    return pQ->head->data;
}

int QueueRear(Queue *pQ) {
    assert(pQ);
    assert(pQ->rear);

    return pQ->rear->data;
}

int QueueEmpty(Queue *pQ) {
    assert(pQ);

    return pQ->head == NULL;
}

int QueueSize(Queue *pQ) {
    assert(pQ);

    Node* cur = pQ->head;
    int count = 0;

    while (cur) {
        cur = cur->next;
        count++;
    }

    return count;
}

2. 循环队列

2.1. CircleQueue.h

#pragma once

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

#define CAPACITY 10

typedef struct CircleQueue {
    int arr[CAPACITY];
    int head;
    int rear;
} CQueue;

void CQueueInit(CQueue *pCQ);

void CQueueDestroy(CQueue *pCQ);

void CQueuePush(CQueue *pCQ, int data);

void CQueuePop(CQueue *pCQ);

int CQueueHead(CQueue *pCQ);

int CQueueRear(CQueue *pCQ);

int CQueueEmpty(CQueue *pCQ);

int CQueueSize(CQueue *pCQ);

void TestCQ();

2.2. CircleQueue.c

#include "CircleQueue.h"

void CQueueInit(CQueue *pCQ) {
    assert(pCQ);

    pCQ->head = pCQ->rear = 0;
}

void CQueueDestroy(CQueue *pCQ) {
    assert(pCQ);

    // do nothing
    // stack data can't be destroyed
}

void CQueuePush(CQueue *pCQ, int data) {
    assert(pCQ);

    if ((pCQ->rear + 1) % CAPACITY != pCQ->head) {
        pCQ->arr[pCQ->rear] = data;
        pCQ->rear = (pCQ->rear + 1) % CAPACITY;
    }
}

void CQueuePop(CQueue *pCQ) {
    assert(pCQ);

    if (pCQ->rear != pCQ->head) {  // not empty
        pCQ->head = (pCQ->head + 1) % CAPACITY;
    }
}

int CQueueHead(CQueue *pCQ) {
    assert(pCQ);

    return pCQ->arr[pCQ->head];
}

int CQueueRear(CQueue *pCQ) {
    assert(pCQ);

    return pCQ->arr[pCQ->rear == 0 ? CAPACITY - 1 : pCQ->rear - 1];
}

int CQueueEmpty(CQueue *pCQ) {
    assert(pCQ);

    return pCQ->head == pCQ->rear;
}

int CQueueSize(CQueue *pCQ) {
    return pCQ->rear + (pCQ->rear >= pCQ->head ? 0 : 1) * CAPACITY - pCQ->head;
}

void TestCQ() {
    CQueue cq;
    CQueueInit(&cq);

    CQueuePush(&cq, 1);
    CQueuePush(&cq, 2);
    CQueuePush(&cq, 3);
    CQueuePush(&cq, 4);
    CQueuePush(&cq, 5);

    CQueuePop(&cq);
    CQueuePop(&cq);
    CQueuePop(&cq);

    CQueuePush(&cq, 6);
    CQueuePush(&cq, 7);
    CQueuePush(&cq, 8);
    CQueuePush(&cq, 9);
    CQueuePush(&cq, 10);
    CQueuePush(&cq, 11);
    CQueuePush(&cq, 12);
    CQueuePush(&cq, 13);

    printf("size : %d\n", CQueueSize(&cq));

    printf("\n");
}
Last modification:September 7th, 2019 at 07:38 pm