设计getMin功能的栈

[编程题]设计getMin功能的栈

热度指数：14989 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

实现一个特殊功能的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

输入描述:

第一行输入一个整数N，表示对栈进行的操作总数。

下面N行每行输入一个字符串S，表示操作的种类。

如果S为"push"，则后面还有一个整数X表示向栈里压入整数X。

如果S为"pop"，则表示弹出栈顶操作。

如果S为"getMin"，则表示询问当前栈中的最小元素是多少。

输出描述:

对于每个getMin操作，输出一行表示当前栈中的最小元素是多少。

示例1

输入

6
push 3
push 2
push 1
getMin
pop
getMin

输出

1
2

备注:

1<=N<=1000000

-1000000<=X<=1000000

数据保证没有不合法的操作

算法知识视频讲解

mmmm0531

#include <stdio.h>
#include <string.h>
#define N 1000000
int a[N];
int len=0;
int min=1000000;
int main(){
int n,num;
char s[10]={0};
scanf("%d",&n);

while(n--){
scanf("%s",s);
if(!strcmp(s, "push")){
scanf("%d",&num);
a[len++]=num;
if(num<min)
min=num;
}else if(!strcmp(s, "pop")){
len--;
int m=1000000;
for(int i = 0;i<len;i++){
if(a[i]<m)
m=a[i];
}
min=m;
}else if(!strcmp(s, "getMin")){
printf("%d\n",min);
}
memset(s,0,sizeof(s));
}

}

发表于 2022-03-31 18:39:02 回复(0)

helloxuanbao

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdbool.h>

typedef struct {
    int *data;
    int top;
} stack;

stack *new_stack(int cap) {
    stack *st = (stack *) malloc(sizeof(stack));
    st->data = (int *) malloc(sizeof(int) * cap);
    st->top = -1;
    return st;
}

void push(stack *st, int val) {
    st->data[++st->top] = val;
}

int pop(stack *st) {
    return st->data[st->top--];
}

int top(stack *st) {
    return st->data[st->top];
}

bool is_empty(stack *st) {
    return st->top == -1;
}

void destroy_stack(stack *st) {
    free(st->data);
    free(st);
}

int main(void) {
    int n, x;
    char opt[10];
    scanf("%d", &n);
    stack *nums = new_stack(n);
    stack *mins = new_stack(n);
    for (int i = 0; i < n; i++) {
        scanf("%s", opt);
        if (strcmp(opt, "push") == 0) {
            scanf("%d", &x);
            push(nums, x);
            if (is_empty(mins) || x <= top(mins)) {
                push(mins, x);
            }
        } else if (strcmp(opt, "pop") == 0) {
            x = pop(nums);
            if (x == top(mins)) {
                pop(mins);
            }
        } else {
            printf("%d\n", top(mins));
        }
    }
    destroy_stack(nums);
    destroy_stack(mins);
    return 0;
}

发表于 2022-02-15 20:37:54 回复(0)