队列

队列的定义

队列简称队，是一种受限制的线性表，仅允许在表的一端插入，在表的另一端进行删除。

• 进行插入的一端叫做队头
• 进行删除的一端叫做队尾

队的特点

• 先进先出(FIFO)

顺序队（循环队列）

顺序队主要以循环队列的形式出现

循环队列的要素

• 队空状态 qu.rear == qu.front
• 队满状态 (qu.rear+1)%MAXSIZE == qu.front

结构体定义

#define MAXSIZE 1024

typedef struct _Queue
{
    int data[MAXSIZE];  //数据
    int front;  //队首指针
    int rear;   //队尾指针
}SqQueue;

操作

采用 p = (p+1)%MAXSIZE;而不是p++的方式移动指针是为了能保证循环再利用性，使其在超过MAXSIZE后能重新回到原始位置

否则一个队只存满再全部取出后就不能再利用了

初始化

//初始化循环队列
void initQueue(SqQueue &qu)
{
    qu.front = qu.rear = 0;
}

判断队空

//判断队空
//队空返回真，否则返回假
bool isQueueEmpty(SqQueue qu)
{
    if(qu.front == qu.rear) return true;
    else return false;
}

判断队满

//判断队满
//队满返回真，否则假
bool isQueueFull(SqQueue qu)
{
    if((qu.rear + 1) % MAXSIZE == qu.front)
        return true;
    else
        return false;
}

进队

//进队
bool enQueue(SqQueue &qu, int e)
{
    //判断队满
    if(isQueueFull(qu)) return false;
    //若未满，先移动尾指针再存元素
    qu.rear = (qu.rear + 1) % MAXSIZE;
    qu.data[qu.rear] = e;

    return true;
}

出队

//出队
bool deQueue(SqQueue &qu, int &e)
{
    //判断队空
    if(isQueueEmpty(qu)) return false;
    //若不为空，则先移动头指针(因为等于0的时候并无元素，所以可以先移动指针)
    qu.front = (qu.front + 1) % MAXSIZE;
    e = qu.data[qu.front];

    return true;
}

链队

链队的要素

• 队空状态 lqu->rear == NULL 或 lqu->front == NULL
• 队满状态不存在（假设内存无限大）

结构体定义

//储存数据的链队结点
typedef struct QNode
{
    int data;   //数据域
    struct QNode *next; //指针域
}QNode;

//头结点定义，用于指示队头和队尾
typedef struct _LiQueue
{
    QNode *front;
    QNode *rear;
}LiQueue;

操作

初始化

//初始化
bool initQueue(LiQueue* &lqu)
{
    lqu = new LiQueue;
    if(!lqu) return false;

    lqu->front = lqu->rear = NULL;

    return true;
}

判断队空

//判断队空，队空返回真，否则假
bool isQueueEmpty(LiQueue *lqu)
{
    if(!lqu->rear || !lqu->front)
        return true;
    else
        return false;
}

进队

//入队
bool enQueue(LiQueue* &lqu, int e)
{
    QNode *node = new QNode;
    if(!node) return false;

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

    //若队为空，则新结点即时队首结点又是队尾结点
    if(!lqu->rear)
        lqu->rear = lqu->front = node;
    else{
        lqu->rear->next = node;
        lqu->rear = node;
    }

    return true;
}

出队

//出队
bool deQueue(LiQueue* &lqu, int &e)
{
    QNode *p;

    //判断队空
    if(!lqu->rear) return false;
    else p = lqu->front;

    //当队中只有一个保存数据的结点时需特殊操作
    if(lqu->front == lqu->rear)
        lqu->rear = lqu->front = NULL;
    else
        lqu->front = lqu->front->next;

    e = p->data;
    delete p;

    return true;
}