鱼C论坛

 找回密码
 立即注册
查看: 2218|回复: 1

[技术交流] Python 数据结构之栈和队列 —— (一)功能实现

[复制链接]
发表于 2020-3-21 13:29:13 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
Python 数据结构之栈和队列 —— (一)功能实现


继前面链表的学习后,接着学习栈和队列这两种线性表。

链表的特点是灵活运用内存空间,对元素的操作不可直接读取,需要 next 的一个个找。

栈和队列也是特殊的线性表,其特点是限制插入和删除元素的操作,既可以基于顺序存储也可以基于链式存储。



关键记住,后进先出(Last In First Out),简称为 LIFO 线性表,其操作均在一端实现。

栈的基本运算有六种:

构造空栈:InitStack(S)
判栈空:StackEmpty(S)
判栈满:StackFull(S)
进栈:Push(S, x)(可形象地理解为压入,这时栈中会多一个元素)
退栈:Pop(S)(可形象地理解为弹出,弹出后栈中就无此元素了)
取栈顶元素:StackTop(S)(与弹出不同,只是使用栈顶元素的值,该元素仍在栈顶不会改变)

由于栈也是线性表,因此线性表的存储结构对栈也适用。

通常栈有顺序栈和链栈两种存储结构,这两种存储结构的不同,则使得实现栈的基本运算的算法也有所不同。

关于顺序栈,需要了解 ‘上溢’ 和 ‘下溢’ 的概念。栈满时 push 就会上溢,栈空时 pop 就会下溢。与判栈满和判栈空关系紧密。

链栈由于没有存储空间限制,没有 ‘上溢’ 的限制,链栈只要有头指针即可操作,也十分方便。

队列

队列 (Queue) 也是一种运算受限的线性表,它的运算限制与栈不同,两头都有限制。

插入只能在表的一端进行 (只进不出),而删除只能在表的另一端进行 (只出不进)。

允许插入的一端称为队尾 (rear),允许删除的一端称为队头 (Front),队列的操作原则是先进先出的,所以队列又称作 FIFO 表 (First In First Out)

队列的基本运算也有六种:

构造空队:InitQueue(Q)
判队空:QueueEmpty(Q)
判队满:QueueFull(Q)
入队:EnQueue(Q, x)
出队:DeQueue(Q)
取队头元素:QueueFront(Q)(与出队不同,队头元素仍然保留)

队列也有顺序存储和链式存储两种存储结构,前者称顺序队列,后者为链队。

顺序队列,也有 ‘上溢’ 和 ‘下溢’,但是还有一种 ‘假上溢’。

在一段连续的存储空间中,由一个队列头指针和一个尾指针表示这个队列,当头指针和尾指针指向同一个位置时,队列为空。

也就是说,队列是由两个指针中间的元素构成的。

当元素出队和入队时,实际上是指针在移动,即使队列没有满(头指针不在头部),如果尾指针在尾部也会出现 ‘溢出’,这就是 ‘假上溢’。

为了克服这种现象,我们引入循环向量的概念,就好比是把向量空间弯起来,形成一个头尾相接的环形。

这样,当存于其中的队列头尾指针移到向量空间的上界 (尾部) 时,再加 1 的操作 (入队或出队) 就使指针指向向量的下界,也就是从头开始。

这时的队列就称循环队列。通常我们应用的大都是循环队列。

由于循环的原因,光看头尾指针重叠在一起我们并不能判断队列是空的还是满的,这时就需要处理一些边界条件,以区别队列是空还是满。

方法至少有三种,一种是另设一个布尔变量来判断 (就是请别人看着,是空还是满由他说了算)。

第二种是少用一个元素空间,当入队时,先测试入队后尾指针是不是会等于头指针,如果相等就算队已满,不许入队。

第三种就是用一个计数器记录队列中的元素的总数,这样就可以随时知道队列的长度了。

只要队列中的元素个数等于向量空间的长度,就是队满。一般我们应用第二种即可,少用一个空间。

当然,如果不知道元素最大长度,为了灵活利用内存空间,也可以使用链队。

Python 实现

顺序存储方式的实现:利用 Python 的 list 数据结构及相关方法即可实现。

栈:用 list 的 append 及 pop 方法即可。

队列:用 deque 的 append 及 popleft 方法即可。

  1. stack = [2, 4, 6, 8]
  2. stack.append(1)  # append 实现入栈
  3. print(stack)  # [2, 4, 6, 8, 1]
  4. stack.append(3)
  5. print(stack)  # [2, 4, 6, 8, 1, 3]
  6. print(stack.pop())  # pop 实现出栈  3
  7. print(stack)  # [2, 4, 6, 8, 1]
  8. print(stack.pop(0))  # pop(0) 可以实现队列的出队功能,但是其时间复杂度为O(n)  2
  9. print(stack)  # [4, 6, 8, 1]

  10. from collections import deque

  11. quene = deque([1, 3, 5, 7])
  12. quene.append(9)  # append 入队功能
  13. print(quene)  # deque([1, 3, 5, 7, 9])
  14. quene.extend([8, 9])  # extend 及 extendleft 功能 参数为可迭代对象,区别于append
  15. quene.extendleft([11, 12])
  16. print(quene)  # deque([12, 11, 1, 3, 5, 7, 9, 8, 9])
  17. print(quene.popleft())  # popleft() 出队功能实现,复杂度为O(1)  12
  18. print(quene)  # deque([11, 1, 3, 5, 7, 9, 8, 9])

  19. d = deque('12345')
  20. print(d)  # deque(['1', '2', '3', '4', '5'])
  21. print(d.popleft())  # 1
  22. print(d.pop())  # 5
  23. print(d)  # deque(['2', '3', '4'])

  24. d = deque('12345', maxlen=5)  # 限制 deque 的长度
  25. d.append(6)  # 当超过限制数的项时, 另一边的项会自动删除
  26. print(d)  # deque(['2', '3', '4', '5', 6], maxlen=5)
复制代码


也可以将栈、队列写成一个类,实现我们需要的功能,用的时候导入模块:

  1. class Stack:
  2.     def __init__(self, size):
  3.         self.size = size
  4.         self.stack = []
  5.         self.top = -1

  6.     def push(self, ele):  # 入栈之前检查栈是否已满
  7.         if self.isfull():
  8.             raise Exception("out of range")
  9.         else:
  10.             self.stack.append(ele)
  11.             self.top = self.top + 1

  12.     def pop(self):  # 出栈之前检查栈是否为空
  13.         if self.isempty():
  14.             raise Exception("stack is empty")
  15.         else:
  16.             self.top = self.top - 1
  17.             return self.stack.pop()

  18.     def isfull(self):
  19.         return self.top + 1 == self.size

  20.     def isempty(self):
  21.         return self.top == -1


  22. class Queue:
  23.     def __init__(self, size):
  24.         self.size = size
  25.         self.front = -1
  26.         self.rear = -1
  27.         self.queue = []
复制代码


队列的具体实现可自行完成,与栈类似,注意 front 和 rear 两个指针即可。试着实现一个循环队列更加实用。

栈和队列的链式存储,在熟悉了链表那一套理论后,也不是难事。

比如栈链,push 方法将新元素结点建成与原头结点连接,作为新头结点即可;

pop 将头结点取出,将第二个结点作为新的头结点即可。操作均在头结点上。

  1. n = node(data)
  2. n.next = head
  3. headnew = n
复制代码


队列的操作需要两个指针,与上文的 Queue 类可能比较像,但是略微麻烦,因为操作的是链表。

总结

理解栈和队列的基本特点,顺序存储方法直接用 Python 实现很方便,有助于我们直接应用解决实际问题。

基于链表的存储,需要我们打好关于链表的理论和应用基础,并不难实现。

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2020-3-21 13:31:51 | 显示全部楼层
沙发,感谢楼主分享
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-6-9 18:46

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表