杭州网站改版公司电话,注册网站怎么注册,公司企业邮箱号,远程教育网站建设方案目录 队列的概念
队列的静态实现
总代码 stl的queue
队列算法题
1.队列模板题
2.机器翻译
3.海港
双端队列 队列的概念
和栈一样#xff0c;队列也是一种访问受限的线性表#xff0c;它只能在表头位置删除#xff0c;在表尾位置插入#xff0c;队列是先进先出…目录 队列的概念
队列的静态实现
总代码 stl的queue
队列算法题
1.队列模板题
2.机器翻译
3.海港
双端队列 队列的概念
和栈一样队列也是一种访问受限的线性表它只能在表头位置删除在表尾位置插入队列是先进先出FIFO栈是后进先出LIFO
队列的静态实现
我们用一个比较大的数组来表示队列h表示队头的前一个元素t表示队尾元素
队列的创建
#include iostream
using namespace std;
const int N 1e5 10;
int q[N], h, t;
队列的插入
void push(int x)
{q[t] x;
}
和顺序表的尾插差不多时间复杂度是O1
队列的删除 我们的删除直接让头指针向前移动一位就行了 void pop()
{h;
}
查询队头元素 h指向的是队头的前一个元素的下标所以h1是队头的下标 int front()
{return q[h 1];
}
查询队尾元素
t就是队尾元素的下标
int back()
{return q[t];
}
队列判空 当我们只剩一个元素的时候h指向这个元素的前面t指向这个元素如果删除的话h h就和t相等了这和我们刚开始没有元素的状态也是一致的所以ht就是我们判断队列为空的要点 bool empty()
{return h t;
}
队列有效元素个数 由于我们h和t是左开右闭的所以t-h就是中间的元素个数比如h指向1t指向3的时候下标23就是我们的元素3-12就是元素个数是一致的 int size()
{return t - h;
}
测试
总代码
#include iostream
using namespace std;
const int N 1e5 10;
int q[N], h, t;
void push(int x)
{q[t] x;
}
void pop()
{h;
}
int front()
{return q[h 1];
}
int back()
{return q[t];
}
bool empty()
{return h t;
}
int size()
{return t - h;
}
int main()
{for (int i 1; i 10; i){push(i);}while (size()){cout front() back() endl;pop();}return 0;
} stl的queue
测试代码
#include iostream
#include queue
using namespace std;
typedef pairint, int PII;
int main()
{queue PII q;for (int i 1; i 10; i){q.push({ i,i * 10 });}while (!q.empty()){auto t q.front();int first t.first;int second t.second;cout first second endl;q.pop();}}
测试结果 队列算法题
1.队列模板题 #include iostream
using namespace std;
const int N 1e410;
int q[N],h,t;int main()
{int n,op,x;cin n;while(n--){cin op;if(op 1){cin x;q[t] x;}else if(op 2){if(t-h 0) cout ERR_CANNOT_POP endl;else h;}else if(op 3){if(t-h 0) cout ERR_CANNOT_QUERY endl;else cout q[h1] endl;}else{cout t-h endl;}}
}
2.机器翻译 我们可以用队列来模拟这个内存存储的单元格此外我们还需要一个bool数组来判断某个单词在不在内存中 下面是我们的实现的代码 #include iostream
#include queue
using namespace std;
const int N 1010;
bool st[N];
int cnt;
queue int q;
int main()
{int n,m;cin m n;while(n--){int x; cin x;if(st[x]);else{q.push(x);st[x] true;cnt;if(q.size() m){st[q.front()] false;q.pop();}}}cout cnt endl;
} 3.海港 这道题我们用队列来模拟我们用一个数组来记录每个国家的人数当每个国家从0变1时种类加1从1变0时种类减1 先把每个船的信息入队列用pair类型时间国家来入队列每次入队列判断种类是否加1 每个船的信息入完了之后要判断队列合不合法如果队头的时刻和队尾的时刻差值超过24小时我们就要把第一个时刻的信息出队列出队列的时候再次判断要不要让种类减1 每次一个信息弄完就打印一下种类 #include iostream
#include queue
using namespace std;
const int N 1e510;
typedef pairint,int PII;
int t,k;
int cnt[N];//记录每个国家的人数从0到1时种类加1从1到0时种类减1其他不变
int kinds;//记录国家种类
queue PII q;
int main()
{int n;cin n;while(n--){cin t k;while(k--){int x;cin x;q.push({t,x});if(cnt[x] 0){kinds;}}//让队列合法while(q.size() (q.back().first - q.front().first 86400)) {int tmp;tmp q.front().second;if(cnt[tmp]-- 1){kinds--;}q.pop();}cout kinds endl;} return 0;}
双端队列
什么是双端队列
双端队列也是一种特殊的线性表它允许在表的两端插入和删除元素
我们就不实现它的模拟实现了
我们直接用stl现成的双端队列deque测试一下
头插头删
#include iostream
#include deque
using namespace std;
struct node {int x, y, z;
};
deque node q;
int main()
{//头插和头删for (int i 1; i 5; i){q.push_front({ i,i * 5,i * 10 });}while (q.size()){auto t q.front();q.pop_front();cout t.x t.y t.z endl;}
} 同理尾插和尾删
#include iostream
#include deque
using namespace std;
struct node {int x, y, z;
};
deque node q;
int main()
{//尾插和尾删for (int i 1; i 5; i){q.push_back({ i,i * 5,i * 10 });}while (q.size()){auto t q.back();q.pop_back();cout t.x t.y t.z endl;}
}
