一.前言：

　　　　1.栈是一种先进后出结构的数据结构，栈加入元素是从栈顶加入的，删除元素也是从栈顶删除的；

　　　　2.队列是一种先进先出的数据结构，队列加入元素是从队尾加入的，删除元素是从队首删除的；

二.习题练习

(A)

现在有n个元素分别是1,2,3,...,n，我们想知道通过一个栈，在n次push/pop后，出栈序列可能是什么样的。例如n是5，那么入栈次序就是1,2,3,4,5，如果我们希望出栈次序同样是1,2,3,4,5，那只要每push一个数，就立即pop一个数。如果我们希望出栈次序是3,2,4,5,1，那么我们先让1,2,3入栈，然后pop出来3和2，接着4入栈后马上pop，再就是5入栈后马上pop，最后再把栈里的1pop出。再例如，如果我们希望出栈次序是5,4,1,2,3，这是办不到的，如果要让5最先出栈，那么出栈次序只可能是5,4,3,2,1

input:

输入由多块输入构成，每块的第一行是n，（1≤n≤1000），接着是多组测试数据，每组一行，每行由n个1到n的整数组成，直到某一行第一个数是0表示此输入块结束，然后是下一块数据。
当某一块的第一行的n是0的时候结束所有输入

output:

对每组数据，只要输出Yes或No，Yes表示能产生那样的出栈序列，No表示不能。 输入块与输入块之间要多输出一个空行分隔。注意对于最后一个n为0的输入块不要多输出空行。

sample input:

5

1 2 3 4 5

5 4 1 2 3

0

6

6 5 4 3 2 1

0

0

sample output:

Yes

No

 

Yes

 

题解：

#include "stdio.h"
int b[10100];
int a[10100],n,top,top1,m,j;
int judge(){
    for(j = 1;j <= n;j++){
        a[++top] = j; 
        while(top >= 1 && a[top] == b[top1]) //边存入栈，边匹配，匹配上了则执行pop操作
            top--,top1++;                 
    }
    return top > 0;
}
int main()
{
    while(1){
        scanf("%d",&n);
        if(n == 0) break;
        while(1){
            top = 0;
            top1 = 1;
            scanf("%d",&m);
            if(m == 0)   break;//输入每行第一个，如果为0则结束输入
            b[1] = m;
            for(j = 2;j <= n;j++)
                scanf("%d",&b[j]);
            if(judge()) printf("No\n");
            else printf("Yes\n");
        }
        printf("\n");
    }
    return 0;
}

 

(B)

定义一个二维数组

int maze[5][5] = {

        0, 1, 0, 0, 0,

        0, 1, 0, 1, 0,

        0, 0, 0, 0, 0,

        0, 1, 1, 1, 0,

        0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

 

input:

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

output:

左上角到右下角的最短路径，格式如样例所示。

sample input:

0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

sample output:

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

 题解：

#include "bits/stdc++.h"
using namespace std;
int mp[10][10];
struct node{
    int x,y;
    int step;
    int x1[10],y1[10];
};
int mv[4][2] ={{-1,0},{1,0},{0,-1},{0,1}};
queue <node> q;
node u,v,w;
int book[10][10];
int main()
{
    for(int i = 0;i < 5;i++)//初始化地图
        for(int j = 0;j < 5;j++)
            cin >> mp[i][j];
    u.x = 0;
    u.y = 0;
    book[u.x][u.y] = 1;
    q.push(u);
    while(!q.empty()){
        v = q.front();//从队首取出一个节点进行广搜
        q.pop();//出队
        if(v.x == 4 && v.y == 4){
            for(int i = 0;i < v.step;i++)
                cout << "(" << v.x1[i] << ", " << v.y1[i] << ")" << endl;//打印最短路径
            cout << "(" << 4 << ", " << 4 << ")" << endl;//直接打印终点
            break;
        }
        for(int i = 0;i < 4;i++){
            w.x = v.x + mv[i][0];
            w.y = v.y + mv[i][1];
            w.step = v.step + 1;
            if(w.x > 4 || w.x < 0 || w.y > 4 || w.y < 0)
                continue;//如果超出地图，则进行下一次尝试
            if(book[w.x][w.y] == 1 || mp[w.x][w.y] == 1)
                continue;//如果这条路已经走过，或者这条路不能走，则进行下一次尝试
            book[w.x][w.y] = 1;//标记这条路已经走过
            w.x1[v.step] = v.x;//保存本次路径
            w.y1[v.step] = v.y;//保存本次路径
            q.push(w);//保存整条路径
        }
    }
    return 0;
}

(C)

You are given a string consisting of parentheses ( ) and [ ]. A string of this type is said to be correct:

if it is the empty string

if A and B are correct, AB is correct,

if A is correct, (A) and [A] is correct.

Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is 128.

Input

The first line contains the number of test cases n. Each of the next n lines contains the string of parentheses ( ) and [ ].

Output

For each test case print in a separate line "Yes" if the expression is correct or "No" otherwise.

Example 1

Input example #1 

3

([])

(([()])))

([()[]()])()

Output example #1 

Yes

No

Yes

 

 题解：

#include "stdio.h"
#include "string.h"
int main()
{
    char ans[10010];
    char tt[10010];
    int n;
    scanf("%d",&n);
    getchar();//把换行接掉，避免影响到字符串输入
    for(int i = 0; i < n; i++){
        gets(tt);
        int j;
        for(j = 0;j < strlen(tt);j++)
            if(tt[j] != ' ')
                break;
        if(j == strlen(tt)){//如果全是空格，则输出Yes
            printf("Yes\n");
            continue;
        }
        int top = 0;
        for(int i = 0; i < strlen(tt); i++){//进行括号匹配
            if(top == 0)
                ans[++top] = tt[i];
            else if(ans[top] == '(' && tt[i] == ')')
                top--;
            else if(ans[top] == '[' && tt[i] == ']')
                top--;
            else if(tt[i] != ' ')
                ans[++top] = tt[i];
        }
        if(top > 0)//如果没有匹配完毕，则输出NO
            printf("No\n");
        else 
            printf("Yes\n");
    }    
    return 0;
}

(D)

欢迎大家加入ACM！
要深入的学习ACM的相关知识，首先就必须学会一门编程语言，推荐C/C++。
不过对于初学者，因为没编过多少代码，经常出现变异错误，其实就是语法错误。
现在要你检查一段代码的语法是否否正确。
为了简化问题，我们只检查 (、)、{、} 括号是否匹配了，并且在输入的代码中不包含字符的'(',')','{','}'。
其他语法错误不检查，如 "#include <stdio.h"，"2 = x"，是错误的，但是不检查。

Input

有多组测试数据，每组测试数据有一段代码，该段代码可能在有多行。
每段代码以Ctrl+Z结束。
处理到文件结束。

Output

每组测试数据输出一行。
如果这段代码括号匹配了，输出 Right ，否则输出 Wrong。

Sample Input

#include <stdio.h
int main(){
    int a b;
    while (scanf("%d%d", &a, &b) != EOF) {
        printf("%d\n", a + b);
    }
}
Ctrl+Z
int main(){
    int a, b;
    while (scanf("%d%d", &a, &b) != EOF) {
        printf("%d\n", a + b);
   
}
Ctrl+Z

Sample Output

Right
Wrong

 题解：

#include "stdio.h"
#include "string.h"
char str[1010];
char stk[10010];
int top;
int main()
{
    top = 0;
    int flag = 0;
    while(scanf("%s",str) != EOF){
        if(strcmp(str,"Ctrl+Z") == 0)//进行匹配
            if(top == 0 && !flag){//如果已经匹配完成了，并且成功了
                flag = 0;
                printf("Right\n");
                continue;
            }
            else {
                flag = 0;
                printf("Wrong\n");
                top = 0;
                continue;
            }

            for(int i = 0;i < strlen(str);i++)//遍历整个字符串，进行存储和匹配
                if(str[i] == '(')
                    stk[++top] = '(';
                else if(str[i] == '{')
                    stk[++top] = '{';
                else if(str[i] == ')' && top == 0 || str[i] == ')' && stk[top] != '(')
                    {   flag = 1;break;}
                else if(str[i] == ')' && stk[top] == '(')
                    top--;
                else if(str[i] == '}' && top == 0 || str[i] == '}' && stk[top] != '{')
                    {flag = 1;break;}
                else if(str[i] == '}' && stk[top] == '{')
                    top--;
    }
    return 0;
}

(E)

宇神完成了栈的实验要求后，他又很是开心，刚要出去五排, 菌菌子突然问道老师让做的队列的那个实验你写完了么，宇神顿时大呼悲哉。。。。他给忘记了，怎么办。。明天就要上交实验报告了，你能帮他搞定么？？？

你需要完成三种操作1.enqueue x，将元素x插入队尾。2.dequeue,若队列非空，则删去队头元素，并输出该元素。3.query，从队头开始删除所有元素，并输出。

 

 

Input

本题有多组测试数据，每组数据首先输入一个T,接下来T行是T种对队列的操作。  (0< T < 100，0< x <= 500)

 

Output

每次执行dequeue操作时删除队头元素输出并换行，如果队列为空输出“this is empty!”并换行。

每次执行query操作时删除所有元素队列内所有元素并输出,每个元素占一行，如果栈为空输出“this is empty!”并换行。

每组数据后有一个空行。

 

Sample Input

10

enqueue 1

enqueue 2

enqueue 3

enqueue 4

query

dequeue

enqueue 1

dequeue

query

dequeue

 

Sample Output

1

2

3

4

this is empty!

1

this is empty!

this is empty!

 

题解：

#include "bits/stdc++.h"
using namespace std;
int main()
{
    char s[1100];
    int que[1100];
    int x;
    int n;
    while(cin >> n){
        int head = 0;
        int tail = 0;
        while(n--){
            cin >> s;
            if(strcmp(s,"enqueue") == 0){//匹配入队操作
                cin >> x;
                que[++tail] = x;
            }
            else{
                if(head == tail)//匹配出队操作
                    cout << "this is empty!" << endl;
                else if(strcmp(s,"query") == 0){
                    while(head < tail)
                        cout << que[++head] << endl;
                }
                else if(strcmp(s,"dequeue") == 0)
                    cout << que[++head] << endl;
            }
        }
        printf("\n");
    }
    return 0;
}

 

(F)

冰冰子最近新学习了队列和栈两种重要的数据结构，他知道它们具有push 和pop操作。

而冰冰子现在想同时研究栈和队列，于是，他开始了一个实验。

现在，假设队列和栈都是空的。给定一系列push k和pop操作之后，冰冰子想知道队列和栈中分别存的数字。若队列或栈已经空了，仍然接收到pop操作，则输出error。

 

Input

第一行为m，表示有m组测试输入，m<100。
每组第一行为n，表示下列有n行push k或pop操作。（n<150）
接下来n行，每行是push k或者pop，其中k是一个整数。
（输入保证同时在队列或栈中的数不会超过100个）

Output

对每组测试数据输出两行，第一行是队列情况，若在队列空时收到pop操作，则输出error。其余情况将队列按照对头至队尾顺序输出队列中所有元素，中间用空格隔开。第二行是栈的情况，若在栈空时收到pop操作，则输出error。其余情况下按照栈底至栈顶的顺序输出栈中所有元素。

Sample Input

2

4

push 1

push 3

pop

push 5

1

pop

 

Sample Output

3 5

1 5

error

error

 题解：

#include "stdio.h"
#include "string.h"
char op[100];
int que[1100];
int stk[1100];
int top,head,tail,flag1,flag2;
int n,m,x;
int main()
{
    scanf("%d",&m);
    while(m--){
        scanf("%d",&n);
        top = head = tail = flag1 = flag2 = 0;
        while(n--){
                scanf("%s",op);
                if(op[1] == 'o' ){//匹配对应的操作
                    if(head == tail) flag1 = 1;//如果队列为空执行pop操作
                    else head++;
                    if(top == 0) flag2 = 1;//如果栈为空执行pop操作
                    else top--;
                }
                if(op[1] == 'u'){
                    scanf("%d",&x);
                    que[++tail] = x;
                    stk[++top] = x;
                }
            }
        if(flag1) printf("error\n");//如果执行过非法操作，则输出error
        else{
            while(head < tail)//打印出队列全部元素
                printf("%d ",que[++head]);
            printf("\n");
        }
        if(flag2) printf("error\n");//如果执行过非法操作，则输出error
        else{
            int t = 0;
            while(t < top)//打印栈区全部元素
                printf("%d ",stk[++t]);
            printf("\n");
        }
    }
    return 0;
}

 

(G)

给出一个由1到n组成的无序数列，如果我们把这个序列看成是数字1~n出栈的顺序，并且入栈顺序是1, 2, 3, ..., n，请问操作时，栈内最多能有多少个元素？

Input

输入有多组数据。

每组数据的第一行为一个整数n代表由1到n的序列。 1<= n  <=100。

第二行为n个用空格隔开的整数，范围是[1,n]。

 

Output

若此序列能由进栈，出栈得到，输出所使用的最小栈容，否则输出-1

Sample Input

5

1 2 3 4 5

4

3 2 1 4

6

6 5 4 1 3 2

Sample Output

1

3

-1

 

题解：

#include "bits/stdc++.h"
int stk[110];
int a[110];
int top;
using namespace std;
int main()
{
    int n;
    while(cin >> n){
        int top1 = 0;
        top = 1;
        int ans = 0;//记录最大个数
        for(int i = 1;i <= n;i++)
            scanf("%d",&a[i]);
        for(int i = 1;i <= n;i++){
            stk[++top1] = i;//存入栈区
            ans = ans > top1 ? ans : top1;//进行最大匹配
            while(stk[top1] == a[top] && top1 > 0){
                top1--;
                top++;
            }
        }
        if(top1 != 0)
            cout << -1 << endl;
        else 
            cout << ans << endl;
    }
    return 0;
}

 

(H)

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

Output

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

Sample Input

1
8
5
0

Sample Output

1
92
10

 题解：

#include "bits/stdc++.h"
using namespace std;
int book[110];
int a[11];
int ans = 0;
int n;
int t;
bool judge(int m,int z)
{
    for(int i = 1;i < m;i++){
        if(book[i] == z)   return false;//如果这一行已经有皇后了
        if(book[i] - i == z - m )  return false;//匹配两条斜线上的棋子
        if(i + book[i] == m + z)  return false;//
    }
    return true;
}
void dfs(int cnt)
{
    if(t + 1 == cnt)//如果找到了一组解
    {
        ans++;
        return;
    }
    for(int i = 1;i <= t;i++){
        if(judge(cnt,i)){
            book[cnt] = i;
            dfs(cnt + 1);
            book[cnt] = 0;//回溯
        }    
    }
    return;
}
int main()
{
    a[1] = 1;
    for(t = 2;t <= 10;t++){//直接打表，不然超时
        dfs(1);
        a[t] = ans;
        ans = 0;
    }
    while(scanf("%d",&n) != EOF && n != 0)
        printf("%d\n",a[n]);
}