文章目录???
1.栈
2.队列
?一、简单介绍栈和队列
? ? ? ?1.栈：栈(stack)是限定仅在表尾进行插入或者删除的线性表，表尾被成为栈顶，表头被称为栈底。对于栈来说，对他只能在栈顶进行操作。所以，栈又被称为先进后出的线性表。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
?2.队列：队列只允许在队列的头进行删除操作，在队列的尾进行插入操作。特点是：先进先出。
二、题目练习
1.
现在有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 0Sample Output
Yes No Yes代码如下：
#include <iostream> using namespace std; const int N = 1010; bool solve(int *a,int n) { int *s = new int [N]; int top = 0; int j = 1; for(int i = 1; i <= n; i++) { s[++top] = i; while(top >= 1 && s[top] == a[j] && j <=n) { j++; top--; } } if(top == 0) return true; else return false; } int main() { ios :: sync_with_stdio(false); cin.tie(); cout.tie(); int n; while(1) { cin >> n; if(n == 0) { return 0; } bool flag = true; while(1) { int *a = new int [N]; for(int i = 1; i <= n; i++) { cin >> a[i]; if(a[1] == 0 && i == 1) { flag = false; cout << endl; break; } } if(flag == true) if(solve(a,n)) cout <<"Yes"<<endl; else cout <<"No"<<endl; else break; delete [] a; } } return 0; }2.
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?content_copy
3 ([]) (([()]))) ([()[]()])()Output example #1?content_copy
Yes No YesExample 2
Input example #10?content_copy
22 ((() ()))) ([)] ((([[[]]])]) ([]) (([()]))) ([()[]()])() [(]) (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) (]) [)] [)))] [[)] ([]) (([()]))) ([()[]()])() ([)] ( ()( [()Output example #10?content_copy
No Yes No No Yes No Yes No Yes No Yes No No No No Yes No Yes No No No No代码如下：
#include <cstring> #include <iostream> #include <vector> using namespace std; const int N = 150; vector<string> answer; int main() { ios ::sync_with_stdio(false); cin.tie(); cout.tie(); char c; int n; // cin >> n; scanf("%d",&n); getchar(); while (n--) { char *a = new char[N]; // char *c = new char[N]; char c[N]; int top = 0; bool flag = true; // cin>>c; // scanf("%s",c); gets(c); // getchar(); // cout<<c<<endl; for (int i = 0; i < strlen(c); i++) { if (c[i] == '(' || c[i] == '[') a[++top] = c[i]; else if (c[i] == ']' || c[i] == ')') { if (a[top] == '(' && c[i] == ')' || a[top] == '[' && c[i] == ']') { top--; } else { // if (c[i] != a[top] || top == 0) flag = false; } } } if (top == 0 && flag) { cout << "Yes" << endl; } else { cout << "No" << endl; } delete[] a; } return 0; }3.
欢迎大家加入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+ZSample Output
Right
Wrong代码如下：
#include <iostream> #include <cstring> using namespace std; char a[10000][10000]; char q[10000]; int main() { while(~scanf("%s",a[0])) { int i = 1; while(~scanf("%s",a[i])) { if(strcmp(a[i],"Ctrl+Z") == 0) break; i++; } int top = 0; bool flag = true; for(int j = 0; j < i; j++) { for(int k = 0; a[j][k] != '\0'; k++) { if (a[j][k] == '(' || a[j][k] == '{') { q[++top] = a[j][k]; } else if (a[j][k] == '}' || a[j][k] == ')') { if (q[top] == '(' && a[j][k] == ')' || q[top] == '{' && a[j][k] == '}') { top--; } else { //cout << 132<<endl; flag = false; } } } if(flag == false) break; } if (top == 0 && flag) cout <<"Right"<<endl; else cout <<"Wrong"<<endl; } return 0; }4.
宇神完成了栈的实验要求后，他又很是开心，刚要出去五排,?菌菌子突然问道老师让做的队列的那个实验你写完了么，宇神顿时大呼悲哉。。。。他给忘记了，怎么办。。明天就要上交实验报告了，你能帮他搞定么？？？
你需要完成三种操作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 dequeueSample Output
1 2 3 4 this is empty! 1 this is empty! this is empty!#include <iostream> using namespace std; void push(int *a,int *tail,int x) { a[(*tail)++] = x; } void pop(int *a,int *front,int tail) { while(*front < tail) { cout << a[(*front)]<<endl; (*front)++; } } int main() { int n; while(cin >> n) { int tail = 0,front = 0; int *a = new int [200]; for(int i = 0; i < n; i++) { string op; int n; cin >> op; if(op[0] == 'e') { cin >> n; push(a,&tail,n); } if(op[0] == 'd') { if(front >= tail) cout <<"this is empty!"<<endl; else cout << a[front++]<<endl; } if(op[0] == 'q') { if(front >= tail) cout <<"this is empty!"<<endl; pop(a,&front,tail); } } cout << endl; } }5.
冰冰子最近新学习了队列和栈两种重要的数据结构，他知道它们具有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 popSample Output
3 5 1 5 error error代码如下：
#include <iostream> #include <cstring> using namespace std; const int N = 2000; int front,top1,top2; void push(int *q,int *s,int n) { q[top1++] = n; s[top2++] = n; } void pop() { front++; top2--; } int main() { int t; cin >> t; while(t--) { top1 = top2 = front = 0; int *q = new int [N]; int *s = new int [N]; bool flag = true; int n; scanf("%d",&n); for(int i = 1; i <= n; i++) { char op[60]; scanf("%s",op); getchar(); if(strcmp(op,"push") == 0) { int t; cin >> t; push(q,s,t); } if(strcmp(op,"pop") == 0) { if(top2 <= 0) flag = false; else pop(); } } if(flag ==true) { while(front < top1) cout << q[front++]<<" "; cout << endl; for(int i =0; i < top2; i++) cout <<s[i]<<" "; cout << endl; } else if(flag == false) cout <<"error"<<endl<<"error"<<endl; delete [] q,s; } return 0; }