面试题21 包含min函数的栈-白红宇

面试题21 包含min函数的栈

阅读量：2400 次

发布时间：2019-05-10

本文共 1581 字，大约阅读时间需要 5 分钟。

地址：http://ac.jobdu.com/problem.php?pid=1522

题目1522：包含min函数的栈

题目描述：

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

输入：

输入可能包含多个测试样例，输入以EOF结束。

对于每个测试案例，输入的第一行为一个整数n(1<=n<=1000000)， n代表将要输入的操作的步骤数。

接下来有n行，每行开始有一个字母Ci。

Ci=’s’时，接下有一个数字k，代表将k压入栈。

Ci=’o’时，弹出栈顶元素。

输出：

对应每个测试案例中的每个操作，

若栈不为空，输出相应的栈中最小元素。否则，输出NULL。

样例输入：

7s 3s 4s 2s 1oos 0

样例输出：

解题思路：

1、栈为空时，压栈

2、栈不为空时，如果当前值比栈顶元素小，将当前值压入栈中，否则再次压入栈顶元素

注意：

在压栈弹栈序列中会遇到栈为空的情况。

#include 
    
     #include 
     
      using namespace std;stack
      
        minS;//k == -1 表示弹栈void min(int k){    if(minS.empty()){        if(k == -1){            printf("NULL\n");            return;        }               minS.push(k);    }    else if(!minS.empty()){        if(k == -1){            minS.pop();            if(minS.empty()){                printf("NULL\n");                return;            }        }        else{            if(k < minS.top())                minS.push(k);            else                minS.push(minS.top());        }    }    printf("%d\n", minS.top());}int main(){    int n;    int k;    char ch[2];    while(scanf("%d", &n) != EOF){        while(!minS.empty())            minS.pop();        while(n --){            scanf("%s", ch);            if(ch[0] == 's'){                scanf("%d", &k);                min(k);            }            else if(ch[0] == 'o')                min(-1);        }    }    return 0;}/**************************************************************    Problem: 1522    Language: C++    Result: Accepted    Time:20 ms    Memory:1052 kb****************************************************************/