Level4题解（1-10）

  2. 主页
  4. 文档
  6. Level4题解（1-10）
  8. 第3课 队列

第3课 队列

队列是一种操作（或者说运算）受到限制的特殊线性表。其插入操作限定在表的一端进行，称为“入队”；其删除操作则限定在表的另一端进行，称为“出队”。插入一端称为队尾（rear/tail）；删除一端称为队头（front）。

队列也被称作“先进先出”线性表（FIFO，First In First Out）。类似于生活中排队购票，先来先买，后来后买。在不断入队、出队的过程中，队列将会呈现出以下几种状态：

  • 队空：队列中没有任何元素。
  • 队满：队列空间已全被占用。
  • 溢出：当队列已满，却还有元素要入队，就会出现“上溢（overflow）”；当队列已空，却还要做“出队”操作，就会出现“下溢（underflow）”。两种情况合在一起称为队列的“溢出”

存储方式

  • 顺序存储 – 静态顺序队列
  • 链式存储 – 动态顺序队列

静态队列

随着入队与出队操作的不断进行，队头指针在数组中不断向队尾方向移动，而在队头前面产生了一片不能利用的“空闲区”，当队尾指针指向数组最后一个位置，即tail = N时，如果再有元素入队就会出现“溢出”，这种溢出称作“假溢出”。如何解决这种情况呢？一种方法是每次出队操作时，都向“空闲区”整体移动一位，带来的后果是时间复杂度高了；另一种方法是让数组首尾相连，形成“环”状，即所谓的“循环队列”。

循环队列

循环队列初始时，front = tail = 0，如果 maxn 个元素一个个依次入队，则 tail = maxn，此时再有元素入队，则它会被存放在 q[0] 这个单元，也会出现 front = tail = 0，与队空时的状态一样。解决方法是少用一个元素空间，约定数据入队前，测试“队尾指针在循环意义下加 1 后是否等于头指针”作为判断“队满”的条件。循环队列的实际长度为 (tail – front + maxn) % maxn。

数组模拟队列

  • 规定
  1. 为了简单, 队头 head 用 hh, 队尾 tail 用 tt
  2. 为了代码写起来简单, 没有使用取模方式
  • 初始化
const int N = 666;
int hh, tt;
int q[N + 6];
  • 空
hh  == tt;
  • 满
int thh = hh + 1;
if (thh == N) thh = 1;
if(thh == tt)
    full;
  • 入队
q[++tt] = x;
if(tt == N) tt = 1;
  • 出队
int data = q[++hh];
if(hh == N)
    hh = 1;

例题 1 P1996 约瑟夫问题

题目描述

n 个人围成一圈，从第一个人开始报数,数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

输入格式

输入两个整数 n,m。

输出格式

输出一行 n 个整数，按顺序输出每个出圈人的编号。

输入输出样例

  • 输入 #1复制

10 3

  • 输出 #1复制

3 6 9 2 7 1 8 5 10 4

说明/提示

分析

  1. 第一种实现: 数组存放, 标记数组显示是否出圈
  2. 第二种实现: 排成一圈, 正好是循环链表的样子 … 然后不断的删除就可以.
  3. 第三种实现: 把他们从圆桌里拉出, 放入队列里排队, 第m个人禁止入队, 如此循环

参考代码

#include<iostream>
#include<queue>
using namespace std;

const int N = 108; // 队列足够大, 无需判断是否满
int n, m, cnt;
int q[N + 2];
int hh /* 队头 */, tt /* 队尾 */;

int main()
{
 cin >> n >> m;

 for(int i = 1; i <= n; i++)
 {
  q[++tt] = i;
 }

 cnt = 0;
 while(hh != tt)
 {
  int x = q[++hh];
  if(hh == N) hh = 1;
  cnt++;
  if(cnt == m) {
   cout << x <<" ";
   cnt = 0;
  }
  else {
   q[++tt] = x;
   if(tt == N) tt = 1;
  }
 }
 return 0;
}

STL- queue

queue 翻译为队列，是 STL 中实现的一个“先进先出”的容器，只能通过函数 front ()来访问队首元素，或通过函数 back()来访问队尾元素。

  • 头文件 #include
  • 队列定义
#include <queue>
using namespace std;
queue<int> myq;
  • push()

push(x)用来将 x 入队，时间复杂度为 0(1)。

  • front ()和 back()

front ()和 back()分别用来获得队首元素和队尾元素，时间复杂度为 0(1)。

  • pop() pop()用来让队首元素出队，时间复杂度为 0(1)。
  • empty()

empty()用来检测 queue 是否为空，返回 true 或者 false，时间复杂度为 0(1)。

  • size()

size()返回 queue 内元素的个数，时间复杂度为 0(1)。

例题 2 UVA10935 卡片游戏 Throwing cards away I

题意翻译

桌子上有n张牌，从第一张牌（即位于牌面的牌）开始，从上往下一次编号为1~n。当剩下两张牌多于两张时进行一下操作：把第一张牌扔掉，然后把新的第一张牌放到整叠牌的最后。当还剩下一张牌的时候，停止操作。n<=50

这题的输出要注意:逗号后面有空格，冒号后面没有空格。

当n=1的时候，应该输出Discarded cards:（此处没有空格）Remaining card: 1（有空格）

输入输出样例

  • 输入
7
19
10
6
0
  • 输出
Discarded cards: 1, 3, 5, 7, 4, 2
Remaining card: 6
Discarded cards: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 4, 8, 12, 16, 2, 10, 18, 14
Remaining card: 6
Discarded cards: 1, 3, 5, 7, 9, 2, 6, 10, 8
Remaining card: 4
Discarded cards: 1, 3, 5, 2, 6
Remaining card: 4

分析

以前用链表实现过类似的功能, 这里我们用队列实现.

  1. STL queue的使用
  2. 怎么实现第二张牌移动到最后
  3. 怎么解决没有空格的问题

参考代码

#include<string>
#include<iostream>
#include<queue>
using namespace std;

int n;

int main()
{
 while(cin>>n){
  if(n == 0)
   break;
  queue<int> q;
  for(int i = 1; i<= n; i++) {
   q.push(i);
  }

  cout << "Discarded cards:";
  bool flag = true;
  while(q.size() >= 2) {
   int x = q.front(); q.pop();
   if(flag == true) {
    cout <<" " << x;
    flag = false;
   }
   else {
    cout<<", "<< x;
   }
   q.push(q.front());
   q.pop();
  }
  cout << endl;
  cout << "Remaining card: "<< q.front() << endl;
 }
 return 0;
}

题单

  • P1996 约瑟夫问题
  • P1540 机器翻译
  • CF266B Queue at the School
  • UVA10935 卡片游戏 Throwing cards away I
  • P1160 队列安排

文章