基于python实现模拟数据结构模型

模拟栈

• Stack() 创建一个空的新栈。 它不需要参数，并返回一个空栈。

• push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。

• pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。

• peek() 从栈返回顶部项，但不会删除它。不需要参数。 不修改栈。

• isEmpty() 测试栈是否为空。不需要参数，并返回布尔值。

• size() 返回栈中的 item 数量。不需要参数，并返回一个整数。

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())

模拟队列

• Queue() 创建一个空的新队列。 它不需要参数，并返回一个空队列。

• enqueue(item) 将新项添加到队尾。 它需要 item 作为参数，并不返回任何内容。

• dequeue() 从队首移除项。它不需要参数并返回 item。 队列被修改。

• isEmpty() 查看队列是否为空。它不需要参数，并返回布尔值。

• size() 返回队列中的项数。它不需要参数，并返回一个整数。
  

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())

模拟双端队列

同同列相比，有两个头部和尾部。可以在双端进行数据的插入和删除，提供了单数据结构中栈和队列的特性

• Deque() 创建一个空的新deque。它不需要参数，并返回空的deque。

• addFront(item) 将一个新项添加到deque的首部。它需要item参数并不返回任何内容。

• addRear(item) 将一个新项添加到deque的尾部。它需要item参数并不返回任何内容。

• removeFront() 从deque中删除首项。它不需要参数并返回item。deque被修改。

• removeRear() 从deque中删除尾项。它不需要参数并返回item。deque被修改。

• isEmpty() 测试deque是否为空。它不需要参数，并返回布尔值。

• size() 返回deque中的项数。它不需要参数，并返回一个整数。
  

案例：回文检查

回文是一个字符串，读取首尾相同的字符，例如，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

模拟链表

• . is_empty()：链表是否为空

• . length()：链表长度

• . travel()：遍历整个链表

• . add(item)：链表头部添加元素

• . append(item)：链表尾部添加元素

• . insert(pos, item)：指定位置添加元素

• . remove(item)：删除节点

• . search(item)：查找节点是否存在
  

结点对象：

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

来源：https://www.cnblogs.com/Hedger-Lee/p/13071239.html