循环队列解决了单向队列占用太大空间问题,
循环队列
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条路同时走。