@songpfei 2016-03-30T14:28:56.000000Z 字数 4932 阅读 1387

队列

数据结构

1. 队列的定义

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
是一种先进先出（FIFO—first in first out）线性表。

2. 队列的分类

2.1 顺序队列

2.1.1 顺序队列的概念

建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置。

每次在队尾插入一个元素是，rear增1；每次哎队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。

顺序队列中的溢出现象：
（1） "下溢"现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
（2）"真上溢"现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
（3）"假上溢"现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。

参照：http://student.zjzk.cn/course_ware/data_structure/web/zhanhuoduilie/zhanhuoduilie3.2.2.1.htm

2.1.2顺序队列的c语言实现

队列有下面几个操作：

InitQueue（）　　 ——初始化队列
EnQueue（） ——进队列
DeQueue（） ——出队列
IsQueueEmpty（） ——判断队列是否为空
IsQueueFull（） ——判断队列是否已满
队列可以由数组和链表两种形式实现队列操作（c语言）

顺序队列的数组实现

#ifndef _QUEUE_H
#define _QUEUE_H
#ifdef __cplusplus
extern "C"{
#endif
#define ElementType int
    typedef struct tagQueue
    {
        int capacity;
        int front;
        int rear;
        ElementType* array;
    }Queue;
    Queue* CreatQueue(int max_elements);
    bool IsQueueEmpty(Queue* q);
    bool IsQueueFull(Queue* q);
    void EnQueue(Queue* q, ElementType val);
    ElementType DeQueue(Queue* q);
    void DistroyQueue(Queue* q);
#ifdef __cplusplus
}
#endif
#endif

#include"queue.h"
#include<stdlib.h>
#include<stdio.h>
Queue* CreatQueue(int max_elements)
{
    Queue *q = (Queue*)malloc(sizeof(Queue));
    if (q == NULL)
    {
        printf("Queue Memory allocation failure\n");
        exit(-1);
    }
    q->array = (ElementType*)malloc(sizeof(ElementType)*max_elements);
    if (q->array == NULL)
    {
        printf("q->array Memory allocation failure\n");
        exit(-1);
    }
    q->capacity = max_elements;
    q->front = 0;
    q->rear = 0;
    return q;
}
bool IsQueueEmpty(Queue* q)
{
    if (q->front == q->rear)
        return true;
    return false;
}
bool IsQueueFull(Queue* q)
{
    if (q->rear >= q->capacity)
        return true;
    return false;
}
void EnQueue(Queue* q, ElementType val)
{
    if (IsQueueFull(q))
    {
        printf("queue is full.");
        exit(-1);
    }
    q->array[q->rear] = val;
    q->rear++;
}
ElementType DeQueue(Queue* q)
{
    if (IsQueueEmpty(q))
    {
        printf("queue is empty.");
        exit(-1);
    }
    q->front++;
    return q->array[q->front - 1];
}
void DistroyQueue(Queue* q)
{
    if (q != NULL)
    {
        if (q->array != NULL)
            free(q->array);
        free(q);
    }
}

// test.cpp : 定义控制台应用程序的入口点。
//
#include"queue.h"
#include<stdio.h>
int main()
{
    Queue* q= CreatQueue(3);
    EnQueue(q, 10);
    EnQueue(q, 9);
    EnQueue(q, 8);
    printf("%d\n", DeQueue(q));
    printf("%d\n", DeQueue(q));
    printf("%d\n", DeQueue(q));
    DistroyQueue(q);
    return 0;
}

2.2 循环队列

2.2.1 概念

在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。处了一些简单应用之外，真正实用的队列时循环队列。
在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%MaxSize。

2.2.2 循环队列的C语言实现

2.3 队列的链表实现

#ifndef _QUEUE_H
#define _QUEUE_H
#ifdef __cplusplus
extern "C"{
#endif
    typedef  int ElementType;
    typedef struct tagListNode
    {
        ElementType element;
        struct tagListNode*  pNextNode;
    }ListNode;
    typedef struct tagQueue
    {
        ListNode* front;
        ListNode* rear;
    }Queue;
    Queue* CreatQueue();
    bool IsQueueEmpty(Queue* q);
    void EnQueue(Queue* q, ElementType val);
    ElementType Front(Queue* q);
    void DeQueue(Queue* q);
    void DistroyQueue(Queue* q);
#ifdef __cplusplus
}
#endif
#endif

#include"queue.h"
#include<stdlib.h>
#include<stdio.h>
#define FatalError(str)  fprintf(stderr,"%s\n",str),exit(1)
Queue* CreatQueue()//建立一个空队列
{
    Queue *q = (Queue*)malloc(sizeof(Queue));
    if (q == NULL)
        FatalError("Queue Memory allocation failure");
    q->front =q->rear = NULL;
    return q;
}
bool IsQueueEmpty(Queue* q)
{
    return q->front==NULL;
}
void EnQueue(Queue* q, ElementType val)
{
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if (node==NULL)
        FatalError("List Node Memory allocation failure");
    node->element = val;
    node->pNextNode = NULL;
    if (IsQueueEmpty(q))
        q->front = node;//将节点插入空队列
    else
        q->rear->pNextNode = node;//链到原队尾节点后
    q->rear = node;//队尾指针指向新的尾
}
void DeQueue(Queue* q)
{
    if (IsQueueEmpty(q))
      FatalError("queue is empty.");
    ListNode* node = q->front;
    q->front = node->pNextNode;
    if (q->rear == node)//原队列只有一个节点
        q->rear = NULL;
    free(node);
}
ElementType Front(Queue* q)
{
    if (IsQueueEmpty(q))
        FatalError("queue is empty.");
    return q->front->element;
}
void DistroyQueue(Queue* q)
{
    if (q != NULL)
    {
        while(!IsQueueEmpty(q))
            DeQueue(q);
        free(q);
    }
}`此处输入代码`

// huawei_test.cpp : 定义控制台应用程序的入口点。
//
#include"queue.h"
#include<stdio.h>
int main()
{
    Queue* q= CreatQueue();
    EnQueue(q, 10);
    EnQueue(q, 9);
    EnQueue(q, 8);
    printf("%d\n", Front(q));
    DeQueue(q);
    printf("%d\n", Front(q));
    DeQueue(q);
    printf("%d\n", Front(q));
    DeQueue(q);
    DeQueue(q);
    DistroyQueue(q);
    return 0;
}

3. 队列的STL实现

queue
queue模板类的定义在头文件中。

与stack模板类很相似，queue模板类也需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为deque类型。

定义queue对象的示例代码如下：

queue q1;

queue q2;

queue的基本操作有：

入队，如例：q.push(x); 将x接到队列的末端。

出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。

访问队首元素，如例：q.front()，即最早被压入队列的元素。

访问队尾元素，如例：q.back()，即最后被压入队列的元素。

判断队列空，如例：q.empty()，当队列空时，返回true。

访问队列中的元素个数，如例：q.size()

4. 优先队列

4.1 定义：

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出（largest-in，first-out）的行为特征。