欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之雙端隊(duì)列詳解

 更新時(shí)間:2015年04月22日 14:35:53   作者:RussellLuo  
這篇文章主要介紹了Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之雙端隊(duì)列,詳細(xì)講述了雙端隊(duì)列的概念、功能、定義及Python實(shí)現(xiàn)與使用雙端隊(duì)列的相關(guān)技巧,非常具有實(shí)用價(jià)值,需要的朋友可以參考下

本文實(shí)例講述了Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之雙端隊(duì)列。分享給大家供大家參考。具體分析如下:

一、概述

雙端隊(duì)列(deque,全名double-ended queue)是一種具有隊(duì)列和棧性質(zhì)的線性數(shù)據(jù)結(jié)構(gòu)。雙端隊(duì)列也擁有兩端:隊(duì)首(front)、隊(duì)尾(rear),但與隊(duì)列不同的是,插入操作在兩端(隊(duì)首和隊(duì)尾)都可以進(jìn)行,刪除操作也一樣。

二、ADT

雙端隊(duì)列ADT(抽象數(shù)據(jù)類型)一般提供以下接口:

① Deque() 創(chuàng)建雙端隊(duì)列
② addFront(item) 向隊(duì)首插入項(xiàng)
③ addRear(item) 向隊(duì)尾插入項(xiàng)
④ removeFront() 返回隊(duì)首的項(xiàng),并從雙端隊(duì)列中刪除該項(xiàng)
⑤ removeRear() 返回隊(duì)尾的項(xiàng),并從雙端隊(duì)列中刪除該項(xiàng)
⑥ empty() 判斷雙端隊(duì)列是否為空
⑦ size() 返回雙端隊(duì)列中項(xiàng)的個(gè)數(shù)

雙端隊(duì)列操作的示意圖如下:

三、Python實(shí)現(xiàn)

在Python中,有兩種方式可以實(shí)現(xiàn)上述的雙端隊(duì)列ADT:使用內(nèi)建類型list、使用標(biāo)準(zhǔn)庫(kù)collections.deque(其實(shí)collections.deque就是Python中雙端隊(duì)列的標(biāo)準(zhǔn)實(shí)現(xiàn))。

兩種方式的不同主要體現(xiàn)在性能上(具體參考 collections.deque | TimeComplexity):

操作|實(shí)現(xiàn)方式  list  collections.deque
-----------------------------------------
addFront    O(n)  O(1)
-----------------------------------------
addRear     O(1)  O(1)
-----------------------------------------
removeFront   O(n)  O(1)
-----------------------------------------
removeRear   O(1)  O(1)

1、使用內(nèi)建類型list

#!/usr/bin/env python
# -*- coding: utf-8 -*-
class Deque:
  def __init__(self):
    self.items = []
  def addFront(self, item):
    self.items.insert(0, item)
  def addRear(self, item):
    self.items.append(item)
  def removeFront(self):
    return self.items.pop(0)
  def removeRear(self):
    return self.items.pop()
  def empty(self):
    return self.size() == 0
  def size(self):
    return len(self.items)

2、使用標(biāo)準(zhǔn)庫(kù)collections.deque

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from collections import deque
class Deque:
  def __init__(self):
    self.items = deque()
  def addFront(self, item):
    self.items.appendleft(item)
  def addRear(self, item):
    self.items.append(item)
  def removeFront(self):
    return self.items.popleft()
  def removeRear(self):
    return self.items.pop()
  def empty(self):
    return self.size() == 0
  def size(self):
    return len(self.items)

四、應(yīng)用

回文(palindrome)是正讀反讀都一樣的單詞或句子,是一種修辭方式和文字游戲。

英文例子:

madam
able was i ere i saw elba

中文例子:

花非花
人人為我、我為人人
如果要實(shí)現(xiàn)一個(gè) 回文驗(yàn)證算法(驗(yàn)證一個(gè)給定的字符串是否為回文),使用Deque類將非常容易:將字符串存儲(chǔ)到雙端隊(duì)列,同時(shí)取出首尾字符并比較是否相等,只要有一對(duì)字符不等,則該字符串不是回文;若全部相等,則該字符串為回文。具體代碼如下:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
def palchecker(aString):
  chardeque = Deque()
  for ch in aString:
    chardeque.addRear(ch)
  while chardeque.size() > 1:
    first = chardeque.removeFront()
    last = chardeque.removeRear()
    if first != last:
      return False
  return True
if __name__ == '__main__':
  str1 = 'able was i ere i saw elba'
  print('"%s" is%s palindrome' % (str1, '' if palchecker(str1) else ' not'))
  str2 = u'人人為我、我為人人'
  print(u'"%s"%s是回文' % (str2, u'' if palchecker(str2) else u'不'))
  str3 = u"What's wrong 怎么啦"
  print(u'"%s"%s是回文' % (str3, u'' if palchecker(str3) else u'不'))

運(yùn)行結(jié)果:

$ python palchecker.py
"able was i ere i saw elba" is palindrome
"人人為我、我為人人"是回文
"What's wrong 怎么啦"不是回文

希望本文所述對(duì)大家的Python程序設(shè)計(jì)有所幫助。

相關(guān)文章

  • 淺析Python字符串中的r和u的區(qū)別

    淺析Python字符串中的r和u的區(qū)別

    在Python中,字符串前面我們經(jīng)??吹綍?huì)加一些前綴,例如u、r、b、f。這篇文章將帶大家簡(jiǎn)單了解一下字符串前加r(R)或u/(U)的前綴的區(qū)別,快來(lái)跟隨小編一起學(xué)習(xí)吧
    2021-12-12
  • 用Python實(shí)現(xiàn)BP神經(jīng)網(wǎng)絡(luò)(附代碼)

    用Python實(shí)現(xiàn)BP神經(jīng)網(wǎng)絡(luò)(附代碼)

    這篇文章主要介紹了用Python實(shí)現(xiàn)BP神經(jīng)網(wǎng)絡(luò)(附代碼),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2019-07-07
  • Python struct模塊解析

    Python struct模塊解析

    我們知道python只定義了6種數(shù)據(jù)類型,字符串,整數(shù),浮點(diǎn)數(shù),列表,元組,字典。但是C語(yǔ)言中有些字節(jié)型的變量,在python中該如何實(shí)現(xiàn)呢?這點(diǎn)頗為重要,特別是要在網(wǎng)絡(luò)上進(jìn)行數(shù)據(jù)傳輸?shù)脑挕?/div> 2014-06-06
  • Python中的min及返回最小值索引的操作

    Python中的min及返回最小值索引的操作

    這篇文章主要介紹了Python中的min及返回最小值索引的操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
    2021-05-05
  • Python中的@cache巧妙用法

    Python中的@cache巧妙用法

    緩存是一種空間換時(shí)間的策略,緩存的設(shè)置可以提高計(jì)算機(jī)系統(tǒng)的性能,這篇文章主要介紹了Python中的@cache巧妙用法,需要的朋友可以參考下
    2023-04-04
  • 手把手帶你用python爬取小姐姐私房照

    手把手帶你用python爬取小姐姐私房照

    這篇文章主要介紹了用python如何爬取小姐姐私房照,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-08-08
  • Python實(shí)現(xiàn)自動(dòng)定時(shí)登錄校園網(wǎng)

    Python實(shí)現(xiàn)自動(dòng)定時(shí)登錄校園網(wǎng)

    這篇文章主要和大家分享一個(gè)Python自動(dòng)定時(shí)登錄校園網(wǎng)的腳步,這樣就不用自己手動(dòng)去登錄,文中的示例代碼簡(jiǎn)潔易懂,需要的可以參考一下
    2023-06-06
  • 利用Python+Java調(diào)用Shell腳本時(shí)的死鎖陷阱詳解

    利用Python+Java調(diào)用Shell腳本時(shí)的死鎖陷阱詳解

    這篇文章主要給大家介紹了關(guān)于利用Python+Java調(diào)用Shell腳本時(shí)的死鎖陷阱的相關(guān)資料,文章通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。
    2018-01-01
  • 快速進(jìn)修Python指南之迭代器Iterator與生成器

    快速進(jìn)修Python指南之迭代器Iterator與生成器

    這篇文章主要為大家介紹了Java開發(fā)者快速進(jìn)修Python指南之迭代器Iterator與生成器示例解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-12-12
  • Django框架實(shí)現(xiàn)在線考試系統(tǒng)的示例代碼

    Django框架實(shí)現(xiàn)在線考試系統(tǒng)的示例代碼

    這篇文章主要介紹了Django框架實(shí)現(xiàn)在線考試系統(tǒng)的示例代碼,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2020-11-11

最新評(píng)論