【九度】题目1522：包含min函数的栈

本文主要是介绍【九度】题目1522：包含min函数的栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

输入：

输入可能包含多个测试样例，输入以EOF结束。
对于每个测试案例，输入的第一行为一个整数n(1<=n<=1000000)， n代表将要输入的操作的步骤数。
接下来有n行，每行开始有一个字母Ci。
Ci=’s’时，接下有一个数字k，代表将k压入栈。
Ci=’o’时，弹出栈顶元素。

输出：

对应每个测试案例中的每个操作，
若栈不为空，输出相应的栈中最小元素。否则，输出NULL。

样例输入：

7
s 3
s 4
s 2
s 1
o
o
s 0

样例输出：

3
3
2
1
2
3
0

栈是先进后出的数据结构。
实现求最小值，如果直接思考，暴力搜索，可能比较耗时。
还需要随时考虑数据弹出和压入。
我们换一种思路，用两个栈来做数据操作。
一个是基本栈，只包含数据，不需要比较大小。
另一类是包含最小数的栈。这个栈包含的最小值是当前数中的最小值。
我们将这两个栈声明为numStack和minStack。
如果要压栈，先将数据压入numStack，压入minStack判断一下，当前栈是否为空，
如果为空，直接压栈，否则就判断栈顶元素和当前元素的大小，将min压入栈。
然后输出minStack的栈顶元素即是当前元素中的最小值。
如果要弹出，判断numStack是否为空，为空直接输出null。
否则numStack和minStack弹出元素，然后判断栈是否空，不空就输出minStack的栈顶元素，否则就输出null。
针对题目来说一下。
操作 numStack minStack
s 3       3                 3
s 4       4                 3
s 2       2                 2
s 1       1                 1
o        pop 1     pop 2
o        pop 2     pop 2
s 0        0                0
保持两个栈长度一致，不管是弹出还是压入，二者都需要同时操作。
C++ AC

#include <stdio.h>
#include <stack>   
#include <string.h>
#include <string>
using namespace std; 
int n,i; int main(){while(scanf("%d",&n) != EOF){stack<int> numStack;stack<int> minStack;for(i = 0; i < n; i++){char operate[2];scanf("%s",operate);if(operate[0] == 'o'){if(numStack.empty()){printf("NULL\n");}else{numStack.pop();minStack.pop();if(minStack.empty()){printf("NULL\n");}else{printf("%d\n",minStack.top());}}}else{int k;scanf("%d",&k);numStack.push(k);if (minStack.empty()) {minStack.push(k);}else {if (k < minStack.top()) {minStack.push(k);}else {minStack.push(minStack.top());}} printf("%d\n",minStack.top());}}}return 0;
} /**************************************************************Problem: 1522User: wangzhenqingLanguage: C++Result: AcceptedTime:20 msMemory:1052 kb
****************************************************************/

Java AC

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Stack;public class Main {/** 1522*/public static void main(String[] args) throws Exception {StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));while (st.nextToken() != StreamTokenizer.TT_EOF) {int n = (int) st.nval;Stack<Integer> stack1 = new Stack<Integer>();Stack<Integer> stack2 = new Stack<Integer>();for (int i = 0; i < n; i++) {st.nextToken();String a = st.sval;if (a.equals("o")) {if (stack1.isEmpty()) {System.out.println("NULL");}else {stack1.pop();stack2.pop();if (stack2.isEmpty()) {System.out.println("NULL");}else {System.out.println(stack2.peek());}}}else if (a.contains("s")) {st.nextToken();int tempNum = (int) st.nval;stack1.push(tempNum);if (stack2.isEmpty()) {stack2.push(tempNum);}else {if (tempNum < stack2.peek()) {stack2.push(tempNum);}else {stack2.push(stack2.peek());}}System.out.println(stack2.peek());}}}}
}
/**************************************************************Problem: 1522User: wangzhenqingLanguage: JavaResult: AcceptedTime:880 msMemory:27384 kb
****************************************************************/

这篇关于【九度】题目1522：包含min函数的栈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---