[关闭]
@cxm-2016 2016-12-15T10:25:13.000000Z 字数 944 阅读 1386

数据结构:设计一个具有getMin的栈

数据结构

版本:2
作者:陈小默
声明:禁止商业,禁止转载

使用任意语言设计一个栈,要求具有如下功能:

  • 使用pop出栈
  • 使用push入栈
  • 使用getMin获取栈中最小值

设计思路:使用两个栈结构

  1. /**
  2. * Copyright (C) <2016> <陈小默>
  3. *
  4. * This program is free software: you can redistribute it and/or modify
  5. * it under the terms of the GNU General Public License as published by
  6. * the Free Software Foundation, either version 3 of the License, or
  7. * (at your option) any later version.
  8. *
  9. * This program is distributed in the hope that it will be useful,
  10. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. * GNU General Public License for more details.
  13. *
  14. * You should have received a copy of the GNU General Public License
  15. * along with this program. If not, see <http://www.gnu.org/licenses/>.
  16. *
  17. * Created by 陈小默 on 16/11/5.
  18. */
  19. class GetMinStack(max: Int) {
  20. val stack = Stack<Int>(max)
  21. val min = Stack<Int>(max)
  22. fun getMin(): Int = min.top!!
  23. fun pop(): Int {
  24. val value = stack.pop()!!
  25. if (value == getMin()) {
  26. min.pop()
  27. }
  28. return value
  29. }
  30. fun push(value: Int) {
  31. stack.push(value)
  32. if (min.isEmpty || value <= getMin()) {
  33. min.push(value)
  34. }
  35. }
  36. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注