队列
- 一、关于队列
- 1. 特点
- 2. 意义
- 3. 基本操作
- (1) 初始化
- (2) 入队
- (3) 出队
- (4) 获取队头、队尾元素
- (5) 获取队列长度
- (6) 判断队列是否为空
- (7) 判断队列是否满出
- 4. 队列 VS 栈
- 二、入栈和出栈
- 三、P1540 NOIP2010 提高组 机器翻译
- 1. 审题
- 2. 思路
- 3. 参考答案
- 四、P1996 约瑟夫环问题
- 1. 审题
- 2. 参考答案
- 2.1 初始思路
- 2.2 循环队列
- 五、总结
一、关于队列
1. 特点
先进先出（
First In First Out，简称FIFO），后进后出。
遵循左闭右开（[head,tail)）原则。
就像排队一样，排在队首的人可以最先享受到服务；反之，排在队尾的人要最后才能享受到服务。
2. 意义
队列是一种先入先出的线性数据结构，只允许元素从一段插入。
3. 基本操作
(1) 初始化
const int n = 105;
int que[n] = {}; // 数组模拟
int head = 0; // 队头指针
int tail = 0; // 队尾指针
(2) 入队
void push()
{
que[tail++] = x;
}
(3) 出队
void pop()
{
head++;
}
(4) 获取队头、队尾元素
void getHead()
{
return que[head];
}
void getTail()
{
return que[tail-1];
}
(5) 获取队列长度
void getLength()
{
return tail-head;
}
(6) 判断队列是否为空
bool isEmpty()
{
return (h == t);
// 或者:
// return (t - h == 0);
}
(7) 判断队列是否满出
bool isFull()
{
return (t >= n);
// 或者:
return (t - h >= n);
}
4. 队列 VS 栈
顺序
队列是先进先出的数据结构，最先插入的元素最先被删除。
栈是是后进先出的数据结构，最后插入的元素最先被删除。实现方法
都是使用数组。
位置
队列的插入操作在队尾进行，删除操作在队首进行。
栈的插入和删除操作都在栈顶进行。
二、入栈和出栈
#include <iostream>
#include <string>
using namespace std;
int que[105] = {};
int head;
int tail;
int n;
int x;
string s;
int main()
{
// 输入指令条数
cin >> n;
while (n--)
{
// 输入指令
cin >> s;
// 入队
if (s == "ENQUEUE")
{
cin >> x;
que[tail++] = x;
}
// 出队
else
{
head++;
}
cout << "Now Queue:";
// 遍历队列
for (int i = head; i <= tail-1; i++)
{
cout << " " << que[i];
}
cout << endl;
}
return 0;
}
三、P1540 NOIP2010 提高组 机器翻译
1. 审题
题目描述
这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。
假设内存中有 M M M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 M − 1 M-1 M−1，软件会将新单词存入一个未使用的内存单元；若内存中已存入 M M M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。
假设一篇英语文章的长度为 N N N 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。
输入格式
共 2 2 2 行。每行中两个数之间用一个空格隔开。
第一行为两个正整数 M , N M,N M,N，代表内存容量和文章的长度。
第二行为 N N N 个非负整数，按照文章的顺序，每个数（大小不超过 1000 1000 1000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。
输出格式
一个整数，为软件需要查词典的次数。
输入输出样例
样例输入
3 7 1 2 1 5 4 4 1样例输出
5
提示
整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：
- 1：查找单词 1 并调入内存。
- 1 2：查找单词 2 并调入内存。
- 1 2：在内存中找到单词 1。
- 1 2 5：查找单词 5 并调入内存。
- 2 5 4：查找单词 4 并调入内存替代单词 1。
- 2 5 4：在内存中找到单词 4。
- 5 4 1：查找单词 1 并调入内存替代单词 2。
共计查了 5 5 5 次词典。
2. 思路
3. 参考答案
#include <iostream>
#include <cstdio>
using namespace std;
int que[1005];
bool a[1005];
int head;
int tail;
int N, M;
int ans;
int x;
int main()
{
freopen("tran.in", "r", stdin);
freopen("tran.out", "w", stdout);
cin >> M >> N;
while (N--)
{
cin >> x;
if (a[x] == false)
{
ans++;
if (tail - head == M) // 判断内存是否满出
{
a[que[head]] = false;
head++;
}
que[tail++] = x;
a[x] = true;
}
}
cout << ans;
fclose(stdin);
fclose(stdout);
return 0;
}
四、P1996 约瑟夫环问题
1. 审题
n n n 个人围成一个圆圈，由第 1 1 1 个人开始报数，每报数到第 m m m 人该人就出圈，然后再由下一个重新报数，直到所有人都出圈为止。依次输出出圈人的编号。
2. 参考答案
2.1 初始思路
#include <iostream>
using namespace std;
int que[10005];
int head;
int tail;
int n, m;
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
que[tail++] = i; // n个人入队
}
while (n--)
{
// 1~m-1个人向后移
for (int i = 1; i <= m-1; i++)
{
que[tail++] = que[head++];
}
// 队首出队
cout << que[head++] << " ";