2015-11-06 11:31:53 Novemser 阅读数 1586

Description
Figure 1 shows the structure of a station for train dispatching.

Figure 1

In this station, A is the entrance for each train and B is the exit. S is the transfer end. All single tracks are one-way, which means that the train can enter the station from A to S, and pull out from S to B. Note that the overtaking is not allowed. Because the compartments can reside in S, the order that they pull out at B may differ from that they enter at A. However, because of the limited capacity of S, no more that m compartments can reside at S simultaneously.

Assume that a train consist of n compartments labeled {1, 2, …, n}. A dispatcher wants to know whether these compartments can pull out at B in the order of {a1, a2, …, an} (a sequence). If can, in what order he should operate it?

Input
Two lines:

1st line: two integers n and m;

2nd line: n integers separated by spaces, which is a permutation of {1, 2, …, n}. This is a compartment sequence that is to be judged regarding the feasibility.

Output
If the sequence is feasible, output the sequence. “Push” means one compartment goes from A to S, while “pop” means one compartment goes from S to B. Each operation takes up one line.

If the sequence is infeasible, output a “no”.

Example 1
Input

5 2
1 2 3 5 4
Output

push
pop
push
pop
push
pop
push
push
pop
pop
Example 2
Input

5 5
3 1 2 4 5
Output

No
Restrictions
1 <= n <= 1,600,000

0 <= m <= 1,600,000

Time: 2 sec

Memory: 256 MB

95分代码

#include <cstdio>
#include <cstring>
int out[1600010];
char print[3200010][5];
int stack[1600010];

void push( int n )
{
}

int top()
{
}

int pop()
{
}

int main()
{
int m, n;
int op = 0;
scanf( "%d%d", &n, &m );

int i;
for (i = 1; i <= n; i++)
scanf( "%d", &out[i] );
int j = 1;
i = 1;
while (i <= n)
{
if (j <= n && sHead <= m && out[i] >= j)
{
push( j++ );
strcpy( print[op++], "push" );
}
else
{
if (out[i] == top())
{
pop();
strcpy( print[op++], "pop" );
i++;
}
else
{
puts( "No" );
return 0;
}
}
}

for (int k = 0; k < op; k++)
{
puts( print[k] );
}
}

2016-09-07 22:49:23 Robot__Man 阅读数 7232

## 1.1 数据结构的逻辑结构

1、集合结构：这种结构表示数据可以合并成一个整体。
这是数据之间关系最弱的一种，就仅比那个一点关系都没有的强一点。
2、线性结构：这种结构中数据之间有一对一的关系（如排队）。
3、树型结构：这种结构中数据之间有一对多的关系，这个关系称为父子关系（典型的如细胞分裂）。
4、网状结构：这种结构中数据之间有多对多的交叉映射关系。

（我们主要研究线性结构和树型结构。）

## 1.2 数据结构的物理结构

1、顺序结构：结构中的数据元素存放在一段连续的内存空间中，典型代表就是数组。随机访问方便，插入删除复杂。
2、链式结构：这种结构中不同的数据被存储在计算机里不同的地方，他们的物理位置之间完全没有关系。链式结构由多个节点构成，每个节点中包括有效数据和至少一个指针变量。

/*链式结构练习*/
#include <stdio.h>

typedef struct node{
int num;
struct node *p_next;//void *p_next;
}node;
node node1 = {1,NULL};

int main(){
node node2 = {2,NULL};
static node node3 = {3,NULL};
node node5 = {5,NULL};//新添一个节点，把它加入链表中

node1.p_next = &node2;
node2.p_next = &node3;
//用二级指针把新增节点5挂上去
while (*pp_tmp){
pp_tmp = &((*pp_tmp)->p_next);
}
*pp_tmp = &node5;*/

//第二种把新增节点5加进去的方法
node *p_tmp = NULL;
while (p_tmp->p_next){
p_tmp = p_tmp->p_next;
}
p_tmp->p_next = &node5;
}
else {
}
//显示所有节点数据
while (p_tmp){
printf("%-3d",p_tmp->num);
p_tmp = p_tmp->p_next;
}
printf("\n");
return 0;
}

## 1.3 数据结构的运算结构

1、创建/销毁
分配资源、建立结构、释放资源
2、插入/删除
增加、减少数据元素
3、获取/修改
遍历、迭代、随机访问
（增删改查）
4、排序/查找
算法应用

2017-08-11 11:54:52 LiuJiuXiaoShiTou 阅读数 669

# 数据结构图文解析之：哈夫曼树与哈夫曼编码详解及C++模板实现

2018-02-28 10:23:23 qq_33733970 阅读数 382

1.进栈函数：append
2.出栈函数：pop
3.查看栈顶函数：li[-1]

##### 链表

class Node(object):
def __init__(self, item):
self.item = item
self.next = None

##### 二叉树：

class BiTreeNode:
def __init__(self, data):
self.data = data
self.lchild = None
self.rchild = None

# 待补充~

2017-12-02 22:58:18 m0_38128121 阅读数 457