队列

循环队列解决了单向队列占用太大空间问题,

循环队列

f 和t 分别为尾指针和头指针

元素入队


当(t+1)%len=f时,视为队满,那么如果此时将t=(t+1)%len,这样t又回到队首;

元素出队


元素进队

元素出队

由上可知
– 当t=f时队为空,
– 当(t+1)%len=f时为队满(损失一个空间)

    void myqueue::InitQueue(int l)
    {
        len_=l;
        space_ =new int[l];
    }
    void myqueue::enQueue(int data)
    {
        space_[rear_]=data;
        rear_=(rear_+1)%len_;
    }
    int myqueue::ExQueue()
    {
        int data=space_[front_];
        front_=(front_+1)%len_;
        return data;
    }
    bool myqueue::IsQueueEmpty()
    {
        return rear_==front_;

    }
    bool myqueue::IsQueueFull()
    {
        return (rear_+1)%len_==front_;
    }

队的链式表达

队的链式表达这不用事先给队设置大小,通过链表实现;

初始化

元素入队

元素出队

void Queuelist::InitQueue()
{
    Node *h=new Node;

    front_=rear_=h;
    h->next=nullptr;
}
void Queuelist::enQueue(int data)//尾插法
{
    Node *cur=new Node;
    cur->data=data;
    rear_->next=cur;
    rear_=cur;
}
int Queuelist:: ExQueue()//出队
{
    int q=front_->next->data;

    if(front_->next==rear_)//只剩一个元素情况
    {

        Node *t=front_;
        front_=rear_;
        delete t;
        front_->next=nullptr;
        return q;
    }
    else
    {
        front_=front_->next;
        return q;
    }

}
bool Queuelist::IsQueueEmpty()
{
return front_==rear_;
}

队列的应用

因为栈是先进先出,所以在连续进几个元素(A,B)时,栈具有长期记忆,只要后面有元素c进栈,那么在同时进几个元素(A,B)的那一次,总有最后一个元素B被被长期记录下来,这样可以用于深度搜索(一条路走到底,走不通,在回到被记一下来的地方走下一条路)


栈会沿着星星路一直走下去
因为队列是先进先出,所以在连续进几个元素(A,B)时,栈具有短期记忆,只要后面有元素c进栈,A出去了就会出B,这样可以用于广度搜索(几条路同时搜索)

队列会2条路同时走。

Leave a Reply