数据结构之队列

 

  与栈相反，队列是一种先进先出的线性表，它只允许在表的一端进行，而在另一端删除元

素。

   在队列中，允许插入的一端叫做队尾，允许删除的一端则称为队头。

1、链队列——队列的链式表示和实现

   用链表表示的队列简称为链队列，一个链队列显然需要两个分别指示对头和队尾的指针

（分别称为头指针和尾指针）才能唯一确定。这里，和线性表的单链表一样，为了操作方便起

见，我们也给队列添加一个头结点。

   链队列的操作即为单链表的插入和删除操作的特殊情况，只是尚需修改尾指针或头指针。

   单链队列——队列的链式存储结构，如下所示。

//单链队列，队列的链式存储结构
typedef struct QNode
{
    ElemType data;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct
{
    QueuePtr front;            //队头指针
    QueuePtr rear;            //队尾指针
}LinkQueue;

2、单链队列的C语言操作

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

#define ElemType int

#define OK   1
#define ERROR 0


//单链队列，队列的链式存储结构
typedef struct QNode
{
    ElemType data;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct
{
    QueuePtr front;            //队头指针
    QueuePtr rear;            //队尾指针
}LinkQueue;

//构造一个空队列
int InitQueue(LinkQueue *q)
{
    //
    q->front = q->rear = (QueuePtr)malloc(sizeof(QNode));
    if(q->front == NULL)
    {
        fprintf(stderr, "malloc() error.\n");
        return ERROR;
    }

    q->front->next = NULL;
    q->rear->next = NULL;

    return OK;
}

//销毁队列，Q不在存在
int DestroyQueue(LinkQueue *q)
{
    //
    while(q->front)
    {
        q->rear = q->front->next;
        free(q->front);
        q->front = q->rear;
    }
    return OK;
}

//判断队列是否为空
int IsEmptyQueue(LinkQueue *q)
{
    return (q->front->next == NULL && q->rear->next == NULL);
}

//插入元素e为新的队尾元素
int InsertQueue(LinkQueue *q, ElemType e)
{
    //
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if(p == NULL)
    {
        fprintf(stderr, "malloc() error.\n");
        return ERROR;
    }

    p->data = e;
    p->next = NULL;

    //如果队列为空
    if(IsEmptyQueue(q))
    {
        q->front->next = p;
        q->rear = p;
    }
    else
    {
        q->rear->next = p;
        q->rear = p;            //不要忘记这句啊
    }
    return OK;
}

//若队列不空，则删除队头元素，用e返回其值，并返回OK
int DeQueue(LinkQueue *q, ElemType *e)
{
    //
    if(IsEmptyQueue(q))
    {
        fprintf(stdout, "the queue is null.\n");
        return ERROR;
    }

    //注意有队头结点
    QueuePtr temp;
    temp = q->front->next;
    *e = temp->data;

    q->front->next = temp->next;

    //一个元素
    if(q->rear == temp)
    {
        q->rear = q->front;
    }

    free(temp);

    return OK;
}

//打印队列
void printQueue(LinkQueue *q)
{
    QueuePtr  temp;
    temp = q->front->next;

    while(temp != NULL)
    {
        printf("%d   ", temp->data);
        temp = temp->next;
    }

}

int main(int argc, char **argv)
{
    LinkQueue *q;
    InitQueue(q);

    srand(time(NULL));

    int i = 0;
    for(i = 0; i < 10; i++)
    {
        InsertQueue(q, i);
    }

    printf("插入队列的元素为:\n");
    printQueue(q);

    int e;
    DeQueue(q, &e);
    printf("队头元素为: %d\n", e);

    return 0;
}

3、循环队列定义

   单链队列时，当队列为空时，front等于rear，现在循环队列当队列满时，也是front等

rear，那么如何判断此时的队列究竟是空还是满呢？

   办法一是设置一个标志变量flag，当front == rear，且flag = 0时为队列空，当front 

==rear，且flag = 1时为队列满；

   办法二是当队列空时，条件就是front == rear，当队列为满时，我们修改其条件，保留一

个元素空间。也就是说，队列满时，数组中还有一个空闲单元。例如下图所示，我们就认为此

队列已经满了，也就是说，我们不允许下图中的右图情况出现。

   我们重点来讨论第二种方法，由于rear可能比front大，也可能比front小，所以，尽管它

们只相差一个位置时就说满的情况，但也有可能是相差整整一圈。所以，若队列的最大尺寸为

QueueSize，那么队列满的条件是(rear + 1) % QueueSize == front（取模"%"的目的就说为

了整合rear与front大小为一个问题)。比如上面这个例子，QueueSzie = 5，上图中的左图中

front = 0，而rear = 4，（4 + 1） % 5 = 0，所以，此时队列满。再看右图，front = 2， 

而rear = 1，(1 + 1) %5 = 2，所以，此时队列也是满的。但是也有例外的情况。

   另外，通用的计算队列长度的公式为：(rear - front + QueueSize) % QueueSize

   循环队列的顺序存储结构，如下所示。

#define ElemType int

typedef struct
{
    ElemType data[MAXSIZE];
    int front;                //头指针
    int rear;                //尾指针，若队列不为空时，rear指向队列尾元素的下一个位置
}SqQueue;

4、循环队列的C操作

#define ElemType int

#define MAXSIZE 100

typedef struct
{
    ElemType data[MAXSIZE];
    int front;                //头指针
    int rear;                //尾指针，若队列不为空时，rear指向队列尾元素的下一个位置
}SqQueue;


#define OK      1
#define ERROR 0
//初始化一个空队列
int InitQueue(SqQueue *q)
{
    q->front = 0;
    q->rear  = 0;

    return OK;
}

//循环队列求队列长度
//返回队列的元素的个数，也就是队列的当前长度
int QueueLength(SqQueue *q)
{
    return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}

//循环队列的入队操作
//若队列未满，则插入元素e为队列新的队尾元素
int EnQueue(SqQueue *q, ElemType e)
{
    if((q->rear + 1) % MAXSIZE == q->front)    //队列满的判断
    {
        return ERROR;
    }

    q->data[q->rear] = e;                    //将元素e赋值给队尾
    q->rear = (q->rear + 1) MAXSIZE;        //rear指向后移一位置，若到最后则转为数组头部
                                            //注意
    return OK;
}

//循环队列的出对操作
//若队列不空，则删除q中队头元素，用e返回值
int DeQueue(SqQueue *q, ElemType *e)
{
    if(q->rear == q->front)                //队列空的判断
    {
        return ERROR;
    }

    *e = q->data[q->front];                //将队头元素赋值给e
    q->front = (q->front + 1) % MAXSIZE;//front指针向后一位置，若到最后，则转到数组头部

    return OK;
}

          参数：严蔚敏老师之《数据结构》、《大话数据结构》

                                                   梦醒潇湘love

                                                 2013-01-12 19:37