Data Structure - Queue (C)

柔光的暖阳◎ 2023-01-18 14:20 204阅读 0赞

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.captainbed.net]

/*
     * Fatal.h - by FreeMan
     */
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define Error( Str )        FatalError( Str )
    #define FatalError( Str )   fprintf( stderr, "%s\n", Str ), exit( 1 )

/*
     * Queue.h - by FreeMan
     */
    
    typedef int ElementType;
    
    #ifndef _Queue_H_
    #define _Queue_H_
    
    struct QueueRecord;
    typedef struct QueueRecord *Queue;
    
    int IsQueueEmpty(Queue Q);
    int IsQueueFull(Queue Q);
    Queue CreateQueue(int MaxElements);
    void DisposeQueue(Queue Q);
    void MakeQueueEmpty(Queue Q);
    void Enqueue(ElementType X, Queue Q);
    ElementType FrontOfQueue(Queue Q);
    void Dequeue(Queue Q);
    ElementType FrontAndDequeue(Queue Q);
    
    #endif

/*
     * Queue.c - by FreeMan
     */
    
    #include "Queue.h"
    #include "..\Fatal.h"
    #include <stdlib.h>
    
    #define MinQueueSize ( 5 )
    
    struct QueueRecord
    {
        int Capacity;
        int Front;
        int Rear;
        int Size;
        ElementType *Array;
    };
    
    int IsQueueEmpty(Queue Q)
    {
        return Q->Size == 0;
    }
    
    int IsQueueFull(Queue Q)
    {
        return Q->Size == Q->Capacity;
    }
    
    Queue CreateQueue(int MaxElements)
    {
        Queue Q;
    
        if (MaxElements < MinQueueSize)
        {
            Error("Queue size is too small!");
        }
    
        Q = malloc(sizeof(struct QueueRecord));
        if (Q == NULL)
        {
            FatalError("Out of memory!!");
        }
    
        Q->Array = malloc(sizeof(ElementType) * MaxElements);
        if (Q->Array == NULL)
        {
            FatalError("Out of memory!!");
        }
    
        Q->Capacity = MaxElements;
        MakeQueueEmpty(Q);
    
        return Q;
    }
    
    void MakeQueueEmpty(Queue Q)
    {
        Q->Size = 0;
        Q->Front = 1;
        Q->Rear = 0;
    }
    
    void DisposeQueue(Queue Q)
    {
        if (Q != NULL)
        {
            free(Q->Array);
            free(Q);
        }
    }
    
    static int Successor(int Value, Queue Q)
    {
        if (++Value == Q->Capacity)
        {
            Value = 0;
        }
        return Value;
    }
    
    void Enqueue(ElementType X, Queue Q)
    {
        if (IsQueueFull(Q))
        {
            Error("Full queue!");
        }
        else
        {
            Q->Rear = Successor(Q->Rear, Q);
            Q->Array[Q->Rear] = X;
            Q->Size++;
        }
    }
    
    ElementType FrontOfQueue(Queue Q)
    {
        if (!IsQueueEmpty(Q))
        {
            return Q->Array[Q->Front];
        }
        Error("Empty queue!");
        return 0; /* Return value used to avoid warning */
    }
    
    void Dequeue(Queue Q)
    {
        if (IsQueueEmpty(Q))
        {
            Error("Empty queue!");
        }
        else
        {
            Q->Front = Successor(Q->Front, Q);
            Q->Size--;
        }
    }
    
    ElementType FrontAndDequeue(Queue Q)
    {
        ElementType X = 0;
    
        if (IsQueueEmpty(Q))
        {
            Error("Empty queue!");
        }
        else
        {
            X = Q->Array[Q->Front];
            Q->Front = Successor(Q->Front, Q);
            Q->Size--;
        }
        return X;
    }

/*
     * QueueTest.c - by FreeMan
     */
    
    #include "Queue.h"
    #include <stdio.h>
    
    main()
    {
        Queue Q;
        int i;
    
        Q = CreateQueue(12);
    
        for (i = 0; i < 10; i++)
        {
            Enqueue(i, Q);
        }
    
        while (!IsQueueEmpty(Q))
        {
            printf("%d\n", FrontOfQueue(Q));
            Dequeue(Q);
        }
    
        for (i = 0; i < 10; i++)
        {
            Enqueue(i, Q);
        }
    
        while (!IsQueueEmpty(Q))
        {
            printf("%d\n", FrontOfQueue(Q));
            Dequeue(Q);
        }
    
        DisposeQueue(Q);
    
        return 0;
    }
    
    // Output:
    /*
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    
    */

[http_www.captainbed.net]: http://www.captainbed.net/troubleshooter