数据结构 (队列略版)
模拟队列
const int N=10010;
int q[N];
int fro=0,tail=0;
void push(int val){
q[tail++]=val;
}
void pop(){
if(fro==tail)return;
fro++;
}
int front(){
if(fro==tail)return -1;
return q[fro];
}
bool empty(){
return tail==front;
}
int size (){
return tail-fro;
}
环形队列:
方案1:
加一个变量
count
保存队列元素个数
✓
初始
：
front=0,rear=0,count=0;
✓
队空
：
count==0
✓
队满
：
count==m
✓
队中元素个数
：
count
➢
优点
✓
队列每个空间都能用上
➢
缺点
✓
多了一个变量
✓
入队、出队需要对
count
加减
1
方案2:
队尾后一个位置永远空着
✓
初始
：
front=0,rear=0;
✓
队空
：
front==rear
✓
队满
：
(rear+1)%m==front
✓
队中元素个数：(rear-front+m)%m
➢
优点
✓
不需要
count
变量
✓
入出队也无需对
count
加减
1
➢
缺点
✓
浪费
1
个空间
题目;
1,模拟排队
有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。
给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。
每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到 队尾 重新排队（**瞬间 **发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。
返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。
**示例 1：**输入：tickets = [2,3,2], k = 2 输出：6 解释： - 第一轮，队伍中的每个人都买到一张票，队伍变为 [1, 2, 1] 。 - 第二轮，队伍中的每个都又都买到一张票，队伍变为 [0, 1, 0] 。 位置 2 的人成功买到 2 张票，用掉 3 + 3 = 6 秒。
int timeRequiredToBuy(vector<int>& tickets, int k) {
int n = tickets.size();
int res = 0;
for (int i = 0; i < n; ++i){
// 遍历计算每个人所需时间
if (i <= k){
res += min(tickets[i], tickets[k]);
}
else{
res += min(tickets[i], tickets[k] - 1);
}
}
return res;
}