数据结构实验之栈八：栈的基本操作

2019-11-08 03:06:13

字体：大中小

来源：转载

供稿：网友

数据结构实验之栈八：栈的基本操作 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic

做的太慢。。遇见莫名的坑(┬＿┬)↘

PRoblem Description

堆栈是一种基本的数据结构。堆栈具有两种基本操作方式，push 和 pop。push一个值会将其压入栈顶，而 pop 则会将栈顶的值弹出。现在我们就来验证一下堆栈的使用。

Input

首先输入整数t（1 <= t <= 10），代表测试的组数，以后是 t 组输入。对于每组测试数据，第一行输入两个正整数 m（1 <= m <= 100)、n（1 <= n <= 1000)，其中m代表当前栈的最大长度，n代表本组测试下面要输入的操作数。而后的 n 行，每行的第一个字符可能是’P’或者’O’或者’A’；如果是’P’，后面还会跟着一个整数，表示把这个数据压入堆栈；如果是’O’，表示栈顶元素出栈；如果是’A’，表示询问当前栈顶的值’。

Output

对于每组测试数据，根据其中的命令字符来处理堆栈；（1）对所有的’P’操作，如果栈满输出’F’，否则完成压栈操作；（2）对所有的’A’操作，如果栈空，则输出’E’，否则输出当时栈顶的值；（3）对所有的’O’操作，如果栈空，则输出’E’，否则输出栈顶元素的值，并让其出栈；

Example Input

2 5 10 A P 9 A P 6 P 3 P 10 P 8 A P 2 O 2 5 P 1 P 3 O P 5 A Example Output

E 9 8 F 8

3 5 Hint

建议：用串的方式（%s）读入操作字符。

way 1 数组模拟栈

#include <bits/stdc++.h>using namespace std;int main(){ int t; scanf("%d",&t); while(t--) { int m,n; int s[200],t; char k[10]; scanf("%d%d",&m,&n); int i=-1; while(n--) { scanf("%s",k); if(k[0]=='P') { scanf("%d",&t); if(i+1>=m) {printf("F/n");} else {i++;s[i]=t;} } else if(k[0]=='A') { if(i==-1) printf("E/n"); else printf("%d/n",s[i]); } else if(k[0]=='O') { if(i==-1) printf("E/n"); else { printf("%d/n",s[i]); i--; } } } printf("/n"); } return 0;}

可能是受了顺序表的折磨，都太长了。。。就是不想用栈写啊，以至不会用 = = 辣鸡！ way 2 来源：http://blog.csdn.net/sunmh_ac/article/details/49049049

#include<stdio.h>#include<string.h>#include<stdlib.h>int n;typedef struct{ int *top; int *base; int stacksize;}stack;int initstack(stack &s){ s.base = (int *)malloc(n*sizeof(int)); if(!s.base) exit(0); s.top = s.base; s.stacksize = n; return 1;}int empty(stack &s){ if(s.base == s.top) return 1; else return 0;}void push(stack &s,int e){ *s.top++ = e;}int main(){ char ch,p[100]; int t,m,n,key; stack s; scanf("%d",&t); for(int i = 1;i <= t;i++) { scanf("%d %d",&m,&n); initstack(s); while(n--) { scanf("%s",p); ch = p[0]; if(ch == 'P') { scanf("%d",&key); if(s.top - s.base >= m) { printf("F/n"); } else { push(s,key); } } else if(ch == 'A') { if(empty(s)) { printf("E/n"); } else { printf("%d/n",*(s.top-1)); } } else if(ch == 'O') { if(empty(s)) { printf("E/n"); } else { printf("%d/n",*(s.top -1)); s.top--; } } } if(i < t) printf("/n"); } return 0;}

上一篇：数据结构实验之栈四：括号匹配

下一篇：数据库查询带有逗号数据进行分割多行显示