数据结构-栈

数据结构是计算机存储、组织数据的方式
本文演示代码为Swift语言

栈(Stack)

栈是一种特殊的线性表，只能在数据的一端进行操作

接口设计

/*
* 方法
*/

// 元素的数量 
int size()
// 是否为空
Bool isEmpty()
// 入栈
void push(T element)
// 出栈
T pop()
// 获取栈顶元素
T top()

实现

栈的实现方式可以利用之前讲到过的数据结构,动态数组、链表等，但由于栈的特点是只能从尾部取出元素、出栈等，使用动态数组和链表的复杂度都一样(O(1)级别)

class Stack<T> {
    // 动态数组存储的元素
    private var elements: [T] = Array<T>()
    
    func size() -> Int {
        return self.elements.count
    }
    
    func isEmpty() -> Bool {
        return self.elements.count == 0
    }

    func clear() {
        self.elements.removeAll()
    }
    
    func push(element: T) {
        self.elements.append(element)
    }
    
    func pop() -> T {
        return self.elements.remove(at: self.elements.count-1)
    }
    
    func top() -> T {
        return self.elements[self.elements.count-1]
    }
}

调用：

let stack = Stack<String>()
stack.push(element: "1111")
stack.push(element: "2222")
stack.push(element: "3333")

print("栈顶元素为:\(stack.top())") // 输出3333

let str = stack.pop()
print("出栈一次后的元素为：\(str)") // 输出3333

let str2 = stack.pop()
print("出栈2次后的元素为：\(str2)") // 输出2222

栈的应用场景

前面介绍了栈的实现方式，似乎看起来对于日常开发当中没有那么多用处，但有些特殊场景栈的作用还是非常大，比如浏览器的前进和后退

浏览器的前进后退

在浏览器:

输入jd.com
qq.com
baidu.com
点击后退
点击后退
点击前进
再输入taobao.com

其实浏览器的前进和后退就用到了栈的数据结构，但它用到了两个栈

软件的撤销与恢复

有些画图软件会有撤销(Undo)、恢复(Redo)功能，其实现原理也是利用到了栈的数据结构

算法练习 - 有效的括号

原文:算法-有效的括号:

分析：
题目当中要求算出有效的括号, 注意必须是连在一起就认为是有效，如([)]就被认为是无效，而{[]}就是有效的
解法一：
遍历字符串，利用栈来判断

遇见左字符{([，将左字符入栈
遇见右字符})]
- 如果栈是空的，说明括号无效
- 如果栈不为空，将栈顶字符串出栈，与右字符比较
  - 如果左右不匹配，说明括号无效
  - 如果左右匹配，继续扫描下一个字符
所有字符扫描完毕
- 如果栈是空的，说明括号有效
- 栈不为空，说明括号无效

let stack = Stack<Character>()
func isValid(charString: inout String) -> Bool {
    for ch in charString {
        if ch == "[" || ch == "(" || ch == "{" {
            stack.push(element: ch)
        }
        else { // 题目当中说道 给定一个只包含xxx，注意有一个”只“字
            // 来到这里说明只有右括号
            if stack.isEmpty() {
                return false
            }
            let stackTopChar = stack.pop()
            if stackTopChar == "(" && ch != ")" {
                return false
            }
            if stackTopChar == "[" && ch != "]" {
                return false
            }
            if stackTopChar == "{" && ch != "}" {
                return false
            }
        }
    }
    
    
    return stack.isEmpty()
}
var str = "{[]}"
let v = isValid(charString: &str)
print(v)

解法二：
利用while循环(不推荐，效率非常慢)

func isValid(charString: inout String) -> Bool {
    
    while charString.contains("()")
    || charString.contains("{}")
    || charString.contains("[]") {
        charString = charString.replacingOccurrences(of: "()", with: "")
        charString = charString.replacingOccurrences(of: "[]", with: "")
        charString = charString.replacingOccurrences(of: "{}", with: "")
    }
    
    return charString.count == 0
}
var str = "{[]}"
let valid = isValid(charString: &str)
print(valid)

本文首次发布于孙忠良 Blog, 作者 [@sunzhongliang] , 转载请保留原文链接.

栈(Stack)

接口设计

实现

栈的应用场景

浏览器的前进后退

软件的撤销与恢复

算法练习 - 有效的括号

CATALOG

FEATURED TAGS

FRIENDS