python数据结构——链表、栈、队列

一、思维梳理：

 二、双向循环链表：

class Node:def __init__(self,data):self.data = dataself.next = Noneself.prev = Noneclass DoubleLink:def __init__(self):self.size = 0self.head = Nonedef is_empty(self):return self.size == 0def add_end(self,data):node = Node(data)if self.is_empty():self.head = nodenode.next = nodenode.prev = nodeelse:q = self.head.prevnode.prev = qnode.next = self.headq.next = nodeself.head.prev = nodeself.size += 1def del_end(self):if self.is_empty():returnelse:if self.size == 1:self.head = Noneelse:q = self.head.prevself.head.prev = q.prevq.prev.next = self.headself.size -= 1def show(self):if self.is_empty():returnelse:q = self.headwhile q.next != self.head:print(q.data,end=" ")q = q.nextprint(q.data,end=" ")print()if __name__ == '__main__':doubleLink = DoubleLink()doubleLink.add_end(10)doubleLink.add_end(20)doubleLink.add_end(30)doubleLink.add_end(40)doubleLink.add_end(50)doubleLink.show()doubleLink.del_end()doubleLink.show()

 结果展示：

10 20 30 40 50 
10 20 30 40 

三、顺序栈：

class Stack:def __init__(self,capacity):self.capacity = capacityself.size = 0self.data = [None]*capacitydef is_empty(self):return self.size == 0def is_full(self):return self.size == self.capacitydef push(self,data):if self.is_full():returnself.data[self.size] = dataself.size += 1def pop(self):if self.is_empty():returnself.size -= 1def top(self):if self.is_empty():returnreturn self.data[self.size-1]def get_size(self):return self.sizedef show(self):for i in range(self.size-1,-1,-1):print(self.data[i],end=" ")print()if __name__ == '__main__':stack = Stack(100)stack.push(10)stack.push(20)stack.push(30)stack.push(40)stack.show()stack.pop()stack.show()

结果展示：

40 30 20 10 
30 20 10 

四、链式栈：

class Node:def __init__(self,data):self.data = dataself.next = Noneclass Stack:def __init__(self):self.size = 0self.top = Nonedef is_empty(self):return self.size == 0def push(self,data):node = Node(data)node.next = self.topself.top = nodeself.size += 1def pop(self):if self.is_empty():returnelse:self.top = self.top.nextself.size -= 1def get_top(self):if self.is_empty():returnreturn self.top.datadef get_size(self):return self.sizedef show(self):if self.is_empty():returnq = self.topwhile q:print(q.data,end=" ")q = q.nextprint()if __name__ == '__main__':stack = Stack()stack.push(10)stack.push(20)stack.push(30)stack.push(40)stack.push(50)stack.push(60)stack.show()stack.pop()stack.show()print(stack.get_top())print(stack.get_size())

结果展示：

60 50 40 30 20 10 
50 40 30 20 10 
50
5