栈、队列和二叉树

马上美赛要来了，写两道题压压惊 😄

Stack

题目如下

问题描述 实现一个栈，完成以下功能： 入栈 出栈 查询栈中位置Y是谁 一开始栈为空，栈中的位置从1开始（即栈底位置为1）。

输入

第一行一个整数n，表示操作个数（1 <= n <= 100000） 接下来n行，每行第一个数字表示操作（见描述）：

若为数字1，则接下来有一串字符串X，表示将X压入栈中。

若为数字2，表示弹出栈顶（保证栈非空），并输出出栈的这个人。

若为数字3，则接下来有一个整数Y，表示询问栈中位置Y是谁（保证位置Y合法），并输出名字。

输入样例 ：
11                                                                                            
1  a
1  b
1  c
3  1
3  2
3  3
2
1  d
3  1
3  2
3  3
输出样例:
a
b
c
c
a
b
d

直接用最简单的数组模拟就ok了，其实用stl里面的应该也可以，这点时间应该不会卡，代码如下：

#include <bits/stdc++.h>
using namespace std;

string Stack[100005];
int top = 1;

void push(string name) {
    Stack[top++] = name;    
}

string pop() {
    return Stack[--top];
}

string query(int pos) {
	return Stack[pos];    
}

int main() {
    int n;
    scanf("%d", &n);
    char name[20];
    for (; n--; ) {
        int op;
        scanf("%d", &op);
        if (op == 1) {
            scanf("%s", name);
            push(name);
        } else if (op == 2) {
            printf("%s\n", pop().c_str());  //c_str的作用是将c++的string类型转化成c的字符串常量，使用%s输出
        } else {
            int pos;
            scanf("%d", &pos);
            printf("%s\n", query(pos).c_str());  
        }
    }
    return 0;
}

Queue

题目如下：

时间限制：2s，空间256MB
问题描述

实现一个队列，完成以下功能：入列 出列 查询队列中位置Y是谁

一开始队列为空，队列中的位置从1开始（即队头从1开始）。

输入 第一行一个整数n，表示操作个数（1 <= n <= 100000）接下来n行，每行第一个数字表示操作（见描述）：

若为数字1，则接下来有一串字符串X，表示将X加入队列中。
若为数字2，表示出列（保证队列非空），并输出出列的这个人。
若为数字3，则接下来有一个整数Y，表示询问队列中位置Y是谁（保证位置Y合法），并输出名字。

数据中的字符串只包含26个小写字母（无空格灯分隔符），且长度不超过15

字符串可能有重复，正如现实中可能有重名。

输出
将所有操作2和操作3输出，一行一个。

输入样例
11
1 a
1 b
1 c
3 1
3 2
3 3
2
1 d
3 1
3 2
3 3
1
2
3
4
5
6
7
8
9
10
11
12
输出样例
a
b
c
a
b
c
d

直接用数组模拟，为了极简，并没有考虑边界情况，当然取模也是完全没有问题的。代码如下：

#include <bits/stdc++.h>
using namespace std;

string myqueue[100005];
int rear = 0 , front = 0;

void enqueue(string name) {
	myqueue[rear++] = name;
}

string dequeue() {
	return myqueue[front++];   
}

string query(int pos) {
    return myqueue[front+pos-1];
}

int main() {
    int n;
    scanf("%d", &n);
    char name[20];
    for (; n--; ) {
        int op;
        scanf("%d", &op);
        if (op == 1) {     //入队 
            scanf("%s", name);
            enqueue(name);
        } else if (op == 2) {    //出队 
            printf("%s\n", dequeue().c_str());
        } else {
            int pos;
            scanf("%d", &pos);    //查询 
            printf("%s\n", query(pos).c_str());
        }
    }
    return 0;
}

二叉排序树

在写这道题之前，先得搞清楚啥是二叉排序树，也叫二叉搜索树啥的。首先肯定是二叉树，再就是排序，规则就是对于一个根节点，左节点小于它，右节点大于它，并递归下去。举一个例子：

从图中可以看到，不管是12这个节点，还是7这个节点，左边的孩子都小于它，右边的孩子都大于它。

题目：

问题描述
给定一个1到n的排列（无重复元素），按顺序依次插入到一棵二叉排序树中，请你将这棵二叉树前序遍历和后序遍历输出。
保证树高不超过50 。

输入
第一行一个整数n。（1 ≤ n ≤ 100000）

接下来一行表示为n个整数，代表1到n的一个排列。

输出
输出所建成的二叉树的前序遍历和后序遍历。

输入样例
10
2 6 9 3 5 7 10 8 4 1

输出样例
2 1 6 3 5 4 9 7 8 10
1 4 5 3 8 7 10 9 6 2

测试输入
20
8 6 4 13 15 17 11 12 19 18 16 10 7 1 2 7 3 5 9 14

测试输出
8 6 4 1 2 3 5 7 7 13 11 10 9 12 15 14 17 16 19 18
3 2 1 5 4 7 7 6 9 10 12 11 14 16 18 19 17 15 13 8

代码实现：

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

int n;
const int N = 100005;

//构造树的结构，用数组维护 
struct node {
	int r , l , val;
}t[N];

int root, cnt;  //树的根节点和整体的高度 

int insert(int v , int x) {  //生成二叉排序树 
	if(x == 0) {    //如果发现是空节点
		x = ++cnt;
		t[x].val = v;
		t[x].l = 0;
		t[x].r = 0;  		
		return x;			
	}   //如果当前值比根节点小，去左边去找，否则去右边
	if(v < t[x].val)
		t[x].l = insert(v , t[x].l);
	else
		t[x].r = insert(v , t[x].r);
	
	return x;  //将对应的编号进行根更新	
}

void pre_visit(int x, vector<int> & ans)
{
	if(x)
	{
		ans.push_back(t[x].val);  //将前序结果保存到vector中
		pre_visit(t[x].l, ans);
		pre_visit(t[x].r, ans);	
	}
}

void last_visit(int x, vector <int> & ans)  //将后序节点保存到vector中
{
	if(x)
	{	
		last_visit(t[x].l, ans);
		last_visit(t[x].r, ans);			
		ans.push_back(t[x].val); 
	}
}
vector <int> getAnswer(vector <int> v) {
	root = cnt = 0;
	
	//将序列中的元素插入到二叉排序树中 
	for(int i = 0 ; i < int(v.size()); ++i) {
		root = insert(v[i] , root);
	} 
	
	vector<int> ans;
	pre_visit(root, ans);
	last_visit(root, ans);
	
	return ans;
} 

int main() {
	vector<int> V;
	scanf("%d", &n);
	for(int i = 0 ; i < n ; ++i) {
		int tmp;
		scanf("%d", &tmp);
		V.push_back(tmp);
	}
	
	vector<int> ans = getAnswer(V);
	
	for(int i = 0 ; i < n ; ++i)
		printf("%d%c", ans[i], " \n"[i == n - 1]);
	for(int i = 0 ; i < n ; ++i)
		printf("%d%c", ans[i + n], " \n"[i == n - 1]);
		
	return 0;	
}

首先将序列保存到一个向量中，调用getAnswer函数，在getAnswer函数内部，会首先调用insert函数，将vector中的每个数据递归地插入到二叉排序中，这块有许多细节需要注意，比如如果是一个空节点的情况，对应节点的l，r和val肯定都是需要更新的。但更重要的是，如何给每个节点进行编号，这里使用cnt来操作，每插入一个节点，都要更新一下cnt的值，然后赋值给相应的x，以免在插入的过程中，有值被覆盖。最后就是先序遍历和后序遍历的结果保存在ans向量中，这块学过数据结构的应该都会操作。

最后还有一个比较骚的操作就是" \n"[i == n - 1]，应该把它看作一个整体，方框表示数组索引，当i=n-1的时候，这个表达式的值为真，结果为1，所以就会输出\n，否则会输出空格。