37.2° Blog

1.概念

一种操作受限的线性表，只能在队尾插入元素，在队头删除元素

特性：先进先出（FIFO）

2.实现

2.1 实现思想

用静态数组存放数据元素，设置队头/队尾 (front/rear)指针

循环队列：用模运算（取余）将存储空间在逻辑上变为“环状”

Q.rear = (Q.rear + 1) % MaxSize

2.2 定义

typedef int ElemType;
#define MaxSize 50
typedef struct
{
    ElemType data[MaxSize]; // 存放栈中的数据
    int front;              // 队列头指针
    int rear;               // 队列尾指针
}SqQueue;

2.3 初始化

// Q.front == Q.rear == 0
void initQueue(SqQueue& Q)
{
    Q.rear = Q.front = 0;   // 初始化队首，队尾指针
}

2.4 入队

bool enQueue(SqQueue& Q, ElemType e)
{
    if((Q.rear + 1) % MaxSize == Q.front)   // 队满
        return false;
    Q.data[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MaxSize;        // 队尾指针加一取模
    return true;
}

2.5 出队

bool deQueue(SqQueue& Q, ElemType& e)
{
    if(Q.rear == Q.front)                   // 队空报错
        return false;
    e = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;      // 队头指针加1取模
    return true;
}

2.6 判空

bool queueEmpty(SqQueue Q)
{
    if(Q.rear == Q.front)   // 队空条件
        return true;  
    else
        return false;  
}

2.7 长度

int GetNumber(SqQueue Q)
{
    return (Q.rear + MaxSize - Q.front) % MaxSize;  // *****
}

2.8 获取队头元素

// 获得队头元素的值，用e返回
bool GetHead(SqQueue& Q, ElemType& e)
{
    if(Q.rear == Q.front)
        return false;
    e = Q.data[Q.front];
    return true;
}