队列

ADT

Note

ADT 队列(queue) Data

queue是一种先进先出(First In First Out,FIFO)的数据结构,他只有一个出口 队列只有队头队尾才能被外界使用，不允许遍历

Operation

push():入队 pop():出队 front():返回队列首元素 back():返回队列尾元素 isemtpy():是否为空 size():返回元素个数

endADT

具体实现

队列体

• 数组队列

typedef struct queue
{
    int front;
    int rear;
    elem Queue_data[NUMBER];
}Queue;

• 链表队列(循环队列)

typedef struct queue
{
    int front;
    elem data;
    elem* next;
}Queue;

初始化

void InitQueue(Queue* q)
{
    q->front = 0;
    q->rear = 0;
    q->data = {NULL};
    //S->next = NULL;
}

出入队列

• 出队列

elem front(Queue* q)//DeQueue
{
    if(q->rear = q->front)
    {
        printf("overflow");
        return;
    }
    
    int x = q->data[q->front];
    q->front = (q->front + 1) % NUMBER;/*循环队列*/
    return x;
}

• 入队列

void pop(Queue* q, elem data)//EnQueue
{
    if(q->rear = q->front)
    {
        printf("overflow");
        return;
    }
    q->data[q->rear] = data;
    q->rear = (q->rear + 1) % NUMBER;/*循环队列*/
}

返回队列元素

int front(Queue* q)
{
    return q->data[q->front];
}

是否为空

bool isEmpty(Queue* q)
{
    if(q->front == q->rear)
    {
        return true;
    }
    return false;
}

元素个数

(rear + maxsize - front) % maxsize