栈
概念：栈是一种特殊的线性表，保存一组元素的集合，插入和删除只能在尾部操作
其特点：
1.栈顶允许插入（入栈）和删除（出栈），另一部分为栈底
2.栈具有后进先出的特点
栈的创建
python中没有内置栈的实现，需要自己手动实现栈的概念，一般可以直接用list
实现：栈的底层其实就是list，通过list来实现栈
class Stack():
def __init__(self):
self.data = list()
#len():返回栈中元素的个数，方法重写来实现
def size(self):
return len(self.data)
#is_empty()：判断栈是否为空
def is_empty(self):
return self.data == []
#push():向栈中添加元素
def push(self, data):
self.data.append(data)
#peek():获取栈顶元素：
def peek(self):
return self.data[len(self.data) - 1]
#pop():删除栈顶元素,并返回
def pop(self):
return self.data.pop()
if __name__ == '__main__':
stack = Stack()
stack.push("a")
stack.push("b")
stack.push("c")
length = stack.size()
print(length)
data = stack.pop()
print(data)
print(stack.peek())
flag = stack.is_empty()
print(flag)
栈常用方法：python中没有栈的内置方法，也就没有相关方法，不过根据栈的概念，我们可以用list中的方法实现栈的常用方法，参考list章节
队列
概念：同栈不同，python中的内置模块，主要有四种类型的队列：Queue, LifoQueue（后进先出队列）, PriorityQueue，dequeue（双向队列）
Queue：先进先出队列，队尾插入，队首删除元素
- Queue的创建：需要导queue这个包
#创建一个可扩容的队列
q = Queue()
#创建一个size为10的队列
q1 = Queue(10)
#put():队列中插入元素
q.put("a")
q.put("b")
#get()：获取队首元素，并从队列中删除此元素
q.get()
print(q.qsize())
while q.empty() == False:
print("q中的元素是:", q.get())
#qsize()：获取队列的size
print("q的size是:", q.qsize())
print("q1的size是： ", q1.qsize())
#q.empty()：判断队列是否为空
print(q1.empty())
队列的常用方法
| 方法名 | 作用 | 返回值 |
|---|---|---|
| put(item, block=True, timeout=None) | 向队列中插入元素，在timeout范围内，若队列有空位则插入，不然超时报full异常，若后两个参数省略，则不会报异常 | 无返回值 |
| put_nowait() | 相当于put()，插入元素满了会报异常 | 无返回值 |
| get(block=True, timeout=None) | 删除队首元素，在指定time内，不然会报empt一场 | 返回删除的元素 |
| Queue.get_nowait() | 同get(),相当于timeout=False,若队列为空时会报异常 | 无返回 |
| qsize() | 获取队列的大小 | 返回队列大小 |
| empty() | 判断队列是否为空 | 返回bool |
| full() | 判读队列是否满了 | 返回bool |
| task_done() | ||
| join() |
- put():插入元素,省略后两个参数，此时队列满了继续插入元素不会报异常
#创建一个size为3的队列
q = Queue(3)
q.put("a")
q.put("b")
q.put("c")
while not q.empty():
print(q.get())
print(q.full())
#创建一个size为3的队列
q = Queue(3)
q.put("a")
q.put("b")
q.put("c")
#此时不会报异常
q.put("m")
image.png
- put(item,black=Ture,timeout=None):队列满了，继续插入元素会报异常
#创建一个size为3的队列
q = Queue(3)
q.put("a")
q.put("b")
q.put("c")
q.put("d",block=True,timeout=2)
- put_nowait():插入元素，插满了会报异常
q = Queue(3)
q.put("a")
q.put("b")
q.put("c")
q.put_nowait("d")
- get()：删除队首元素并返回
#创建一个size为3的队列
q = Queue(3)
q.put("a")
q.put("b")
q.put("c")
#不带参数的get()
q.get()
q.get()
q.get()
print(q.qsize())
#带参数的get()
q.get(block=True,timeout=2)
#get_nowait()
q.get_nowait()
*LifoQueue：后进先出队列，在队尾进行插入，在队尾进行删除
"""
LifoQueue():后进先出队列
"""
lq = LifoQueue()
lq.put("a")
lq.put("b")
while not lq.empty():
print(lq.get())
PriorityQueue:优先级队列，按照优先级来取元素，元素以元祖形式插入，当两个元素优先级一致时，按照排序字段进行排序（从小到大），从而能快速获取最大值最小值
"""
PriorityQueue():优先级队列，按照元祖插入元素，元祖第一位为优先级
"""
pq = PriorityQueue()
pq.put((1, 9))
pq.put((1, 9, 2))
pq.put((1, 8))
pq.put((2, 0))
while not pq.empty():
print(pq.get())
优先级比较不出，会报错（字典，不同类型的元素）
pq = PriorityQueue()
#优先级一样的元素，无法比较会报错
pq.put((1, {"k":1}))
pq.put((1,{"1":1}))
while not pq.empty():
print(pq.get())
pq = PriorityQueue()
pq.put(('a', 9))
pq.put((1, 9, 2))
pq.put((1, 8))
pq.put((2, 0))
#
while not pq.empty():
print(pq.get())
双向队列：
与以上队列不同的是，双向队列是python的collections中的deque类,具有队列和栈的属性，可以从队头插入删除元素，也可以从队尾插入删除元素[拥有和list基本一样的方法]
- 双向队列的创建
"""
双向队列deque：具有队列和栈的双属性，可以任意从队头队尾插入删除元素
"""
#[]可以省略，可见deque其实底层就是list,所以和list中某些方法的用法一致
dq = deque([])
dq1 = deque()
双向队列常用方法
| 方法名 | 作用 | 返回值 |
|---|---|---|
| append(var) | 插入元素 | 无返回值 |
| appendleft(var) | 向队头插入元素 | 无返回 |
| extend([var1, var2,...]) | 插入一组元素 | 无返回值 |
| extendleft([var1, var2,...]) | 向队头插入元素 | 无返回 |
| insert(index, var) | 向指定位置插入元素 | 无返回 |
| remove(var) | 删除指定var | 无返回值 |
| pop() | 删除队尾元素 | 返回删除的元素 |
| clear() | 清空队列 | 无返回 |
| popleft() | 删除队头元素 | 返回删除的元素 |
| remove(var) | 删除指定元素 | 无返回值 |
| copy() | 拷贝当前队列 | 返回新的队列 |
| count(var) | 计算当前var的个数，不存在返回0 | 返回个数 |
| reverse() | 反转队列，在原队列上操作 | 无返回值 |
| rotate(num) | 将队尾num个元素取出并放置队头 | 无返回值 |
- apend(var):插入元素，无返回值
dq = deque()
dq.append("a")
print(dq)
- appendleft(var):向队列头插入元素，无返回
dq = deque()
dq.append("a")
dq.appendleft("x")
dq.extend(["aa","bb"])
print(dq)
- extend([var1,var2,...]):插入一组元素，无返回值
dq = deque()
dq.append("a")
dq.extend(["aa","bb"])
print(dq)
- extendleft([var1, var2,...]):向队伍头插入元素，无返回值
dq = deque()
dq.append("a")
dq.appendleft("x")
dq.extend(["aa","bb"])
dq.extendleft(["xs","zm"])
print(dq)
-insert(index, var):向指定位置插入元素，无返回
dq = deque()
dq.append("a")
dq.appendleft("x")
dq.extend(["aa","bb"])
dq.insert(1, "s")
print(dq)
- remov(var):删除指定var，无返回值
dq = deque()
dq.append("a")
dq.appendleft("x")
dq.extend(["aa","bb"])
dq.extendleft(["xs","zm"])
print(dq)
dq.remove("a")
print(dq)
- pop():删除队尾元素,返回删除的元素
dq = deque()
dq.append("a")
dq.appendleft("x")
dq.extend(["aa","bb"])
dq.extendleft(["xs","zm"])
re = dq.pop()
print(re)
- popleft():删除队头元素
dq = deque()
dq.append("a")
dq.appendleft("x")
dq.extend(["aa","bb"])
dq.extendleft(["xs","zm"])
print(dq)
re = dq.popleft()
print(re)
- remove(var)：删除指定var，无返回值
dq = deque()
dq.append("a")
dq.appendleft("x")
dq.extend(["aa","bb"])
dq.extendleft(["xs","zm"])
print(dq)
dq.remove("xs")
print(dq)
- clear():清空队列
dq = deque()
dq.append("a")
dq.appendleft("x")
dq.extend(["aa","bb"])
dq.extendleft(["xs","zm"])
dq.clear()
print(dq)
- copy():拷贝队列，返回拷贝后的新队列
dq = deque()
dq.append("a")
dq.appendleft("x")
dq.extend(["aa","bb"])
dq.extendleft(["xs","zm"])
print("原队列：",dq)
print("原队列id：", id(dq))
dq1 = dq.copy()
print("拷贝的队列:", dq1)
print("拷贝后队列的id", id(dq1))
- count(var):统计指定var的个数，若存在返回结果，反之，返回0
dq = deque()
dq.append("a")
dq.appendleft("x")
dq.extend(["aa","bb"])
dq.extendleft(["xs","zm"])
print(dq.count("aa"))
print(dq.count("b"))
- reverse():在原队列基础上反转队列，不会创建新的队列
dq = deque()
dq.append("a")
dq.appendleft("x")
dq.extend(["aa","bb"])
dq.extendleft(["xs","zm"])
print(id(dq))
#reverse():反转队列
dq.reverse()
print(dq)
print(id(dq))
- rotate(num):把队尾num个元素插入到队头
dq = deque()
dq.append("a")
dq.appendleft("x")
dq.extend(["aa","bb"])
dq.extendleft(["xs","zm"])
print("原队列", dq)
#rotate(num):轮转【相当于pop(),然后再appendleft()】
dq.rotate(4)
print("轮转后的队列", dq)
循环队列
非内置队列，将普通的队列首尾相连，head指向头，tail指向尾，每次插入一位元素tail都后移一位，每次删除元素head都后移
"""
循环队列：插入元素，tail++，删除元素，head++，
"""
class CircQueue():
def __init__(self, maxsize):
self.queue = [None] * maxsize
self.maxsize = maxsize
self.head = 0
self.tail = 0
self.cnt = 0
#判断队列是否为空
def is_empty(self):
return self.cnt == 0
#判断队列是否满
def is_full(self):
return self.cnt == self.maxsize
#向队列中插入元素
def push(self, val):
if self.is_full():
print("队列满了，无法插入元素")
return
if self.is_empty():
self.queue[self.tail] = val
self.cnt = 1
else:
self.tail = (self.tail + 1) % self.maxsize
self.queue[self.tail] = val
self.cnt += 1
def pop(self):
if self.is_empty():
return " "
val = self.queue[self.head]
self.head = (self.head + 1) % self.maxsize
self.cnt -= 1
return val
#清空队列
def clear(self):
if self.is_empty():
return True
self.head = 0
self.tail = 0
self.cnt = 0
return True
#计算当前队列长度
def len(self):
return self.cnt
#获取列表中所有元素
def get(self):
if self.is_empty():
return []
l = []
for i in range(self.cnt):
index = (i + self.head) % self.maxsize
l.append(self.queue[index])
print(l)
if __name__ == '__main__':
q = CircQueue(10)
q.push("a")
q.push("b")
q.push("c")
q.get()
q.pop()
q.get()
练习
最大k个数和最小k个数:
heaqp.nlargest(k, data)
heaqp.nsmallest(k, data)
import heaqp
nums = [1, 2, 3, 10, 9]
#最大3个数
ret1 = heaqp.nlargest(3, nums)
print(ret1)
#最小3个数
ret2 = heaqp.nsmallest(3, nums)
print(ret2)
