AB1. 【模板】栈
描述
输入描述
输出描述
示例1
输入:
6 push 1 pop top push 2 push 3 pop
输出:
1 error 3
C 解法, 执行用时: 13ms, 内存消耗: 676KB, 提交时间: 2022-07-17
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <malloc.h>
#define MAX_CONTENT_OF_STACK 100000
int main()
{
int *b = (int*)malloc(MAX_CONTENT_OF_STACK * sizeof(int));
int base = 0;
int top = base;
int i;
int operTimes = 0;
char ch_input[100] = {0};
int x = 0;
int len = 0;
int beishu = 1;
int j;
scanf("%d",&operTimes);
for(i=0;i<operTimes;i++)
{
//scanf("%s\n",ch_input);//输入空格则字符串结束(字符串中有空格时不能使用)
fgets(ch_input, sizeof(ch_input), stdin);
if(ch_input[0] == '\n')
{
fgets(ch_input, sizeof(ch_input), stdin);
}
else
{
;
}
len = strlen(ch_input);
if(ch_input[0] == 'p' && ch_input[1] == 'u')
{
if(len < 6)
{
printf("error\n");
}
else if(len == 6)
{
x = ch_input[5] - 48;
}
else
{
for(j=len-2;j>=5;j--)
{
x+=(ch_input[j] - 48)*beishu;
beishu = beishu * 10;
}
}
b[top] = x;//入栈
x = 0;
beishu = 1;
top++;
}
else if(ch_input[0] == 'p' && ch_input[1] == 'o')//输出栈顶，并让栈顶出栈
{
if(top==base)
{
printf("error\n");
}
else
{
printf("%d\n",b[top-1]);
top--;
}
}
else if(ch_input[0] == 't' && ch_input[1] == 'o')//输出栈顶，栈顶不出栈
{
if(top==base)
{
printf("error\n");
}
else
{
printf("%d\n",b[top-1]);
}
}
else
{
printf("error\n");
}
}
}
C 解法, 执行用时: 13ms, 内存消耗: 1664KB, 提交时间: 2022-05-12
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#define maxsize 100000
typedef struct
{
int data[maxsize];
int top;
}Stack;
void Create_stack(Stack ** sq)
{
*sq = (Stack *)malloc(sizeof(Stack));
}
void Init_stack(Stack * sq)
{
sq->top = -1;
}
bool push(Stack * sq, int i_data)
{
if(sq->top == maxsize - 1)
{
return false;
}
sq->top++;
sq->data[sq->top] = i_data;
return true;
}
bool pop(Stack *sq, int * o_data)
{
if(sq->top == -1)
{
return false;
}
*o_data = sq->data[sq->top];
sq->top--;
return true;
}
bool top(Stack *sq, int * o_data)
{
if(sq->top == -1)
{
return false;
}
*o_data = sq->data[sq->top];
return true;
}
int main()
{
bool status;
Stack *stack = NULL;
int o_data;
Create_stack(&stack);
Init_stack(stack);
int ope_times;
scanf("%d\n", &ope_times);
char ope_lines[ope_times][10];
int ope_sizes[ope_times];
for(int i = 0 ; i < ope_times; i++)
{
gets(ope_lines[i]);
ope_sizes[i] = strlen(ope_lines[i]);
int temp, i_data = 0, t = 1;
int ptr = ope_sizes[i];
switch(ope_sizes[i])
{
case 3:
if(ope_lines[i][0] == 'p')
{
status = pop(stack, &o_data);
if(status == true)
{
printf("%d\n", o_data);
}
else
{
printf("error\n");
}
}
else if(ope_lines[i][0] == 't')
{
status = top(stack, &o_data);
if(status == true)
{
printf("%d\n", o_data);
}
else
{
printf("error\n");
}
}
break;
default:
while(ptr > 5)
{
temp = ope_lines[i][ptr-1] - 48;
i_data += temp * t;
t *= 10;
ptr--;
}
push(stack, i_data);
break;
}
}
return 0;
}
C 解法, 执行用时: 14ms, 内存消耗: 808KB, 提交时间: 2022-07-22
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
typedef int DataType;
typedef struct Stack{
DataType * a;
int Size;
int Capacity;
}Stack;
void InitStack(Stack * p)
{
p->a = NULL;
p->Size = p->Capacity = 0;
}
bool StackEmpty(Stack *p)
{
return p->Size == 0;
}
void StackPush(Stack *p, DataType num)
{
if(p->Capacity == p->Size)
{
int newCapacity = p->Capacity == 0 ? 4 : p->Capacity*2;
DataType *tmp = (DataType *)realloc(p->a, sizeof(DataType) * newCapacity);
if(tmp)
p->a = tmp;
p->Capacity = newCapacity;
}
p->a[p->Size++] = num;
}
void StackPop(Stack * p)
{
if(StackEmpty(p))
return;
p->Size--;
}
int getNum(char *s)
{
int len = strlen(s);
int num = 0;
for(int i = 5; i < len; i++)
{
num = num * 10 + (s[i] - '0');
}
return num;
}
int main()
{
Stack p;
InitStack(&p);
int n = 0;
scanf("%d",&n);
getchar();
for(int i = 0; i < n; i++)
{
char input[10] = {0};
gets(input);
if(strcmp(input,"pop") == 0)
{
if(StackEmpty(&p))
printf("error\n");
else
{
printf("%d\n", p.a[p.Size-1]);
StackPop(&p);
}
}
else if (strcmp(input,"top") == 0)
{
if(StackEmpty(&p))
printf("error\n");
else
printf("%d\n", p.a[p.Size-1]);
}
else{
int num = getNum(input);
StackPush(&p, num);
}
}
return 0;
}
C 解法, 执行用时: 14ms, 内存消耗: 860KB, 提交时间: 2022-04-18
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<string.h>
#include<ctype.h>
typedef struct Stack
{
int* a;
int size;
int capacity;
}Stack;
void STInit(Stack* st)
{
assert(st);
st->a = NULL;
st->size = st->capacity = 0;
}
bool STEmpty(Stack* st)
{
return st->size == 0;
}
void STPush(Stack* st,int x)
{
assert(st);
// 栈满,扩容
if(st->capacity == st->size)
{
int newCapacity = st->capacity == 0 ? 4 : st->capacity * 2;
int* tmp = (int*)realloc(st->a,sizeof(int) * newCapacity);
if(tmp)
{
st->a = tmp;
}
// 新长度
st->capacity = newCapacity;
}
// 插入元素
st->a[st->size] = x;
st->size++;
}
void STPop(Stack* st)
{
assert(st);
if(STEmpty(st))
return;
st->size--;
}
int strGetNum(char* s)
{
int num = 0;
while(*s)
{
if(isdigit(*s))
{
// 转换成数字
while(isdigit(*s) && *s)
{
num = num * 10 + (*s - '0');
s++;
}
break;
}
s++;
}
return num;
}
int main()
{
Stack st;
STInit(&st);
int n = 0;
scanf("%d",&n);
getchar();
for(int i = 0;i < n;i++)
{
char input[10] = { 0 };
gets(input);
// 删除操作
if(strcmp(input,"pop") == 0)
{
// 删除失败
if(STEmpty(&st))
printf("error\n");
else
{
printf("%d\n",st.a[st.size-1]);
STPop(&st);
}
}
else if(strcmp(input,"top") == 0)
{
// 栈空
if(STEmpty(&st))
printf("error\n");
else
printf("%d\n",st.a[st.size-1]);
}
else
{
// 只剩下插入操作了
int x = strGetNum(input);
STPush(&st,x);
}
}
return 0;
}
C++ 解法, 执行用时: 14ms, 内存消耗: 1056KB, 提交时间: 2022-05-06
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void write(int x){
int cnt=0;char f[40];
if(x<0){
putchar('-');
x=-x;
}
if(!x)
putchar('0');
while(x){
f[cnt++]=x%10+'0';
x/=10;
}
while(cnt)
putchar(f[--cnt]);
putchar('\n');
}
int n;
char c[4];
stack<int> P;
signed main(){
n=read();
while(n--){
scanf("%s",c);
if(c[0]=='p')
if(c[1]=='u')
P.push(read());
else
if(!P.empty()){
write(P.top());
P.pop();
}
else
puts("error");
else
if(!P.empty())
write(P.top());
else
puts("error");
}
return 0;
}