一、思维导图
二、双向循环链表的判空、尾插、遍历(反向)、尾删
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prior = None
class circularDoublyLinkedList():
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def isEmpty(self):
return self.size == 0
def add_tail(self, data):
node = Node(data)
if self.isEmpty():
self.head = node #
node.next = node # 循环链表特性
node.prior = None # 双向链表特性(该行可有可无)
self.size += 1
else:
i = 1
q = self.head
while i < self.size: # 找到最后一个节点
q = q.next
i += 1
node.prior = q # 双向链表
node.next = self.head # 循环链表
self.head.prior = node # 双向链表
q.next = node
self.size += 1
def show(self):
if self.isEmpty():
print("遍历西巴")
return
else:
q = self.head.prior
while q != self.head:
print(f"{q.data}", end="<--")
q = q.prior
print(f"{q.data}", end="<--") # 此时已经到了尾部，但尾部节点直接跳出了循环没有打印，这里补上
print()
def delete_tail(self):
if self.isEmpty():
print("无需删除")
return
else:
q = self.head
i = 1
while i < self.size-1:
q = q.next
i += 1
q.next = self.head
self.head.prior = q
self.size-=1
if __name__ == '__main__':
linked_list = circularDoublyLinkedList()
linked_list.add_tail(1)
linked_list.add_tail(2)
linked_list.add_tail(3)
linked_list.add_tail(4)
linked_list.show()
linked_list.delete_tail()
linked_list.show()
linked_list.delete_tail()
linked_list.show()
linked_list.delete_tail()
linked_list.show()
linked_list.delete_tail()
linked_list.delete_tail()
linked_list.show()
三、顺序栈
class Stack:
def __init__(self, capacity=10):
self.data = [None] * capacity
self.size = 0
self.capacity = capacity # 最大容量
def isEmpty(self):
return self.size == 0
def isFull(self):
return self.size == self.capacity
def push(self, value):
if self.isFull():
print("stack is full")
return False
else:
i = self.size - 1
while i >= 0:
self.data[i + 1] = self.data[i]
i -= 1
self.data[0] = value
self.size+=1
def pop(self):
if self.isEmpty():
print("stack is empty")
return None
else:
i = 0
while i < self.size-1:
self.data[i] = self.data[i+1]
i+=1
self.data[self.size-1] = None
self.size-=1
def expend(self):
print("扩容")
self.capacity = int(self.capacity * 1.5) # 定义扩容量
print(f"新容量为：{int(self.capacity)}")
self.backup_data = self.data
self.data = [None] * int(self.capacity) # 重置并扩容
for i in range(self.size): # 将备份好的列表逐步加入回重置并扩容后的列表
self.data[i] = self.backup_data[i]
def show(self):
if self.isEmpty():
print("数据表为空")
return
else:
i = 0
while i < self.size:
print(self.data[i],end=" ")
i+=1
print()
def first_value(self):
return self.data[0]
if __name__ == '__main__':
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.show()
print("first_value is ------>",stack.first_value())
stack.pop()
stack.show()
stack.pop()
stack.show()
stack.pop()
stack.show()
stack.pop()
stack.pop()
stack.show()
四、链式栈
class Node():
def __init__(self, data):
self.data = data
self.next = None
class Linked_Stack():
def __init__(self):
self.size = 0
self.head = None
def isEmpty(self):
return self.size == 0
def push(self, data):
node = Node(data)
if self.isEmpty():
self.head = node
self.size += 1
else:
node.next = self.head
self.head = node
self.size += 1
def pop(self):
if self.isEmpty():
print("Stack is Empty")
else:
self.head = self.head.next
self.size -= 1
def first_value(self):
return self.head
def show(self):
if self.isEmpty():
return
else:
q = self.head
while q:
print(q.data, end="-->")
q = q.next
print()
if __name__ == '__main__':
link_stack = Linked_Stack()
link_stack.push(1)
link_stack.show()
link_stack.push(2)
link_stack.push(3)
link_stack.show()
link_stack.pop()
link_stack.show()
link_stack.pop()
link_stack.show()
link_stack.pop()
link_stack.show()
link_stack.pop()
link_stack.show()
五、顺序队列
class Queue:
def __init__(self, capacity=10):
self.data = [None] * capacity
self.size = 0
self.capacity = capacity
# 判空
def isEmpty(self):
return self.size == 0
# 入队
def push(self, data):
i = self.size - 1
while i >= 0:
self.data[i + 1] = self.data[i]
i -= 1
self.data[0] = data
self.size += 1
def pop(self):
if self.isEmpty():
print("Queue is empty")
return None
else:
self.data[self.size - 1] = None
self.size -= 1
# 遍历
def show(self):
if self.isEmpty():
print("数据表为空")
return
else:
i = 0
while i < self.size:
print(self.data[i], end=" ")
i += 1
print()
if __name__ == '__main__':
queue = Queue()
queue.push(1)
queue.show()
queue.push(2)
queue.show()
queue.push(3)
queue.show()
queue.push(4)
queue.show()
queue.pop()
queue.show()
queue.pop()
queue.show()
queue.pop()
queue.show()
queue.pop()
queue.pop()
queue.show()