模拟栈
class Stack():
def __init__(self):
self.items = []
def push(self,item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return len(self.items) - 1
def isEmpty(self):
return self.items == []
def size(self):
return len(self.items)
s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.pop())
print(s.pop())
print(s.pop())
print(s.isEmpty()) 模拟队列
class Queue():
def __init__(self):
self.items = []
def enqueue(self,item):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def isEmpty(self):
return self.items == []
def size(self):
return len(self.items)
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())
print(q.dequeue())
print(q.dequeue()) 案例：烫手山芋
烫手山芋游戏介绍：6个孩子围城一个圈，排列顺序孩子们自己指定。第一个孩子手里有一个烫手的山芋，需要在计时器计时1秒后将山芋传递给下一个孩子，依次类推。规则是，在计时器每计时7秒时，手里有山芋的孩子退出游戏。该游戏直到剩下一个孩子时结束，最后剩下的孩子获胜。请使用队列实现该游戏策略，排在第几个位置最终会获胜。
准则：队头孩子的手里永远要有山芋。
queue = Queue()
kids = ['A','B','C','D','E','F']
#将六个孩子添加到队列中，A是队头位置的孩子
for kid in kids:
queue.enqueue(kid)
while queue.size() > 1:
#在7秒之内山芋会被传递6次
for i in range(6):
kid = queue.dequeue()
queue.enqueue(kid)
queue.dequeue()
print('获胜者为：',queue.dequeue()) 模拟双端队列
同同列相比，有两个头部和尾部。可以在双端进行数据的插入和删除，提供了单数据结构中栈和队列的特性
案例：回文检查
回文是一个字符串，读取首尾相同的字符，例如，radar toot madam。
def isHuiWen(s):
ex = True
q = Dequeue()
# 将字符串的每一个字符添加到双端队列中
for ch in s:
q.addFront(ch)
for i in range(len(s) // 2):
font = q.removeFront()
rear = q.removeRear()
if font != rear:
ex = False
break
return ex 模拟链表
结点对象：
class Node():
def __init__(self,item):
self.item = item
self.next = None 链表对象：
class Link():
#构建出一个空的链表
def __init__(self):
self._head = None #永远指向链表中的头节点
#想链表的头部插入节点
def add(self,item):
node = Node(item)
node.next = self._head
self._head = node
def travel(self):
cur = self._head
#链表为空则输出‘链表为空'
if self._head == None:
print('链表为空！')
while cur:
print(cur.item)
cur = cur.next
def isEmpty(self):
return self._head == None
def length(self):
cur = self._head
count = 0
while cur:
count += 1
cur = cur.next
return count
def search(self,item):
cur = self._head
find = False
while cur:
if cur.item == item:
find = True
break
cur = cur.next
return find
def append(self,item):
node = Node(item)
#链表为空的情况
if self._head == None:
self._head = node
return
cur = self._head #头节点
pre = None #cur的前一个节点
while cur:
pre = cur
cur = cur.next
pre.next = node
def insert(self,pos,item):
node = Node(item)
if pos < 0 or pos > self.length():
print('重新给pos赋值！！！')
return
cur = self._head
pre = None
for i in range(pos):
pre = cur
cur = cur.next
pre.next = node
node.next = cur
def remove(self,item):
cur = self._head
pre = None
if self._head == None:#链表为空
print('链表为空，没有可删除的节点！！1')
return
#删除的是第一个节点的情况
if self._head.item == item:
self._head = self._head.next
return
#删除的是非第一个节点的情况
while cur:
pre = cur
cur = cur.next
if cur.item == item:
pre.next = cur.next
return 以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持python博客。
Powered By python教程网 鲁ICP备18013710号
python博客 - 小白学python最友好的网站!