程序员必须掌握的数据结构 2

无论是任何程序员，不论是算法，还是其他，都需要掌握一定的数据结构。本文以最优雅的方式，基于Python，完成算法，不要问，背下来就好。代码量更少，更好背。

源码： github.com/SpikeKing

第2篇 栈与队列：括号匹配(栈)、二进制转换(栈)、烫手的山芋(队列)、回文(双端队列)、反转链表(链表)；

1. 括号匹配

括号匹配，判断字符串中括号是否匹配。当为左括号时入栈，为右括号时出栈，最后，判断栈是否为空，为空则括号匹配，否则不匹配。Python的list就可以实现 栈 的功能。算法共14行。

def par_checker(symbol_str):
    """
    括号匹配，list包含栈的功能
    append是添加，pop是删除
    https://docs.python.org/2/tutorial/datastructures.html
    14行
    :param symbol_str: 符号字符串
    :return: 是否
    """
    s = list()  # python的list可以实现stack功能
    idx = 0
    while idx < len(symbol_str):
        symbol = symbol_str[idx]
        if symbol == '(':
            s.append(symbol)
        elif symbol == ')':
            s.pop()
        idx += 1
    if not s:
        return True
    else:
        return False


def test_of_par_checker():
    print(par_checker('(())'))
    print(par_checker('((()'))
    print(par_checker('(a)()((()))'))


if __name__ == '__main__':
    test_of_par_checker()
复制代码

2. 二进制转换

将二进制数除以base，输入队列中，再倒序输出，恰好是 栈 的功能。将数字添加至字符串中，即可。算法共11行。

def base_converter(num, base):
    """
    将二进制转换为其他进制
    :param num: 数字
    :param base: 基数
    :return: 数字的字符串
    """
    digs = '0123456789ABCDEF'  # 支持16位
    base_stack = list()

    while num > 0:
        rem = num % base
        base_stack.append(rem)
        num //= base  # 递减一直到0

    res_str = ''  # 转换为str
    while base_stack:
        res_str += digs[base_stack.pop()]

    return res_str


if __name__ == '__main__':
    print(base_converter(25, 2))
    print(base_converter(25, 16))
复制代码

3. 烫手的山芋

点名，点到谁，谁出圈，循环使用 队列 ，最后一个出队。算法共10行。

from queue import Queue


def hot_potato(name_list, num):
    """
    烫手的山芋，循环去除
    :param name_list: 名字列表
    :param num: 循环数
    :return: 最后剩下的人
    """
    q = Queue()

    for name in name_list:
        q.put(name)

    while q.qsize() > 1:
        for i in range(num - 1):  # 每次都死一个循环，最后一个死亡
            live = q.get()
            q.put(live)
        dead = q.get()  # 输出死亡
        print('Dead: {}'.format(dead))

    return q.get()


def test_of_hot_potato():
    name_list = ['Bill', 'David', 'Susan', 'Jane', 'Kent', 'Brad']
    num = 3
    print(hot_potato(name_list, num))


if __name__ == '__main__':
    test_of_hot_potato()
复制代码

4. 回文

双端队列，队首和队尾的输出是否相等。算法共12行。

from collections import deque


def pal_checker(a_str):
    """
    回文，双端队列
    :param a_str: 输入字符串
    :return: 是否回文
    """
    q_char = deque()

    for ch in a_str:
        q_char.append(ch)

    equal = True

    # while的终止条件长度或者Bool
    while len(q_char) > 1:
        first = q_char.pop()
        last = q_char.popleft()
        if first != last:
            equal = False
            break

    return equal


def test_of_pal_checker():
    print(pal_checker('lsdkjfskf'))
    print(pal_checker('radar'))


if __name__ == '__main__':
    test_of_pal_checker()
复制代码

5. 链表反转

链表反转，prev_node保留头结点，临时变量next_node，保留当前结点之后的结点。算法共8行。

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next_node = None


def reverse_list(node_head):
    """
    链表逆序，交换链表
    :param node_head: 链表头
    :return: 新的链表的头结点
    """
    prev_node = None

    while node_head:
        next_node = node_head.next_node
        node_head.next_node = prev_node
        prev_node = node_head
        node_head = next_node

    return prev_node


def init_list():
    n1 = Node(1)
    n2 = Node(2)
    n3 = Node(3)
    n4 = Node(4)
    n5 = Node(5)
    n1.next_node = n2
    n2.next_node = n3
    n3.next_node = n4
    n4.next_node = n5
    return n1


def show_list(node_head):
    head = node_head
    while head:
        print(head.data, end=' ')
        head = head.next_node


def test_of_reverse_list():
    head_node = init_list()
    show_list(head_node)
    print()
    head_node = reverse_list(head_node)
    show_list(head_node)


if __name__ == '__main__':
    test_of_reverse_list()
复制代码

OK, that's all! Enjoy it!