首先实现一个顺序存储的栈。
struct MyStack<T> {
/// 声明一个泛型数组，用于存储栈中的元素(栈结构的后备存储器)
private var elements = [T]()
/// 返回栈结构中元素的个数
public var count: Int {
// 返回数组elements中的元素个数
return elements.count
}
/// 获取或者设置栈的存储容量
public var capacity: Int {
// 获取栈的存储容量
get {
// 返回数组elements的容量
return elements.capacity
}
// 设置栈的最小容量
set {
// 设置数组elements的最小容量
elements.reserveCapacity(newValue)
}
}
/// 初始化方法(创建栈实例)
public init() {}
/// 使用push方法执行入栈操作
public mutating func push(element: T) {
// 判断栈是否已满
if count == capacity {
fatalError("栈已满，不能再执行入栈操作！")
}
// 使用数组的append()方法将元素添加到数组elements中
self.elements.append(element)
}
/// 使用pop方法执行出栈操作
@discardableResult
public mutating func pop() -> T? {
// 判断栈是否已空
if count == 0 {
fatalError("栈已空，不能再执行出栈操作！")
}
// 移除数组elements的最后一个元素
return elements.popLast()
}
/// 返回栈顶元素
public func top() -> T? {
// 返回数组elements的最后一个元素(但是不移除该元素)
return elements.last
}
/// 清空栈中所有的元素
public mutating func clear() {
// 清空数组elements中所有的元素
elements.removeAll()
}
/// 判断栈是否为空
public func isEmpty() -> Bool {
// 判断数组elements是否为空
return elements.isEmpty
}
/// 判断栈是否已满
public func isFull() -> Bool {
// 对数组的存储情况进行判断
if count == 0 {
// 如果数组为空，则表示栈还未存储数据元素
return false
} else {
// 如果数组不为空，则返回数组的存储容量
// 然后再根据实际存储情况判断栈是否已满
return count == elements.capacity
}
}
}
一。括号匹配检验
假设表达式中允许包含两种括号：圆括号和方括号，其嵌套顺序随意，即()或者[([][])]都是正确的，而这[(]或者(()])或者([())都是不正确的格式，检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述，例如，考虑以下括号的判断：[([][])]
func checkSymbol(orgStr:String) -> Bool {
let leftArr = ["(", "["]
let rightArr = [")", "]"]
let pairValue = ["(":")", "[":"]"]
var stack:MyStack = MyStack<String>()
stack.capacity = orgStr.count
for char in orgStr {
let s = String(char)
if leftArr.contains(s) {
//左边的括号
stack.push(element: s)
}else if rightArr.contains(s) {
//右边的括号
if stack.isEmpty() {
//判断栈是否为空
return false
}else {
let targetValue = pairValue[stack.top()!]
if s == targetValue {
return true
}else {
return false
}
}
}
}
return stack.isEmpty()
}
二。每日气温
根据每日气温列表，请重新生成一个列表，对应位置的输入时你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置0来代替。例如，给定一个列表temperatures = [73,74,75,71,69,72,76,73]，你的输出应该是[1,1,4,2,1,1,0,0]。提示：气温列表长度的范围是[1,30000]。每个气温的值的均为华氏度，都是在[30,100]范围内的整数
func temperature(orgTemArr:[Int]) -> [Int] {
var stack = MyStack<Int>()
stack.capacity = orgTemArr.count
var resultArr:[Int] = Array.init(repeating: 0, count: orgTemArr.count)
for (index, value) in orgTemArr.enumerated() {
if stack.isEmpty() {
//当栈为空
stack.push(element: index)
}else {
//当当前值小于等于栈顶
if value <= orgTemArr[stack.top()!] {
stack.push(element: index)
}else {
while !stack.isEmpty(){
//如果当前值始终大于栈顶，进行对结果数组的赋值。
if value > orgTemArr[stack.top()!] {
let top = stack.top()!
resultArr[top] = index - top
stack.pop()
}else {
break
}
}
}
}
stack.push(element: index)
}
return resultArr
}
print("temper ==== \(temperature(orgTemArr: [73,74,75,71,69,72,76,73]))")
运行结果
image.png
三。爬楼梯
假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定n是一个正整数
func climbStairs(n:Int) -> Int {
if n == 0 {
return 0
}else if n == 1 {
return 1
}else if n == 2 {
return 2
}
return climbStairs(n: n-1)+climbStairs(n: n-2)
}
