1.模版栈
描述
请你实现一个栈。
操作：
push x：将 加x x 入栈，保证 x x 为 int 型整数。
pop：输出栈顶，并让栈顶出栈
top：输出栈顶，栈顶不出栈
输入描述：
第一行为一个正整数 n n ，代表操作次数。(1≤n≤100000)(1≤n≤100000)
接下来的 n n ，每行为一个字符串，代表一个操作。保证操作是题目描述中三种中的一种。
输出描述：
如果操作为push，则不输出任何东西。
如果为另外两种，若栈为空，则输出 "error“
否则按对应操作输出。
这题是自己手敲一个栈出来，采用的是acm模式，我使用函数将相关的几个操作封装了起来，然后使用strcmp来分辨应该进行什么操作。因为是使用的c语言，所以分配空间的时候使用的是malloc。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max 100000
typedef struct{
int t[max];
int top;
}stack;
void initstack(stack *s){
s->top=-1;
}
void push(stack *s,int m){
if(s->top==max) printf("error\n");
else{
s->t[s->top]=m;
s->top++;
}
}
void pop(stack *s){
if(s->top==-1) printf("error\n");
else{
s->top--;
printf("%d\n",s->t[s->top]);
}
}
void top(stack *s){
if(s->top==-1) printf("error\n");
else{
s->top--;
printf("%d\n",s->t[s->top]);
s->top++;
}
}
int main(){
int n;
scanf("%d",&n);
stack *s = (stack*)malloc(sizeof(stack));
initstack(s);
while(n--){
char *r = (char*)malloc(6*sizeof(char));
scanf("%s",r);
if(!strcmp(r,"pop")) pop(s);
if(!strcmp(r,"top")) top(s);
if(!strcmp(r,"push")){
int b;
scanf("%d",&b);
push(s,b);
}
}
}
2.栈的压入、弹出序列
描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
- 0<=pushV.length == popV.length <=1000
- -1000<=pushV[i]<=1000
- pushV 的所有数字均不相同
这题依旧采用c语言进行实现，因为是核心代码模式，所以在结题时只用考虑返回值为真还是为假。我采用的是看最后栈有没有空，如果没有空则代表该序列无法实现。
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pushV int整型一维数组
* @param pushVLen int pushV数组长度
* @param popV int整型一维数组
* @param popVLen int popV数组长度
* @return bool布尔型
*/
bool IsPopOrder(int* pushV, int pushVLen, int* popV, int popVLen ) {
// write code here
int temp[pushVLen],top=0;
int m=0,n=0;
while(m<pushVLen){
temp[top++]=pushV[m++];
while(top>0&&n<popVLen&&temp[top-1]==popV[n]){
n++;
top--;
}
}
return top==0;
}
3.有效括号序列
描述
给出一个仅包含字符’(‘,’)‘,’{‘,’}‘,’[‘和’]',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()“和”()[]{}“都是合法的括号序列，但”(]“和”([)]"不合法。
数据范围：字符串长度 0≤n≤100000≤n≤10000
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
这题依旧是核心代码的模式，鉴于此，所以此题使用c++语言进行编写，使用了c++里关于栈的库函数。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return bool布尔型
*/
bool isValid(string s) {
// write code here
stack<char> a;
for(int i=0;i<s.length();i++)
{
if(a.empty())
{
a.push(s[i]);
continue;
}
if(s[i]==')'&&a.top()=='(') a.pop();
else if(s[i]==']'&&a.top()=='[') a.pop();
else if(s[i]=='}'&&a.top()=='{') a.pop();
else a.push(s[i]);
}
return a.empty();
}
};
谢谢你的阅读！
