栈

概念：栈是一种特殊的线性表，保存一组元素的集合，插入和删除只能在尾部操作
其特点：
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():插入元素,省略后两个参数，此时队列满了继续插入元素不会报异常

#创建一个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()

双向队列常用方法

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