数据结构 -- 栈 stack
特征: 先进后出
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): #出栈 修改 if not self.isEmpty(): # not True return self.items.pop() def isEmpty(self): #是否为空 return self.items == [] #返回布尔值 def peek(self): # 栈顶值 数据还在栈里面 不修改 return self.items[-1] def size(self): #栈里面一共有多少数字 return len(self.items) stack = Stack() stack.push(1) stack.push(2) stack.push(3) # print(stack.pop()) # print(stack.pop()) # print(stack.pop()) # print(stack.peek()) print(stack.size())
s = Stack() #模拟浏览器回退按钮 def getRequest(url): s.push(url) def showCurrentPage(): print(s.pop()) def back(): return s.pop() getRequest('www.1.com') getRequest('www.2.com') getRequest('www.3.com') showCurrentPage() print(back()) print(back()) -- 下面是结果 -- www.3.com www.2.com www.1.com
数据结构 -- 队列 queue
特征: 先进先出,后进后出
案例: 20台电脑公用一个打印机,排队打印的情况
Queue() 创建一个空的新队列。 它不需要参数,并返回一个空队列。 enqueue(item) 将新项添加到队尾。 它需要 item 作为参数,并不返回任何内容。 dequeue() 从队首移除项。它不需要参数并返回 item。 队列被修改。 isEmpty() 查看队列是否为空。它不需要参数,并返回布尔值。 size() 返回队列中的项数。它不需要参数,并返回一个整数。 # 队列 队尾 0 = = = = = -1> 对头 class Queue(): def __init__(self): self.items = [] def enqueue(self,item): #进队列 修改 self.items.insert(0,item) def dequeue(self): #出队列 修改了队列 if not self.isEmpty(): return self.items.pop() def isEmpty(self): return self.items == [] def size(self): #个数 元素 return len(self.items) def travel(self): #遍历 return self.items q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) print(q.travel()) print(q.dequeue()) print(q.dequeue()) print(q.dequeue())
例子 : 烫手的山芋
数据结构 - 双端队列 Deque double-ended queue
优缺点: (尽管双端队列看起来似乎比栈和队列更灵活,但实际上在应用程序中远不及栈和队列有用)
- 同同列相比,有两个头部和尾部。可以在双端进行数据的插入和删除,提供了单数据结构中栈和队列的特性
- Deque() 创建一个空的新 deque。它不需要参数,并返回空的 deque。
- addFront(item) 将一个新项添加到 deque 的首部。它需要 item 参数 并不返回任何内容。
- addRear(item) 将一个新项添加到 deque 的尾部。它需要 item 参数并不返回任何内容。
- removeFront() 从 deque 中删除首项。它不需要参数并返回 item。deque 被修改。
- removeRear() 从 deque 中删除尾项。它不需要参数并返回 item。deque 被修改。
- isEmpty() 测试 deque 是否为空。它不需要参数,并返回布尔值。
- size() 返回 deque 中的项数。它不需要参数,并返回一个整数。
class Deque(): def __init__(self): self.items = [] def addFront(self,item): #进队首 self.items.append(item) #追加 def addRear(self,item): #队尾 self.items.insert(0,item) #插入0 位置 def isEmpty(self): #是否空 return self.items == [] #布尔值 def removeFront(self): #出队首 if not self.isEmpty(): return self.items.pop() def removeRear(self): #出队尾 if not self.isEmpty(): return self.items.pop(0) #pop 0位置的 def size(self): #个数 return len(self.items) #长度 # 回文检查 abccba def huiwen(s): q = Deque() for ch in s: q.addFront(ch)
while q.size()>1: if q.removeFront() != q.removeRear(): return False return True print(huiwen('abbba'))