+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-08(47)

2019-09(90)

2019-10(13)

2019-11(9)

2019-12(19)

数据结构12:双端队列与回文词判定

发布于2020-08-29 15:28     阅读(719)     评论(0)     点赞(3)     收藏(3)


0

1

2

3

4

5

6

7

目录

 

一、什么是双端队列

二、双端队列Deque定义的操作:

三、双端队列的python实现

四、回文词判定

五、回文词判定代码实现


一、什么是双端队列

双端队列Deque是一种有序的数据集

跟队列相似,其两端可以称为“首端”与“尾端”,区别是:双端队列Deque中数据项可以从队首加入,也可以从队尾加入,数据项也可以从两端移除。因此,从某种意义上说,双端队列集成了栈和队列的能力

双端队列不具有内在的“后进先出”或者“先进先出”的特性,如果用双端队列来模拟栈或者队列,需要由使用者自行维护操作的一致性。

二、双端队列Deque定义的操作:

三、双端队列的python实现

  1. class Deque():
  2. def __init__(self):
  3. self.items = []
  4. def isEmpty(self):
  5. return self.items == []
  6. def addFront(self, item):
  7. self.items.append(item)
  8. def addRear(self, item):
  9. self.items.insert(0, item)
  10. def removeFront(self):
  11. return self.items.pop()
  12. def removeRear(self):
  13. return self.items.pop(0)
  14. def size(self):
  15. return len(self.items)

四、回文词判定

回文词是指正读和反读都一样的词如radar, toot,上海自来水来自海上

判定方法:

用双端队列很容易解决回文词的问题,先将需要判定的词加入Deque,在从两端同时移除字符判定是否相同,直到deque中剩下0个或1个字符。

五、回文词判定代码实现

  1. class Deque():
  2. def __init__(self):
  3. self.items = []
  4. def isEmpty(self):
  5. return self.items == []
  6. def addFront(self, item):
  7. self.items.append(item)
  8. def addRear(self, item):
  9. self.items.insert(0, item)
  10. def removeFront(self):
  11. return self.items.pop()
  12. def removeRear(self):
  13. return self.items.pop(0)
  14. def size(self):
  15. return len(self.items)
  16. def palchecker(String):
  17. chardeque = Deque()
  18. for ch in String:
  19. chardeque.addRear(ch)
  20. stillEqual = True
  21. while chardeque.size() > 1 and stillEqual:
  22. first = chardeque.removeFront()
  23. last = chardeque.removeRear()
  24. if first != last:
  25. stillEqual = False
  26. return stillEqual
  27. print(parChecker('lsdkdf'))
  28. print(parChecker('qwewq'))

原文链接:https://blog.csdn.net/xddwz/article/details/108285075

0

1

2

3

4

5

6

7

8

9



所属网站分类: 技术文章 > 博客

作者:dfh8374

链接: https://www.pythonheidong.com/blog/article/498150/42bb0ea37026438b69a6/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

3 0
收藏该文
已收藏

评论内容:(最多支持255个字符)