队列
队列简介
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(
front
)进行删除操作,而在表的后端(rear
)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。是一种先进先出的数据结构
队列就像排队一样,前面先到的人会先离开,后进去的人会后离开。
上课没带数位板,用鼠标画的,凑合着看吧…
队列的实现
知道了队列是什么,现在来实现队列吧~
-
STL
队列
STL的队列大家可以在这里找到队列。
当然,我也把队列的部分复制到这里了,你也可以在这里看。
queue(队列)
定义::
queue <类型> 变量名;
常用函数::
size(); 这个队列的长度
empty(); 返回这个队列是否为空
push(); 往队尾插入一个元素
front(); 返回队头元素
back(); 返回队尾元素
pop(); 把队头弹出
注意:队列没有clear函数!!!
清空:
变量名 = queue <int> ();
-
手写队列
手写队列我也给大家整出来了,点稽进入。
然后把有注释的代码放在这里。
class Queue{
public:
int q[N],head = 0,tail = 0;
void init(){ // 创建,初始化
tail = -1;
}
void push(int x){ // 往队列里插一个数(从最后)
q[++ tail] = x;
}
void pop(){ // 弹出队顶
head ++;
}
int find(int x){ // 查找一个数
for(int i = head;i <= tail;i ++){
if(q[i] == x) return i;
}
return -1;
}
int size(){ // 队列长度
return tail - head + 1;
}
int query(){ // 返回队顶
return q[head];
}
int seek(int x){ // 返回队列中编号为x的数
return q[x];
}
int min_value(){ // 找最小值
int minn = 0x3f3f3f3f;
for(int i = head;i <= tail;i ++){
minn = min(minn,q[i]);
}
return minn;
}
int max_value(){ // 找最大值
int maxx = -0x3f3f3f3f;
for(int i = head;i <= tail;i ++){
maxx = max(maxx,q[i]);
}
return maxx;
}
};
关于队列例题
比较简单的一道题,可以用来练练手
相比第一道,会更难一点,可以用来提升水平