@cxm-2016
2016-12-15T10:25:13.000000Z
字数 944
阅读 1408
数据结构
版本:2
作者:陈小默
声明:禁止商业,禁止转载
使用任意语言设计一个栈,要求具有如下功能:
- 使用pop出栈
- 使用push入栈
- 使用getMin获取栈中最小值
设计思路:使用两个栈结构
/**
* Copyright (C) <2016> <陈小默>
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*
* Created by 陈小默 on 16/11/5.
*/
class GetMinStack(max: Int) {
val stack = Stack<Int>(max)
val min = Stack<Int>(max)
fun getMin(): Int = min.top!!
fun pop(): Int {
val value = stack.pop()!!
if (value == getMin()) {
min.pop()
}
return value
}
fun push(value: Int) {
stack.push(value)
if (min.isEmpty || value <= getMin()) {
min.push(value)
}
}
}