数据结构-队列

队列

• 队列是只允许在一端进行插入，而在另一端进行删除的线性表
• 队头（Front）：允许删除的一端，又称为队首。
• 队尾（Rear）： 允许插入的一端。
• 先进入队列的元素必然先离开队列，即先进先出（First In First Out）简称FIFO

• 顺序队列

  • 用数组来实现队列，可以将队首放在数组下标为0的位置。

• 循环队列

  • 把数组“掰弯”，形成一个环。Rear指针到了下标为4的位置还能继续指回到下标为0的地方。这样首尾相连的顺序存储的队列就叫循环队列
  • 入队：rear=(rear+1)%MaxSize
  • 出队：front=(front+1)%MaxSize

  • 循环队列的操作

    • 1.入队：
    • 2.出队：

  • 概要: 那如何分辨队列是空还是满呢？

    • 方法一：设置标志位flag，当flag=0且rear等于front时为队列空，当flag=1且rear等于front时为队列满。
    • 方法二：我们把front=rear仅作为队空的判定条件。当队列满的时候，令数组中仍然保留一个空余单元。我们认为这种情况就是队列满了。

• 链式队列

  • 队列的链式存储结构，其实就是线性表的单链表，只不过需要加点限制，只能表尾插入元素，表头删除元素。
  • 为了方便操作，我们分别设置队头指针和队尾指针，队头指针指向头结点，队尾指针指向尾结点。

  • 链式队列的操作

    • 1.入队：我们知道队列只能从队尾插入元素，队头删除元素。于是入队就是在队尾指针进行插入结点操作。链队的插入操作和单链表的插入操作是一致的。
    • 2.出队：出队就是头结点的后继结点出队，然后将头结点的后继改为它后面的结点。

• 双端队列

  • 双端队列是指允许两端都可以进行入队和出队操作的队列

基本操作

Status InitQueue_CSq(CSqQueue *Q)
{
    (*Q).base = (QElemType_CSq *)malloc(MAXQSIZE*sizeof(QElemType_CSq));
    if(!(*Q).base)
        exit(OVERFLOW);

    (*Q).front = (*Q).rear = 0;

    return OK;
}

void ClearQueue_CSq(CSqQueue *Q)
{
    (*Q).front = (*Q).rear = 0;
}

void DestroyQueue_CSq(CSqQueue *Q)
{
    if((*Q).base)
        free((*Q).base);
        
    (*Q).base = NULL;
    (*Q).front = (*Q).rear = 0;
}

Status QueueEmpty_CSq(CSqQueue Q)
{
    if(Q.front==Q.rear)                         //队列空的标志
        return TRUE;
    else
        return FALSE;
}

int QueueLength_CSq(CSqQueue Q)
{
    return (Q.rear-Q.front+MAXQSIZE) % MAXQSIZE;//队列长度 
}

Status GetHead_CSq(CSqQueue Q, QElemType_CSq *e)
{
    if(Q.front==Q.rear)                            //队列空
        return ERROR;
        
    *e = Q.base[Q.front];
    
    return OK;
}

Status EnQueue_CSq(CSqQueue *Q, QElemType_CSq e)
{
    if(((*Q).rear+1)%MAXQSIZE == (*Q).front)    //队列满
        return ERROR;
        
    (*Q).base[(*Q).rear] = e;
    (*Q).rear = ((*Q).rear+1)%MAXQSIZE;
    
    return OK;
}

Status DeQueue_CSq(CSqQueue *Q, QElemType_CSq *e)
{
    if((*Q).front==(*Q).rear)                    //队列空
        return ERROR;
        
    *e = (*Q).base[(*Q).front];
    (*Q).front = ((*Q).front+1)%MAXQSIZE;
    
    return OK;
}

void QueueTraverse_CSq(CSqQueue Q, void(Visit)(QElemType_CSq))
{
    int i = Q.front;
    
    while(i!=Q.rear)
    {
        Visit(Q.base[i]);
        i = (i+1)%MAXQSIZE;
    }
}