程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 隊列——鏈表與數組實現(數據結構與算法分析C語言版)

隊列——鏈表與數組實現(數據結構與算法分析C語言版)

編輯：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
    {
        P->Next = NULL;
        P->Element = X;
        Q->Rear->Next = P;
        Q->Rear = P;
    }
}

ElementType Front( Queue Q )
{
    return Q->Front->Next->Element;
}

ElementType FrontAndDequeue( Queue Q )
{
    ElementType X = 0;
    if (!IsEmpty(Q))
    {
        X = Front(Q);
        Dequeue(Q);
    }
    else
    {
        printf("The queue is empty!\n");
    }
    return X;
}

void PrintQueue( Queue Q )
{
    QNodePtr P = Q->Front;
    while (P != Q->Rear)
    {
        P = P->Next;
        printf("%d\n", P->Element);
    }
}

#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
{
  P->Next = NULL;
  P->Element = X;
  Q->Rear->Next = P;
  Q->Rear = P;
}
}

ElementType Front( Queue Q )
{
return Q->Front->Next->Element;
}

ElementType FrontAndDequeue( Queue Q )
{
ElementType X = 0;
if (!IsEmpty(Q))
{
  X = Front(Q);
  Dequeue(Q);
}
else
{
  printf("The queue is empty!\n");
}
return X;
}

void PrintQueue( Queue Q )
{
QNodePtr P = Q->Front;
while (P != Q->Rear)
{
P = P->Next;
printf("%d\n", P->Element);
}
}循環隊列一般是用循環數組實現，其判空條件有多種方式：其一是設一個標志位以區別隊列是空還是滿；其二是少用一個元素空間，約定以隊列頭指針在隊列尾指針的下一位置上作為隊列呈滿狀態標志。或者是如下面代碼所示，為表示隊列的結構體設置一個表示隊列大小的size標志，若size為0，那麼隊列為空。
數組實現：隊列頭文件，queue.h

[cpp]
typedef int ElementType;

#ifndef _QUEUE_
#define _QUEUE_

struct QueueRecord;
typedef QueueRecord *Queue;

int IsEmpty( Queue Q );
int IsFull( Queue Q );
Queue CreateQueue( int MaxElements );
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 );

#endif

typedef int ElementType;

#ifndef _QUEUE_
#define _QUEUE_

struct QueueRecord;
typedef QueueRecord *Queue;

int IsEmpty( Queue Q );
int IsFull( Queue Q );
Queue CreateQueue( int MaxElements );
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 );

#endif實現文件：queue.cpp

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

struct QueueRecord
{
    int Capacity;
    int Front;
    int Rear;
    int Size;
    ElementType *Array;
};

int IsEmpty( Queue Q )
{
    return Q->Size == 0;
}

int IsFull( Queue Q )
{
    return Q->Size == Q->Capacity;
}

void MakeEmpty( Queue Q )
{
    Q->Size = 0;
    Q->Front = 1;
    Q->Rear = 0;
}

Queue CreateQueue( int MaxElements )
{
    Queue Q;
    Q = (Queue)malloc(sizeof(struct QueueRecord));
    if (Q == NULL)
    {
        printf("Out of space!\n");
        return NULL;
    }
    Q->Array = (ElementType*)malloc(sizeof(ElementType) * MaxElements);
    if (Q->Array == NULL)
    {
        printf("Out of space!\n");
        return NULL;
    }
    Q->Capacity = MaxElements;
    MakeEmpty(Q);
    return Q;
}

void DisposeQueue( Queue Q )
{
    if (Q != NULL)
    {
        free(Q->Array);
        free(Q);
    }
}

static int Succ(int Value, Queue Q)
{
    if (++Value == Q->Capacity)
        Value = 0;
    return Value;
}

void EnQueue( ElementType X, Queue Q )
{
    if (IsFull(Q))
    {
        printf("Queue is full!\n");
        return;
    }
    else
    {
        Q->Size++;
        Q->Rear = Succ(Q->Rear, Q);
        Q->Array[Q->Rear] = X;
    }
}

ElementType Front( Queue Q )
{
    if (!IsEmpty(Q))
    {
        return Q->Array[Q->Front];
    }
    printf("Queue is Empty!\n");
    return 0;
}

void Dequeue( Queue Q )
{
    if (!IsEmpty(Q))
    {
        Q->Size--;
        Q->Front = Succ(Q->Front, Q);
    }
    else
    {
        printf("Queue is Empty!\n");
    }
}

ElementType FrontAndDequeue( Queue Q )
{
    ElementType X = 0;
    if (!IsEmpty(Q))
    {
        Q->Size--;
        X = Q->Array[Q->Front];
        Q->Front = Succ(Q->Front, Q);
    }
    else
    {
        printf("Queue is Empty!\n");
    }
    return X;
}

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

struct QueueRecord
{
int Capacity;
int Front;
int Rear;
int Size;
ElementType *Array;
};

int IsEmpty( Queue Q )
{
return Q->Size == 0;
}

int IsFull( Queue Q )
{
return Q->Size == Q->Capacity;
}

void MakeEmpty( Queue Q )
{
Q->Size = 0;
Q->Front = 1;
Q->Rear = 0;
}

Queue CreateQueue( int MaxElements )
{
Queue Q;
Q = (Queue)malloc(sizeof(struct QueueRecord));
if (Q == NULL)
{
  printf("Out of space!\n");
  return NULL;
}
Q->Array = (ElementType*)malloc(sizeof(ElementType) * MaxElements);
if (Q->Array == NULL)
{
  printf("Out of space!\n");
  return NULL;
}
Q->Capacity = MaxElements;
MakeEmpty(Q);
return Q;
}

void DisposeQueue( Queue Q )
{
if (Q != NULL)
{
free(Q->Array);
free(Q);
}
}

static int Succ(int Value, Queue Q)
{
if (++Value == Q->Capacity)
Value = 0;
return Value;
}

void EnQueue( ElementType X, Queue Q )
{
if (IsFull(Q))
{
  printf("Queue is full!\n");
  return;
}
else
{
  Q->Size++;
  Q->Rear = Succ(Q->Rear, Q);
  Q->Array[Q->Rear] = X;
}
}

ElementType Front( Queue Q )
{
if (!IsEmpty(Q))
{
return Q->Array[Q->Front];
}
printf("Queue is Empty!\n");
return 0;
}

void Dequeue( Queue Q )
{
if (!IsEmpty(Q))
{
  Q->Size--;
  Q->Front = Succ(Q->Front, Q);
}
else
{
  printf("Queue is Empty!\n");
}
}

ElementType FrontAndDequeue( Queue Q )
{
ElementType X = 0;
if (!IsEmpty(Q))
{
  Q->Size--;
  X = Q->Array[Q->Front];
  Q->Front = Succ(Q->Front, Q);
}
else
{
  printf("Queue is Empty!\n");
}
return X;
}