队列

2017-01-16 本文已影响95人 AceKitty

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。（先进先出）

队列的链试存储结构

队列既可以用链表实现，也可以用顺序表实现。跟栈相反的是，栈一般我们用顺序表来实现，而队列我们常用链表来实现，简称为链队列。

队列的定义

typedef int ElemType;
typedef struct QNode {
    ElemType data;
    struct QNode *next;
}QNode, *QueuePrt;
typedef struct {
    QueuePrt front, rear; //队头， 队尾
}LinkQueue;

将队头指针指向链表队列的头节点，而队尾指针指向终端节点。（注：头节点不是必要的，但是为了方便操作，我们加上了）

图片.png

空队列时，front和rear都指向头结点。

图片.png

创建一个队列
创建一个队列要完成两个任务：一是在内存中创建一个头结点，二是将队列的头指针和尾指针都指向这个生成的头节点，因为此时是空队列。

void initQueue(LinkQueue *q) {
    q->front = q->rear = (QueuePrt)malloc(sizeof(QNode));
    if (!q->front)
    {
        exit(0);
    }
    q->front->next = NULL;
}

*入队操作

//在队列中插入元素
void InsertQueue(LinkQueue *q, ElemType e) {
    QueuePrt p;
    p = (QueuePrt)malloc(sizeof(QNode));
    if (p == NULL)
    {
        exit(0);
    }
    p->data = e;
    p->next = NULL;
    q->rear->next = p;
    q->rear = p;
}

出队操作

//删除队列中的元素
void DeleteQueue(LinkQueue *q, ElemType *e) {
    QueuePrt p;
    if (q->front == q->rear)
    {
        return;
    }
    p = q->front->next;
    *e = p->data;
    q->front->next = p->next;
    if (q->rear == p)
    {
        q->rear = q->front;
    }
    free(p);
}

销毁队列

//销毁队列
void DestroyQueue(LinkQueue *q) {
    while (q->front)
    {
        q->rear = q->front->next;
        free(q->front);
        q->front = q->rear;
    }
}

队列的顺序存储结构

假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的存储单元，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端这是队头。

图片.png

入队出队操作：
入队列操作其实就是在队尾追加一个元素，不需要任何移动，时间复杂度为O(1)。出队列则不同，因为我们已经假设下标为0的位置是队列的队头，因此每次出队列操作所有元素都要向前移动。

图片.png

队列这样的入队出队操作会存在一些问题，例如按下边的情形继续入队列，就会出现数组越界的错误：

图片.png

循环队列
为了解决上述队列溢出问题，我们采用循环队列来实现。
循环队列它的容量是固定的，并且它的队头和队尾指针都可以随着元素入出队列而发生改变，这样循环队列逻辑上就好像是一个环形存储空间。

图片.png

定义一个循环队列

#define MAXSIZE 100
typedef struct {
    ElemType *base;//用于存放内存分配基地址 这里你也可以用数组存放
    int front;
    int rear;
}cycleQueue;

初始化循环队列

//循环队列的初始化
void initQueue(cycleQueue *q) {
    q->base = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
    if (!q->base)
    {
        exit(0);
    }
    q->front = q->rear = 0;
}

循环队列入队

//入队操作
void InsertQueue(cycleQueue *q, ElemType e) {
    if ((q->rear + 1)%MAXSIZE == q->front)
    {
        return; //队列已满
    }
    q->base[q->rear] = e;
    q->rear = (q->rear + 1) % MAXSIZE;
}

循环队出队

//出队列操作
void DeleteQueue(cycleQueue *q, ElemType *e) {
    if (q->front == q->rear)
    {
        return;//队列为空
    }
    *e = q->base[q->front];
    q->front = (q->front + 1) % MAXSIZE;
}

人生，仿佛是栈的重现。
每天你奔波于事业与家庭之间，做着似乎总是重复的事情，为的只是一餐温饱。
你总说，在哪里跌倒就在那里爬起来，但是，你发现似乎总是在同一个地方跌倒无数次！
有一那么一次，你弹栈找不到返回地址，你忧郁了，迷茫了。。。
但是，你抬头仰望星空，在孤独中多思考，在彷徨中多回顾，就有希望，不断进取，就能成功！
人生，又是一个大队列的实现，春夏秋冬年复一年，改变的是时间，不变的是你对未来的执念。

队列

队列的链试存储结构

队列的顺序存储结构

猜你喜欢

热点阅读