队列——链表与数组实现(数据结构与算法分析C语言版)

链队列：一个链队列显然需要两个分别指向队头和队尾的指针（即头指针和尾指针）才能唯一确定。一般，为了操作方便，可以给链队列添加一个头结点，并令头指针指向头结点。由此，空的链队列的判决条件为：头指针和尾指针均指向头结点，如下图所示：

头文件：queue.h

[cpp]
typedef int ElementType;

#ifndef _QUEUE_LIST_
#define _QUEUE_LIST_

struct QNode;
struct Node;
typedef QNode *QNodePtr;
typedef Node *PtrToNode;
typedef PtrToNode Queue;

int IsEmpty( Queue Q );                       //判断队列是否为空Q->Rear == Q->Front;
Queue CreateQueue();                         //构造队列
void DisposeQueue( Queue Q );                //删除整个队列，回收空间
void MakeEmpty( Queue Q );                  //释放队列空间，将其置为空
void EnQueue( ElementType X, Queue Q );     //在队列尾端插入元素
ElementType Front( Queue Q );              //取出对头元素，但不删除
void Dequeue( Queue Q );                   //删除对头元素
ElementType FrontAndDequeue( Queue Q );   //
void PrintQueue( Queue Q );               //打印队列

#endif

typedef int ElementType;

#ifndef _QUEUE_LIST_
#define _QUEUE_LIST_

struct QNode;
struct Node;
typedef QNode *QNodePtr;
typedef Node *PtrToNode;
typedef PtrToNode Queue;

int IsEmpty( Queue Q );                       //判断队列是否为空Q->Rear == Q->Front;
Queue CreateQueue();                         //构造队列
void DisposeQueue( Queue Q );                //删除整个队列，回收空间
void MakeEmpty( Queue Q );                  //释放队列空间，将其置为空
void EnQueue( ElementType X, Queue Q );     //在队列尾端插入元素
ElementType Front( Queue Q );              //取出对头元素，但不删除
void Dequeue( Queue Q );                   //删除对头元素
ElementType FrontAndDequeue( Queue Q );   //
void PrintQueue( Queue Q );               //打印队列

#endif实现文件queue.c

[cpp] view plaincopyprint?#include "queue.h"
#include <stdio.h>
#include <stdlib.h>

struct QNode
{
    ElementType Element;
    QNodePtr Next;
};

struct Node
{
    QNodePtr Front;
    QNodePtr Rear;
};

int IsEmpty( Queue Q )
{
    return Q->Rear == Q->Front;
}

void MakeEmpty( Queue Q )
{
    if (Q == NULL)
    {
        printf("The queue is empty! Must use CreateQueue first!\n");
        return;
    }
    else
    {
        while(!IsEmpty(Q))
            Dequeue(Q);
    }
}

Queue CreateQueue()
{
    //不仅要为对头(Queue)申请空间，还要为队列元素/节点（QNode）申请空间.
    Queue Q;
    Q = (Queue)malloc(sizeof(struct Node));
    if (Q == NULL)
    {
        printf("Out of space!\n");
        return NULL;
    }
    Q->Front = Q->Rear = (QNodePtr)malloc(sizeof(struct QNode));

    if (Q->Front == NULL)
    {
        printf("Out of space!\n");
        return NULL;
    }
    Q->Front->Next = NULL;
    return Q;
}

void DisposeQueue( Queue Q )
{
    while (Q->Front != NULL)
    {
        Q->Rear = Q->Front->Next;
        free(Q->Front);
        Q->Front = Q->Rear;
    }
}

void Dequeue( Queue Q )
{
    //删除链队列第一个元素
    if (!IsEmpty(Q))
    {
        QNodePtr P;
        P = Q->Front->Next;
        Q->Front->Next = P->Next;
        if (Q->Rear == P)          //判断队列中是否只有一个元素
            Q->Rear = Q->Front;
        free(P);
    }
    else
    {
        printf("The queue is empty!\n");
    }
}

void EnQueue( ElementType X, Queue Q )
{
    QNodePtr P = (QNodePtr)malloc(sizeof(struct QNode));
    if (P == NULL)
    {
        printf("Out of space!\n");
        return;
    }
    else
  &nbs

补充：软件开发 , C++ ,