数据结构—栈的简单应用

最近决心重拾数据结构，从头深入学习理解一遍，由于最近使用最多语言是lua，因此以下示例皆使用lua语言

栈：它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
后入先出是它的特点

local stack = {}

stack.init = function(self)
    self.data = {}
end

stack.empty = function(self)
    self.data = {}
end

stack.isEmpty = function(self)
    if self:length() == 0 then
        return true
    else
        return false
    end
end

stack.destory = function(self)
    self.data = {}
end

stack.length = function(self)
    return #self.data
end

stack.getTop = function(self)
    return self.data[#self.data]
end

stack.push = function(self, size)
    table.insert(self.data, size)
end

stack.pop = function(self)
    local data_size = #self.data
    local ele = self.data[data_size]
    table.remove(self.data, data_size)
    return ele
end

return stack

应用举例：
1、数制转换
十进制N和其他d进制的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：
N=（N div d）* d + （N mod d） -- div：整除 mod：求余
只要迭代地 X除以h，直到商为0，将每次得到的余数倒序排列，这便是短除法的原理
实现：

local function binary_conversion(N, d)
    while N/d ~= 0 do
        stack.push(stack, math.fmod(N,d))
        N = math.floor(N / d)
    end

    local str = ""
    for i = stack:length(),1,-1 do
        str = str .. stack:pop()
    end
    return str
end

2、括号匹配的检测
假设表达式中允许包含三种括号，其嵌套顺序随意，检验括号是否匹配可用”期待的急迫程度“这个概念来描述，例如考虑下列括号序列
[ ( [ ] [ ] ) ]
12345678
当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号只能暂时靠边，而迫切等待与第二个括号匹配的第七个括号”）“的出现，类似的，因等来的第三个括号"["，其期待匹配的程度较第二个更紧迫，第二个也只能靠边。再接受了第四个括号后，第三个括号的期待得到满足，消解之后，第二个成为最紧迫的。。。以此类推，可见，这个处理过程与栈的特点相吻合

local function check_brackets(content)
    local length = string.len(content)
    for i=1,length do
        local bite = string.sub(content, i ,i)
        if is_left(bite) then
            stack:push(bite)
        elseif is_right(bite) then
            if not stack:isEmpty() then
                local top = stack:getTop()
                if is_match(top ,bite) then
                    stack:pop()
                else
                    return false, i
                end
            else
                return false,i
            end
        end
    end
    return stack:isEmpty()
end

最后编辑于：2020.05.06 00:48:33