Any programmer, algorithmic or otherwise, needs to have a grasp of data structures. This article has done the algorithm in Python in the most elegant way possible. Don’t ask, just memorize it. Less code, easier to memorize.

Source: github.com/SpikeKing

Chapter 2 stack and queue: parenthesis matching (stack), binary conversion (stack), hot potato (queue), palindrome (double-ended queue), reverse linked list (linked list);

1. Matching parentheses

Parentheses match. Determines whether the parentheses match in the string. When the parenthesis is left, the stack is pushed, and when the parenthesis is right, the stack is unloaded. Finally, the stack is determined to be empty. If it is empty, the parenthesis matches, otherwise, it does not match. A List in Python can act like a stack. The algorithm consists of 14 lines.

def par_checker(symbol_str):
    "" "matching brackets, the list contains the function of the stack append is added, the pop is to remove https://docs.python.org/2/tutorial/datastructures.html line 14: param symbol_str: Symbol string :return: Whether """
    s = list()  # Python lists can implement stack functionality
    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(a):
    print(par_checker('() ()'))
    print(par_checker('((()'))
    print(par_checker('(a)()((()))'))


if __name__ == '__main__':
    test_of_par_checker()
Copy the code

2. Binary conversion

Divide the binary number by base, put it in the queue, and output it in reverse order, which is exactly what the stack does. Add a number to the string. The algorithm consists of 11 lines.

def base_converter(num, base):
    """ Convert binary to other bases :param num: number :param base: base: return: numeric string """
    digs = '0123456789ABCDEF'  # support 16 bits
    base_stack = list()

    while num > 0:
        rem = num % base
        base_stack.append(rem)
        num //= base  # decremented all the way to 0

    res_str = ' '  # convert to 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))
Copy the code

3. Hot potato

Call the roll, call who, circle who, circle the queue, last one out. The algorithm consists of 10 lines.

from queue import Queue


def hot_potato(name_list, num):
    """ Hot potato, loop removal :param name_list: list of names :param num: number of loops :return: last remaining person """
    q = Queue()

    for name in name_list:
        q.put(name)

    while q.qsize() > 1:
        for i in range(num - 1) :# Every time a cycle dies, the last one dies
            live = q.get()
            q.put(live)
        dead = q.get()  # export death
        print('Dead: {}'.format(dead))

    return q.get()


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


if __name__ == '__main__':
    test_of_hot_potato()
Copy the code

4. Palindrome

Whether the output of the head and tail of a queue is equal. The algorithm consists of 12 lines.

from collections import deque


def pal_checker(a_str):
    "" palindrome, double-ended queue :param a_str: Input string :return: Palindrome or not """
    q_char = deque()

    for ch in a_str:
        q_char.append(ch)

    equal = True

    The end condition length of the # while or Bool
    while len(q_char) > 1:
        first = q_char.pop()
        last = q_char.popleft()
        iffirst ! = last: equal =False
            break

    return equal


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


if __name__ == '__main__':
    test_of_pal_checker()
Copy the code

5. List inversion

Prev_node preserves the head node, and next_node, a temporary variable, preserves the node after the current one. The algorithm consists of 8 lines.

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


def reverse_list(node_head):
    """ Reverse list, swap list :param node_head: list head: return: new list head """
    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(a):
    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(a):
    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()
Copy the code

OK, that’s all! Enjoy it!