This article is an example of a Python implementation of data structures and algorithms for double-ended queues. Shared for your reference. Specific analysis is as follows:
I. Overview
Double-ended queue (deque, full name double-ended queue) is a linear data structure with the nature of the queue and stack. Double-ended queue also has two ends: the first (front), the end of the queue (rear), but different from the queue is that the insertion operation can be carried out at both ends (the first and the end of the queue), and the same deletion operation.
II. ADT
Double-ended queue ADTs (Abstract Data Types) generally provide the following interfaces:
① Deque() creates a double-ended queue
② addFront(item) Inserts an item into the head of the queue.
③ addRear(item) inserts an item to the end of the queue
④ removeFront() returns the item at the head of the queue and removes the item from the double-ended queue.
⑤ removeRear() returns the item at the end of the queue and removes it from the double-ended queue.
⑥ empty() Determines whether the double-ended queue is empty or not
⑦ size() Returns the number of items in a double-ended queue.
A schematic of the double-ended queue operation is shown below:
III. Python implementation
In Python, there are two ways to implement the above double-ended queue ADT: using the built-in type list, and using the standard library (which is actually the standard implementation of double-ended queues in Python).
The difference between the two approaches is mainly in performance (see specifically | TimeComplexity）：
manipulate|implementation method list ----------------------------------------- addFront O(n) O(1) ----------------------------------------- addRear O(1) O(1) ----------------------------------------- removeFront O(n) O(1) ----------------------------------------- removeRear O(1) O(1)
1、Use the built-in type list
#!/usr/bin/env python
# -*- coding: utf-8 -*-
class Deque:
def __init__(self):
= []
def addFront(self, item):
(0, item)
def addRear(self, item):
(item)
def removeFront(self):
return (0)
def removeRear(self):
return ()
def empty(self):
return () == 0
def size(self):
return len()
2. Use of standardized libraries
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from collections import deque
class Deque:
def __init__(self):
= deque()
def addFront(self, item):
(item)
def addRear(self, item):
(item)
def removeFront(self):
return ()
def removeRear(self):
return ()
def empty(self):
return () == 0
def size(self):
return len()
IV. Applications
A palindrome is a word or sentence that reads the same both forward and backward, and is a rhetorical device and play on words.
Examples in English:
madam
able was i ere i saw elba
Chinese example:
non-floral
All for one and one for all
If you want to implement a palindrome verification algorithm (to verify that a given string is a palindrome), it will be very easy to use the Deque class: the string is stored in a double-ended queue, and at the same time take out the first and last characters and compare them to see if they are equal, as long as there is a pair of characters that are unequal, the string is not a palindrome; if they are all equal, then the string is a palindrome. Specific code is as follows:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def palchecker(aString):
chardeque = Deque()
for ch in aString:
(ch)
while () > 1:
first = ()
last = ()
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'All for one and one for all'
print(u'"%s"%s is a palindrome.' % (str2, u'' if palchecker(str2) else u'No.'))
str3 = u"What's wrong?"
print(u'"%s"%s is a palindrome.' % (str3, u'' if palchecker(str3) else u'No.'))
Running results:
$ python "able was i ere i saw elba" is palindrome "All for one and one for all."It's a palindrome. "What's wrong?"不It's a palindrome.
I hope that what I have described in this article will help you in your Python programming.