数据结构与算法学习笔记 (二) 栈 链表 队列 树 堆 图 并查集

学习数据结构与算法的目的：
1.掌握底层 coding
2.从顶层宏观的去观察一种数据结构的各种操作 推荐 一个动态可视化网站 Visualgo

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。栈允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。由于堆叠数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。栈也称为后进先出表。

栈的复杂度

栈属于常见的一种线性结构，对于进栈和退栈而言，时间复杂度都为 O(1)

栈的基本功能实现 class Stack(object): #创建一个Stack类 def __init__(self, limit=10): self.stack = [] #存放元素 self.limit = limit #栈容量极限 def push(self, data): #push进栈 判断栈是否溢出 if len(self.stack) >= self.limit: print(\'StackOverflowError\') pass self.stack.append(data) def pop(self): #pop出栈 if self.stack: return self.stack.pop() else: raise IndexError(\'pop from an empty stack\') #空栈不能被弹出 def peek(self): #查看栈的最上面的元素 if self.stack: return self.stack[-1] def is_empty(self): #判断栈是否为空 return not bool(self.stack) def size(self): #栈的大小 return len(self.stack)

给个例子，根据stack数据结构的特点，检查括号是否完全匹配

class Stack(object): #创建一个Stack类 def __init__(self, limit=10): self.stack = [] #存放元素 self.limit = limit #栈容量极限 def push(self, data): #push进栈 判断栈是否溢出 if len(self.stack) >= self.limit: print(\'StackOverflowError\') pass self.stack.append(data) def pop(self): #pop出栈 if self.stack: return self.stack.pop() else: raise IndexError(\'pop from an empty stack\') #空栈不能被弹出 def peek(self): #查看栈的最上面的元素 if self.stack: return self.stack[-1] def is_empty(self): #判断栈是否为空 return not bool(self.stack) def size(self): #栈的大小 return len(self.stack) def balanced_parentheses(parentheses): stack = Stack(len(parentheses)) for parenthesis in parentheses: if parenthesis == \'(\': stack.push(parenthesis) elif parenthesis == \')\': if stack.is_empty(): return False stack.pop() return stack.is_empty() if __name__ == \'__main__\': examples = [\'((()))\', \'((())\', \'(()))\'] print(\'Balanced parentheses demonstration:\n\') for example in examples: print(example + \':\' + str(balanced_parentheses(example))) #输出 ((())):True ((()):False (())):False 链表

链表(linked_list)是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表。
链表通过将链点 i 与其邻居链点 i+1 通过指针相关联，从索引 0 到索引 N-1 对链点进行排序。链表分为单链表和双链表两种。
单链表的具体功能是如何实现的。

#单链表的具体功能 class Node: #创建一个 Node 的类，作为基础数据结构：链点，并初始化对应的内参 def __init__(self, data): self.data = data #表示对应的元素值 self.next = None #表示下一个链接的链点 class Linked_List: #创建Linked_List类 并初始化对象的内参 def __init__(self): self.head = None #表示链表的头部元素 def initlist(self, data_list): #链表初始化函数 self.head = Node(data_list[0]) #创建头结点 temp = self.head for i in data_list[1:]: #逐个为data内的数据创建结点 建立链表 node = Node(i) temp.next = node temp = temp.next def is_empty(self): if self.head.next == None: #判断链表是否为空 print("Linked_list is empty") return True else: return False def insert(self, key, value): #链表中任意位置添加一个 item 元素 链表插入数据函数 if key<0 or key>self.get_length()-1: print("insert error") temp = self.head i = 0 while i<=key: #遍历找到索引值为 key 的结点 在其后面插入结点 pre = temp temp = temp.next i = i+1 node = Node(value) pre.next = node node.next = temp def remove(self, key): #链表删除数据函数 if key<0 or key>self.get_length()-1: print("insert error") i = 0 temp = self.head while temp != None: #遍历找到索引值为 key 的结点 pre = temp temp = temp.next i = i+1 if i==key: pre.next = temp.next temp = None return True pre.next = None def get_length(self): #获取链表的长度 temp = self.head #临时变量指向队列头部 length = 0 #计算链表的长度变量 while temp != None: length = length +1 temp = temp.next return length def print_list(self): #遍历链表，并将元素依次打印出来 print("linked_list:") temp = self.head while temp is not None: print(temp.data) temp = temp.next def reverse(self): #将链表反转 prev = None current = self.head while current: next_node = current.next current.next = prev prev = current current = next_node self.head = prev 复杂度