from collections import deque# Initializing a queueq =deque()# Adding elements to a queueq.append('a')q.append('b')q.append('c')print("Initial queue")print(q)# Removing elements from a queueprint("\nElements dequeued from the queue")print(q.popleft())print(q.popleft())print(q.popleft())print("\nQueue after removing elements")print(q)# Uncommenting q.popleft()# will raise an IndexError# as queue is now empty
常见的面试问题：
反转队列的前 k 个元素
使用链表实现队列
使用队列实现栈
3、栈
用 list 实现，push 操作使用 append() 方法，pop 操作使用 pop()
stack = []# append() function to push# element in the stackstack.append('a')stack.append('b')stack.append('c')print('Initial stack')print(stack)# pop() function to pop# element from stack in# LIFO orderprint('\nElements popped from stack:')print(stack.pop())print(stack.pop())print(stack.pop())print('\nStack after elements are popped:')print(stack)# uncommenting print(stack.pop())# will cause an IndexError# as the stack is now empty
常见的面试问题：
使用栈实现一个队列
使用栈计算后缀表达式
使用栈的获取第二大元素
使用栈创建 main 函数
4、链表
链表主要用于创建高级数据结构，如图和树，或者用于需要经常在整个结构中添加/删除元素的任务。
classNode:def__init__(self,dataval=None): self.dataval = dataval self.nextval =NoneclassSLinkedList:def__init__(self): self.headval =Nonelist1 =SLinkedList()list1.headval =Node("Mon")e2 =Node("Tue")e3 =Node("Wed")# Link first Node to second nodelist1.headval.nextval = e2# Link second Node to third nodee2.nextval = e3
常见的面试问题：
打印给定链表的中间元素
从排序的链表中删除重复的元素
检查单链表是否为回文
合并 k 排序链表
查找两个链表的交点
5、循环链表
标准链表的主要缺点是必须始终从 Head 节点开始。循环链表通过将 Tail 节点的空指针替换为指向 Head 节点的指针来修复这个问题。
这种设置的优点是可以从任何节点开始遍历整个列表。
常见的面试问题：
检测链表中的循环
反转循环链表
以给定大小的组来反转循环链表（Reverse circular linked list in groups of a given size）
classNode:def__init__(self,data): self.left =None self.right =None self.data = datadefinsert(self,data):# Compare the new value with the parent nodeif self.data:if data < self.data:if self.left isNone: self.left =Node(data)else: self.left.insert(data)elif data > self.data:if self.right isNone: self.right =Node(data)else: self.right.insert(data)else: self.data = data# Print the treedefPrintTree(self):if self.left: self.left.PrintTree()print( self.data),if self.right: self.right.PrintTree()# Use the insert method to add nodesroot =Node(12)root.insert(6)root.insert(14)root.insert(3)root.PrintTree()
常见的面试问题：
检查两个二叉树是否相同
实现二叉树的层次序遍历
打印二叉查找树的周长
沿着一条路径求所有节点的和
连接一个二叉树的所有兄弟节点
7、图
有向图 & 无向图
当用纯文本编写时，图有一个顶点和边的列表：
V ={a, b, c, d, e}E ={ab, ac, bd, cd, de}
在 Python 中，图最好使用字典来实现，每个顶点的名称作为键，边列表作为值。
# Create the dictionary with graph elementsgraph ={"a": ["b","c"],"b": ["a","d"],"c": ["a","d"],"d": ["e"],"e": ["d"]}# Print the graphprint(graph)
常见的面试问题：
检测有向图中的循环
在有向图中查找父节点
计算无向图中的边数
检查两个顶点之间是否存在路径
求两个顶点之间的最短路径
8、哈希表
（这个图画的很棒，于是偷过来了）
import pprintclassHashtable:def__init__(self,elements): self.bucket_size =len(elements) self.buckets = [[] for i inrange(self.bucket_size)] self._assign_buckets(elements)def_assign_buckets(self,elements):for key, value in elements:# calculates the hash of each key hashed_value =hash(key)# positions the element in the bucket using hash index = hashed_value % self.bucket_size# adds a tuple in the bucket self.buckets[index].append((key, value))defget_value(self,input_key): hashed_value =hash(input_key) index = hashed_value % self.bucket_size bucket = self.buckets[index]for key, value in bucket:if key == input_key:return(value)returnNonedef__str__(self):# pformat returns a printable representation of the objectreturn pprint.pformat(self.buckets)if__name__=="__main__": capitals = [ ('France','Paris'), ('United States','Washington D.C.'), ('Italy','Rome'), ('Canada','Ottawa') ] hashtable =Hashtable(capitals)print(hashtable)print(f"The capital of Italy is {hashtable.get_value('Italy')}")
# first stage
FROM python:3.8 AS builder
COPY requirements.txt .
# install dependencies to the local user directory (eg. /root/.local)
RUN pip install --user -r requirements.txt
# second stage
FROM python:3.8-slim
WORKDIR /code
# copy only the dependencies that are needed for our application and the source files
COPY --from=builder /root/.local /root/.local
COPY ./src .
# update PATH
ENV PATH=/root/.local:$PATH
# make sure you include the -u flag to have our stdout logged
CMD [ "python", "-u", "./main.py" ]
