Shen Huang's Blog
0%

14级集训队讨论会2--Stack and Queue

Posted on Edited on

问题1

四月一日快到了，Vayko想了个愚人的好办法——送礼物。嘿嘿，不要想的太好，这礼物可没那么简单，Vayko为了愚人，准备了一堆盒子，其中有一个盒子里面装了礼物。盒子里面可以再放零个或者多个盒子。假设放礼物的盒子里不再放其他盒子。

输入

((((B)()))())

(B)

输出

4

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
int main(int argc, char const *argv[])
{
    char c[1111];
    while (~scanf("%s", c)){
        stack <int> st;
        while (!st.empty()) st.pop();
        for (int i = 0; i < strlen(c); i ++){
            if (c[i] == '('){
                st.push(1);
            }else if (c[i] == ')'){
                st.pop();
            }else {
                printf("%dn", st.size());
                break;
            }
        }
    }
    return 0;
}

栈的定义

栈和队列一个先进后出，一个先进先出。 堆栈（英语：stack），也可直接称栈。它的特殊之处在于只能允许在链结串列或阵列的一端（称为堆栈顶端指标，英语：top）进行加入资料（英语：push）和输出资料（英语：pop）的运算。另外堆叠也可以用一维阵列或连结串列的形式来完成。 由于堆栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。 堆叠数据结构使用两种基本操作：推入（push）和弹出（pop）： 推入：将数据放入堆栈的顶端（阵列形式或串列形式），堆栈顶端top指标加一。 弹出：将顶端数据资料输出（回传），堆栈顶端资料减一。

- stack<INT</span> s；定义一个INT类型的栈s，也可以定义结构体的类型的。 </span>

- s.empty()判断栈是否是空的，是空的就返回真，不然就是假，所以这个是常常用在if和while里面。 </span>

- s.top()返回栈顶元素，a=s.top()的话那么a就被赋值成栈顶元素了，只是返回，但不改变栈里面的内容，也就是没有删除栈顶元素。</span>

- s.pop()用来删除栈顶元素的，没有返回值，不能对空栈使用。 </span>-</span>

s.size()返回栈里面有多少元素，就是用来确定栈里面的元素数量的。

- s.push()进栈的函数，s.push(a)。</span>

队列定义

队列（queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。 队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

- queue<INT</span> q;这里的INT和栈一样的。</span>

- q.empty(); q.pop(); q.size(); q.push(); </span>

- q.back(); q.front();这两个是队列的的返回方式，back是返回的队尾的元素，front是返回的队首的元素。</span>

手动实现一下栈和队列（数组或者链表）

问题2

某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数。。。，以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。

输入 </span>

2

20

40

输出 </span>

1 7 19

1 19 37