数据结构栈(数据结构栈和队列知识点总结)

1 什么是栈2 栈的实现

2.1 栈的抽象类型2.2 栈的实现 3 栈的应用实例

3.1 括号匹配

3.1.1 只判断一种括号是否匹配3.1.3 判断多种括号是否匹配 3.2 十进制数的转换

3.2.1 十进制转二进制3.2.2 十进制数转成任一进制数

栈是常见的数据结构之一，是一种有序集合，又称为“下堆栈”，添加和移除总是发生在同一端（栈顶），栈的另一端即为”栈底“。

栈中的元素离栈底越近，表示其在栈中的时间越长。栈中先添加的元素最后被移除，其遵循last-in-first-out (LIFO)原则。

此处采用Python语言实现栈

class Stack():

    # initialize a Stack, define a list as stack
    def __init__(self):
        self.items = []

    # isEmpty
    def isEmpty(self):
        return self.items == []

    # push a new item onto the Stack
    def push(self, item):
        self.items.append(item)

    # pop a new item from the Stack
    def pop(self):
        self.items.pop()

    # peek a item of the Stack top
    def peek(self):
        return self.items[len(self.items)-1]

    # length of the 栈
    def size(self):
        return len(self.items)

测试：

if __name__ == "__main__":
    s = Stack()
    print('the length of the stack', s.size())
    # push
    s.push(2)
    print('the length of the stack', s.size())
    s.push(3)
    s.push(4)
    print('the length of the stack', s.size())

    # pop
    s.pop()
    print('the length of the stack', s.size())

    # retuen the elm of top
    i = s.peek()
    print('the value of the stack top', i)
    print('the length of the stack', s.size())

结果：

the length of the stack 0
the length of the stack 1
the length of the stack 3
the length of the stack 2
the value of the stack top 3
the length of the stack 2

思路：遇到左括号就将左括号压栈，遇到右括号就对栈进行出栈操作，若栈不为空则不匹配。

def parChecker(symbleString):
    s = Stack()
    index = 0
    flag= True
    while index < len(symbleString) and flag:
        if symbleString[index] == '(':
        # 将左括号压入栈
            s.push(symbleString[index])
        elif s.isEmpty():
            flag= False
        else:
            s.pop()
        index = index + 1
    if flag and s.isEmpty():
        print(symbleString, "匹配")
    else:
        print(symbleString, "不匹配")

测试：

if __name__ == '__main__':
    string = '(())'
    parChecker(string)

结果：

(()) 匹配

思路：遇到左括号就将左括号压栈，遇到右括号就判断其是否与栈顶元素属于同一类的左括号，若不是则不匹配，若栈不为空则不匹配。

def parChecker(symbleString):
    s = Stack()
    index = 0
    flag = True
    while index < len(symbleString) and flag :
        symble = symbleString[index]
        if symble in '{[(':
        # 将左括号压栈
            s.push(symble)
        elif s.isEmpty():
            flag = False
        else:
            vt = s.pop()
            if not match(vt, symble):
            # 判断右括号是否与栈顶元素匹配
                flag = False
        index = index + 1
    if flag and s.isEmpty():
        print(symbleString, "匹配")
    else:
        print(symbleString, "不匹配")
        
def match(top, symble):
    left = '([{'
    rigth = ')]}'
    # 如果left的索引与 right的索引相同，返回True
    return left.index(top) == rigth.index(symble)

测试：

if __name__ == '__main__':
    symbleString = '{{[()][]()}}'
    parChecker(symbleString)

结果：

{{[()][]()}} 匹配

思路：十进制数除以2后将余数压栈

def divideBy2(number):
    s = Stack()
    result = ''
    while number > 0:
        re = number % 2
        s.push(re)
        number = number >> 1
    # print result
    while not s.isEmpty():
        result = result + str(s.pop())
    return result

思路：与十进制转二进制思路相同。要注意 转16进制时，10 到15用ABCDEF表示。

def divideBybase(number, base):
    '''
    十进制转成任意进制数
    :param number: 十进制数
    :param base: 基数
    '''
    s = Stack()
    result = ''
    digits = '0123456789ABCDEF'
    while number > 0:
        re = number % base
        s.push(re)
        number = number // base

    while not s.isEmpty():
        result = result + digits[s.pop()]
    return result

测试：

if __name__ == "__main__":
    number = 1000
    base1 = 8
    base2 = 16
    print(number, ' --2--> ',  divideBy2(number))
    print(number, ' --8--> ', divideBybase(number, base1))
    print(number, ' --16--> ', divideBybase(number, base2))

结果：

1000  --2-->  1111101000
1000  --8-->  1750
1000  --16-->  3E8